Jackson_Miller @ 2023-08-17 10:31:51
#include<bits/stdc++.h>
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
using namespace std;
const int N=1e5+10;
struct Tree{
int wei,val,siz,ch[2];
}t[N];
int n,m,tot,root;
int last,ans,a,b,c;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
inline void pushup(int x){
t[x].siz = t[ls(x)].siz + t[rs(x)].siz + 1;
}
void spilt(int x,int k,int &a,int &b){
if(!x){
a=0,b=0;
return ;
}
if(t[x].val<=k){
a=x;
spilt(rs(x),k,rs(x),b);
}
else{
b=x;
spilt(ls(x),k,a,ls(x));
}
}
int merge(int x,int y){
if(!x||!y){
return x+y;
}
if(t[x].wei<=t[y].wei){
rs(x)=merge(rs(x),y);
pushup(x);
return x;
}
else{
ls(y)=merge(x,ls(y));
pushup(y);
return y;
}
}
void insert(int k){
t[tot++].val=k,t[tot].wei=rand();
t[tot].siz=1;
spilt(root,k,a,b);
root=merge(merge(a,tot),b);
}
void remove(int k){
spilt(root,k,a,b);
spilt(a,c,a,b);
c=merge(ls(c),rs(c));
c=merge(merge(a,c),b);
}
int ck_rk(int k){
int rank;
spilt(root,k-1,a,b);
rank=t[a].siz;
root=merge(a,b);
return rank;
}
int ck_val(int x,int k){
if(k==t[ls(x)].siz+1){
return t[x].val;
}
if(k<=t[ls(x)].siz){
return ck_val(ls(x),k);
}
else{
return ck_val(rs(x),k-t[ls(x)].siz-1);
}
}
int ck_pre(int x){
return ck_val(root,ck_rk(x)-1);
}
inline int ck_next(int x){
return ck_val(root,ck_rk(x+1));
}
int main(){
int n,m;
n=read(),m=read();
for(int i=1;i<=n;i++){
int x;
x=read();
insert(x);
}
while(m--){
int op,qwq;
op=read();
qwq=read()^last;
if(op==1){
insert(qwq);
}
else if(op==2){
remove(qwq);
}
else if(op==3){
last=ck_rk(qwq);
}
else if(op==4){
last=ck_val(root,qwq);
}
else if(op==5){
last=ck_pre(qwq);
}
else if(op==6){
last=ck_next(qwq);
}
ans^=last;
}
cout<<ans;
} by Special_Judge @ 2023-08-17 11:16:57
@Jackson_Miller 问题很多，我稍微粗看了一下，建议重写（
#include<bits/stdc++.h>
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
using namespace std;
const int N=1e5+10;
struct Tree{
int wei,val,siz,ch[2];
}t[N];
int n,m,tot,root;
int last,ans,a,b,c;
int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
void pushup(int x){
t[x].siz = t[ls(x)].siz + t[rs(x)].siz + 1;
}
void split(int x,int k,int &a,int &b){//1. split拼错了
if(!x){
a=0,b=0;
return ;
}
if(t[x].val<=k){
a=x;
split(rs(x),k,rs(x),b);
}
else{
b=x;
split(ls(x),k,a,ls(x));
}
pushup(x);//2. split之后要pushup
}
int merge(int x,int y){
if(!x||!y){
return x+y;
}
if(t[x].wei<=t[y].wei){
rs(x)=merge(rs(x),y);
pushup(x);
return x;
}
else{
ls(y)=merge(x,ls(y));
pushup(y);
return y;
}
}
void insert(int k){
t[++tot].val=k;//3. 要写++tot，否则节点编号不对
t[tot].wei=rand();
t[tot].siz=1;
split(root,k,a,b);
root=merge(merge(a,tot),b);
}
void remove(int k){
//4. 原来的这两句split我真的无力吐槽了，正确的是这样的：
//先split成两棵树a和c，a中是小于等于k的数，c是大于k的数
//再split a,分成a和b，a是小于k的数，b是等于k的树
split(root,k,a,c);
split(a,k-1,a,b);
//5. 你的root不要了？
b=merge(ls(b),rs(b));
root=merge(merge(a,b),c);
}
int ck_rk(int k){
int rank;
split(root,k-1,a,b);
rank=t[a].siz;
root=merge(a,b);
return rank+1;//6. 排名应当加1
}
int ck_val(int x,int k){
if(k==t[ls(x)].siz+1){
return t[x].val;
}
if(k<=t[ls(x)].siz){
return ck_val(ls(x),k);
}
else{
return ck_val(rs(x),k-t[ls(x)].siz-1);
}
}
int ck_pre(int x){
//7. 这写的啥...找前驱和排名有啥关系...正确做法是split出一棵值全部小于x的树然后找它的最右节点
split(root,x-1,a,b);
int now=a;
while(rs(now))now=rs[now];
root=merge(a,b);
return t[now].val;
}
int ck_next(int x){
//8. 同7.，我不想改了
return ck_val(root,ck_rk(x+1));
}
int main(){
int n,m;
n=read(),m=read();
for(int i=1;i<=n;i++){
int x;
x=read();
insert(x);
}
while(m--){
int op,qwq;
op=read();
qwq=read()^last;
if(op==1){
insert(qwq);
}
else if(op==2){
remove(qwq);
}
else if(op==3){
last=ck_rk(qwq);
}
else if(op==4){
last=ck_val(root,qwq);
}
else if(op==5){
last=ck_pre(qwq);
}
else if(op==6){
last=ck_next(qwq);
}
ans^=last;
}
cout<<ans;
} by Special_Judge @ 2023-08-17 11:18:55
我把我自己的写法贴一下吧 Link
by Jackson_Miller @ 2023-08-17 11:20:12
@Special_Judge 谢谢你大佬，关注你了
by 羊羊君的幻想 @ 2023-08-17 11:23:06
1.N大小要开到1e6，因为m次操作，可以添加m次数
2.前驱和后继那里写的有点问题
3.split那里没有pushup
4.删除那里写的有问题
暂时就发现这么多，还是没有调好，别的细节你在看看吧
by 羊羊君的幻想 @ 2023-08-17 11:23:50
@Jackson_Miller 问题是真的多，反反复复看了好几遍都没调好
by Special_Judge @ 2023-08-17 11:27:59
@Jackson_Miller 看了你最近一次的提交，8.那里要找最左节点啊...这是二叉搜索树的性质，平衡树是一棵二叉搜索树
int ck_next(int x){
//8. 同7.，我不想改了
split(root,x,a,b);
int now=b;
while(ls(now))now=ls(now);
root=merge(a,b);
return t[now].val;
}by Special_Judge @ 2023-08-17 11:29:15
可能还有一些细节的错误我没看出来，还是建议理解了平衡树再来写，看你的代码感觉你对平衡树的性质不是很理解