帮我调出这个代码,你就能得到一个关注
P3369 【模板】普通平衡树
only wa on 13
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M=3e5+110;
const int Mod=4e7+110;
mt19937_64 Rand(20100123);
int Read(){
int sum=0,k=1;
char c=getchar();
while(c>'9'||c<'0'){
if(c=='-')k=-2;
c=getchar();
}
while(c>='0'&&c<='9'){
sum=sum*10+c-48;
c=getchar();
}return sum*k;
}
struct Tree_Node{
int lz,rz;
int Val,Nval;
int Size;
}t[M];
void Update(int u){t[u].Size=t[t[u].lz].Size+t[t[u].rz].Size+1;}
int Sum=0;
int Get_Node(int val){
t[++Sum].Val=val;
t[Sum].Size=1;
t[Sum].Nval=Rand();
return Sum;
}
int Roxt,Royt,Rozt;
void Val_Split(int Now,int val,int &Roxt,int &Royt){//权值分裂
if(Now==0){
Royt=Roxt=0;
return ;
}
if(t[Now].Val<=val){
Roxt=Now;
Val_Split(t[Now].rz,val,t[Now].rz,Royt);
}
else{
Royt=Now;
Val_Split(t[Now].lz,val,Roxt,t[Now].lz);
}
Update(Now);
}
void Rand_Split(int Now,int Num,int &Roxt,int &Royt){
if(Now==0){
Royt=Roxt=0;
return;
}
if(Num<=t[t[Now].lz].Size){
Royt=Now;
Rand_Split(t[Now].lz,Now,Roxt,t[Now].lz);
}
else{
Roxt=Now;
Rand_Split(t[Now].rz,Num-t[t[Now].lz].Size-1,t[Now].rz,Royt);
}
Update(Now);
}
int Merge(int u,int v){
if(u==0||v==0) return u+v;
if(t[u].Nval<t[v].Nval){
t[u].rz=Merge(t[u].rz,v);
Update(u);
return u;
}
else{
t[v].lz=Merge(u,t[v].lz);
Update(v);
return v;
}
}
int Root;
void Insert(int val){
Val_Split(Root,val,Roxt,Royt);
Root=Merge(Merge(Roxt,Get_Node(val)),Royt);
return ;
}
void Group_Delete(int val){
Val_Split(Root,val,Roxt,Rozt);
Val_Split(Roxt,val-1,Roxt,Royt);
Root=Merge(Roxt,Rozt);
}
void Single_Delete(int val){
Val_Split(Root,val,Roxt,Rozt);
Val_Split(Roxt,val-1,Roxt,Royt);
Royt=Merge(t[Royt].lz,t[Royt].rz);
Root=Merge(Merge(Roxt,Royt),Rozt);
}
int Find_Kth(int Rot,int k){
int Now=Rot;
for(int i=1;i>=0;i++){
if(k<=t[t[Now].lz].Size) Now=t[Now].lz;
else if(k==t[t[Now].lz].Size+1) return t[Now].Val;
else{
k=k-t[t[Now].lz].Size-1;
Now=t[Now].rz;
}
}
}
int Find_Rank(int val){
Val_Split(Root,val-1,Roxt,Royt);
int Res=t[Roxt].Size+1;
Root=Merge(Roxt,Royt);
return Res;
}
int Find_From(int val){
Val_Split(Root,val-1,Roxt,Royt);
int Ans=Find_Kth(Roxt,t[Roxt].Size);
Root=Merge(Roxt,Royt);
return Ans;
}
int Find_Next(int val){
Val_Split(Root,val,Roxt,Royt);
int Ans=Find_Kth(Royt,1);
Root=Merge(Roxt,Royt);
return Ans;
}
signed main(){
// freopen("in.in", "r", stdin);
// freopen("std.txt", "w", stdout);
int n=Read();
// Insert(0x3f3f3f3f);
// Insert(-0x3f3f3f3f);
for(int i=1;i<=n;i++){
int opt=Read(),x=Read();
if(opt==1){
Insert(x);
continue;
}
if(opt==2){
Single_Delete(x);
continue;
}
if(opt==3){
Insert(x);
cout<<Find_Rank(x)<<endl;
Single_Delete(x);
continue;
}
if(opt==4){
Insert(x);
cout<<Find_Kth(Root,x+1)<<endl;
Single_Delete(x);
continue;
}
if(opt==5){
Insert(x);
cout<<Find_From(x)<<endl;
Single_Delete(x);
continue;
}
if(opt==6){
Insert(x);
cout<<Find_Next(x)<<endl;
Single_Delete(x);
continue;
}
}
return 0;
}