网站建设网页,东莞网站开发哪里找,淘宝购物网站,免费视频素材软件app文章目录前言注意事项代码所谓替罪羊树#xff0c;就是有一头替罪羊的树 #xff08;逃#xff09;
前言
在看完了一大堆各种平衡树的教程之后#xff0c;决定学一个这个 因为它有一个很关键的好处#xff1a;无须旋转 可以在pushup复杂度太恶心的题中做到splay做不到的…
文章目录前言注意事项代码所谓替罪羊树就是有一头替罪羊的树 逃
前言
在看完了一大堆各种平衡树的教程之后决定学一个这个 因为它有一个很关键的好处无须旋转 可以在pushup复杂度太恶心的题中做到splay做不到的事情 比如平衡树套线段树 但是在区间问题中还是splay最强啦
注意事项
拍扁操作必须是未被删除的点拍扁时要记录点的副本数量
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define il inline
const int N5e6100;
const int M150;
const int mod998244353;
inline ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}return x*f;
}
int n,m;
int ls[N],rs[N],siz[N],val[N],cnt[N],de[N],tot,rub[N],top,r;
int q[N],num,o[N];
il int New(int v,int oo){int xtop?rub[top--]:tot;ls[x]rs[x]0;siz[x]cnt[x]oo;val[x]v;de[x]0;return x;
}
il void pushup(int x){siz[x]siz[ls[x]]siz[rs[x]]cnt[x];de[x]cnt[x]?0:1;if(ls[x]) de[x]de[ls[x]];if(rs[x]) de[x]de[rs[x]];return;
}
il int build(int l,int r){if(lr) return 0;int mid(lr)1;int kNew(q[mid],o[mid]);ls[k]build(l,mid-1);rs[k]build(mid1,r);pushup(k);return k;
}
il void pia(int x){if(!x) return;pia(ls[x]);if(cnt[x]){q[num]val[x];o[num]cnt[x];}pia(rs[x]);rub[top]x;return;
}
const double A0.7;
il void check(int x){if(!cnt[x]) return;if(siz[x]*Asiz[ls[x]]||siz[x]*Asiz[rs[x]]||siz[x]de[x]){num0;pia(x);xbuild(1,num);}return;
}
il void ins(int k,int v){if(!k){kNew(v,1);return;}if(vval[k]){cnt[k];pushup(k);return;}else if(vval[k]) ins(ls[k],v);else ins(rs[k],v);pushup(k);check(k);return;
}
il void del(int k,int v){if(!k) return;if(vval[k]){cnt[k]--;pushup(k);return;}if(vval[k]) del(ls[k],v);else del(rs[k],v);pushup(k);check(k);return;
}
il int findrnk(int k,int v){if(!k) return 1;if(vval[k]) return siz[ls[k]]1;else if(vval[k]) return findrnk(ls[k],v);else return siz[ls[k]]cnt[k]findrnk(rs[k],v);
}
il int findnth(int k,int kth){//printf(k%d kth%d\n,k,kth);if(kthsiz[ls[k]]) return findnth(ls[k],kth);else if(kthsiz[ls[k]]cnt[k]) return val[k];else return findnth(rs[k],kth-siz[ls[k]]-cnt[k]);
}
il int findpre(int x){//printf(rnk%d\n,findrnk(r,x));return findnth(r,findrnk(r,x)-1);
}
il int findnxt(int x){return findnth(r,findrnk(r,x1));
}
void print(int k){if(!k) return;printf(k%d val%d ls%d rs%d siz%d cnt%d\n,k,val[k],ls[k],rs[k],siz[k],cnt[k]);print(ls[k]);print(rs[k]);if(kr) putchar(\n);
}
int main(){nread();for(int i1;in;i){int opread(),xread();switch(op){case 1:{ins(r,x);break;}case 2:{del(r,x);break;}case 3:{printf(%d\n,findrnk(r,x));break;}case 4:{printf(%d\n,findnth(r,x));break;}case 5:{printf(%d\n,findpre(x));break;}case 6:{printf(%d\n,findnxt(x));break;}}//print(r);}return 0;
}
/*
9
1 10
1 10
1 15
3 5
*/
