抛弃理性，保持随机——Leafy Treap 瞎写
线段树的标记下传与平衡树不大一样，这也就是Leafy Treap 出现的意义
正如其名，这里给出了一个leafy 化的 FHQ_Traep 的实现
feature:
- 复杂度同
FHQ - 可以简单可持久化
- 可以避免在标记维护时的讨论，减少常数
- 维护序列码量小于市面上大部分
Leafy平衡树，如WBLT(单旋)，Leafy_Splay，比cmd的码量多一点
weak points:
- 常数大于普通
FHQ，一般多个几十毫秒 - 较难以在有重复的权值树中删除一个元素
- 双倍空间，节点报废严重
下面来重点介绍一下几个关键的操作
Pushup/Pushdown
和线段树同理，但是注意的是，叶子不能进行这两种操作
Split
在分裂的过程中，如果树裂成了两半，那一定有一个节点会消失
不难看出，在对于一个不是叶子节点的节点在分裂之后有一边空了出来，那就可以用另一边的节点去代替它，然后把这个节点丢进垃圾桶
下面是按 size 分裂的代码
void split(int now,int &x,int &y,int k){
if(!now) return x=y=0,void();
pushdown(now);
if(siz[l(now)]>=k)
y=now,split(l(now),x,l(y),k),
(!l(now)&&!leaf[now])?rb.push(now),now=y=r(now):1;
else
x=now,split(r(now),r(x),y,k-siz[l(now)]),
(!r(now)&&!leaf[now])?rb.push(now),now=x=l(now):1;
pushup(now);
}
Merge
合并的过程中，如果一个叶子节点这个时候要作为根了，就新建一个节点，然后把叶子设为这个点的一个儿子，然后去合并另一个儿子
值得注意的是，我一开始的实现忽略了一点，如果直接给新建的节点赋上一个随机权值，这样很明显是不符合小根堆的要求的，解决方法就是将新建节点的权值赋为原来节点的权值，然后再给原来的节点倾定一个大于原来的权值
事实上，原来的假做法成功地通过了除普通平衡树外的所有题目，而且通过了loj上的普通平衡树，洛谷上会 T 一个点，本地测试加不加这个优化会使有两秒左右的区别
const int lim=2e9;
mt19937 raddd(time(0));
auto radd(int down){
int len=lim-down;
return raddd()%len+down;
}
int merge(int a,int b){
if(!a||!b) return a+b;
int p;
if(rad[a]<rad[b]){
if(leaf[a]){
l(p=nid())=a;
swap(rad[a],rad[p]);
rad[a]=radd(rad[p]);
}else p=a;
r(p)=merge(r(p),b);
}
else {
if(leaf[b]){
r(p=nid())=b;
swap(rad[b],rad[p]);
rad[b]=radd(rad[p]);
}else p=b;
l(p)=merge(a,l(p));
}
return pushup(p),p;
}
Build
这里参考OI-wiki的第二种建树方法，模仿线段树，然后随机权值，可以证明这是对的
void build(int &now,int l,int r){
now=nid();
if(l==r) return val[now]=a[l],siz[now]=leaf[now]=1,void();
int mid(l+r>>1);
build(l(now),l,mid),build(r(now),mid+1,r);
pushup(now);
}
其他的操作就同普通的FHQ了
给出文艺平衡树的代码和线段树1的代码，删去了缺省源，可以去我博客里面找
const int N=2e5+10,lim=2e9;
mt19937 raddd(time(0));
auto radd(int down){
int len=lim-down;
return raddd()%len+down;
}
int a[N],q,n;
struct Leafy{
int val[N],son[2][N],rad[N],tag[N],siz[N],idx,root,leaf[N];
queue<int> rb;
int nid(){
int p;
if(rb.size()) p=rb.front(),rb.pop();
else p=++idx;
val[p]=siz[p]=son[0][p]=son[1][p]=val[p]=leaf[p]=0,rad[p]=raddd();
return p;
}
void pushup(int now){if(!leaf[now]) siz[now]=siz[l(now)]+siz[r(now)];}
void pushdown(int now){
if(!leaf[now]&&tag[now]){
tag[l(now)]^=1,tag[r(now)]^=1,tag[now]^=1;
swap(l(now),r(now));
}
}
void build(int &now,int l,int r){
now=nid();
if(l==r) return val[now]=a[l],siz[now]=leaf[now]=1,void();
int mid(l+r>>1);
build(l(now),l,mid),build(r(now),mid+1,r);
pushup(now);
}
void split(int now,int &x,int &y,int k){
if(!now) return x=y=0,void();
pushdown(now);
if(siz[l(now)]>=k)
y=now,split(l(now),x,l(y),k),
(!l(now)&&!leaf[now])?rb.push(now),now=y=r(now):1;
else
x=now,split(r(now),r(x),y,k-siz[l(now)]),
(!r(now)&&!leaf[now])?rb.push(now),now=x=l(now):1;
pushup(now);
}
int merge(int a,int b){
if(!a||!b) return a+b;
int p;
pushdown(a),pushdown(b);
if(rad[a]<rad[b]){
if(leaf[a]){
l(p=nid())=a;
swap(rad[a],rad[p]);
rad[a]=radd(rad[p]);
}else p=a;
r(p)=merge(r(p),b);
}
else {
if(leaf[b]){
r(p=nid())=b;
swap(rad[b],rad[p]);
rad[b]=radd(rad[p]);
}else p=b;
l(p)=merge(a,l(p));
}
return pushup(p),p;
}
void turnover(int l,int r){
int a,b,c;
split(root,b,c,r),split(b,a,b,l-1);
tag[b]^=1;
root=merge(a,merge(b,c));
}
void dfs(int now){
if(!now) return ;
if(val[now]) cout << val[now] <<' ';
pushdown(now);
dfs(l(now)),dfs(r(now));
}
}fhq;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
n=rd(),q=rd();
iota(a+1,a+n+1,1);
fhq.build(fhq.root,1,n);
while(q--){
int l=rd(),r=rd();
fhq.turnover(l,r);
}
fhq.dfs(fhq.root);
return 0;
}
const int N=2e5+10,lim=2e9;
mt19937 raddd(19937);
auto radd(int down){
int len=lim-down;
return raddd()%len+down;
}
ll a[N];
int n,q;
struct FHQ{
ll data[N],tag[N];
int siz[N],son[2][N],rad[N],idx,leaf[N],root;
queue<int> rb;
int nid(){
int p;
if(rb.size()) p=rb.front(),rb.pop();
else p=++idx;
data[p]=siz[p]=tag[p]=son[0][p]=son[1][p]=0;
rad[p]=raddd();
return p;
}
void pushup(int now){
if(leaf[now]) return ;
data[now]=data[l(now)]+data[r(now)],
siz[now]=siz[l(now)]+siz[r(now)];
}
void pushdown(int now){
if(tag[now]&&!leaf[now]){
tag[l(now)]+=tag[now],
tag[r(now)]+=tag[now];
data[l(now)]+=tag[now]*siz[l(now)],
data[r(now)]+=tag[now]*siz[r(now)];
tag[now]=0;
}
}
void build(int &now,int l,int r){
now=nid();
if(l==r)return siz[now]=1,data[now]=a[l],leaf[now]=1,void();
int mid(l+r>>1);
build(l(now),l,mid),build(r(now),mid+1,r);
pushup(now);
}
void split(int now,int &x,int &y,int k){
pushdown(now);
if(!now) return x=y=0,void();
if(siz[l(now)]>=k){
y=now,split(l(now),x,l(y),k);
if(!l(now)&&!leaf[now]) rb.push(now),y=r(now);
}
else {
x=now,split(r(now),r(x),y,k-siz[l(now)]);
if(!r(now)&&!leaf[now]) rb.push(now),x=l(now);
}
pushup(now);
}
int merge(int a,int b){
if(!a||!b) return a+b;
int p;
pushdown(a),pushdown(b);
if(rad[a]<rad[b]){
if(leaf[a]){
l(p=nid())=a;
swap(rad[a],rad[p]);
rad[a]=radd(rad[p]);
}else p=a;
r(p)=merge(r(p),b);
}
else {
if(leaf[b]){
r(p=nid())=b;
swap(rad[b],rad[p]);
rad[b]=radd(rad[p]);
}else p=b;
l(p)=merge(a,l(p));
}
return pushup(p),p;
}
void modify(int l,int r,ll x){
int a,b,c;
split(root,b,c,r);
split(b,a,b,l-1);
tag[b]+=x,data[b]+=siz[b]*x;
root=merge(merge(a,b),c);
}
ll query(int l,int r){
int a=0,b=0,c=0;
ll ans;
split(root,b,c,r);
split(b,a,b,l-1);
ans=data[b];
root=merge(merge(a,b),c);
return ans;
}
}fhq;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
n=rd(),q=rd();
fp(i,1,n) a[i]=rd();
fhq.build(fhq.root,1,n);
while(q--){
int op=rd(),l=rd(),r=rd(),x;
if(op==1)
fhq.modify(l,r,rd());
else cout << fhq.query(l,r) << '\n';
}
return 0;
}
权值操作
按权值分裂没有什么好说的，和普通分裂一样
但是这里有一个问题，由于Leafy 的特性，使得原来的删除策略失效了
这里只能给出一种退而求其次的做法，对每个数存一个pair，第二关键字为不重复的一个值，删除的时候，就从分裂好的树内找出最小值，然后再出来，再将其他树合并
删除权值就不要leafy了，真的常数大，加强版这份代码跑了大概 23s
const int N=2e6+2e5+10,lim=2e9;
int n,ind,q,ans;
mt19937 raddd(time(0));
auto radd(int down){
int len=lim-down;
return raddd()%len+down;
}
struct FHQ{
pii data[N];
int son[2][N];
int rad[N];
int siz[N],leaf[N],idx,root;
queue<int> rb;
void pushup(int now){
if(!leaf[now])
data[now]=max(data[r(now)],data[l(now)]),
siz[now]=siz[l(now)]+siz[r(now)];
}
int nid(){
int p;
if(rb.size())p=rb.front(),rb.pop();
else p=++idx;
data[p]=mpr(0,0),siz[p]=leaf[p]=l(p)=r(p)=0,rad[p]=raddd();
return p;
}
void split(int now,int &x,int &y,pii k){
if(!now) return x=y=0,void();
pii v=(leaf[now])?data[now]:data[l(now)];
if(v<=k)
x=now,split(r(now),r(now),y,k),
(!leaf[now]&&!r(now))?rb.push(now),x=now=l(now):1;
else
y=now,split(l(now),x,l(now),k),
(!leaf[now]&&!l(now))?rb.push(now),y=now=r(now):1;
pushup(now);
}
int merge(int a,int b){
if(!a||!b) return a+b;
int p;
if(rad[a]<rad[b]){
if(leaf[a]){
l(p=nid())=a;
swap(rad[a],rad[p]);
rad[a]=radd(rad[p]);
}else p=a;
r(p)=merge(r(p),b);
}
else {
if(leaf[b]){
r(p=nid())=b;
swap(rad[b],rad[p]);
rad[b]=radd(rad[p]);
}else p=b;
l(p)=merge(a,l(p));
}
return pushup(p),p;
}
int kth(int rt,int k){
int now=rt;
while(!leaf[now]){
if(siz[l(now)]>=k) now=l(now);
else k-=siz[l(now)],now=r(now);
}return now;
}
void insert(int x){
int p=nid(),a,b;
data[p]=mpr(x,++ind),leaf[p]=1,siz[p]=1;
split(root,a,b,data[p]);
root=merge(merge(a,p),b);
}
void del(int x){
pii y1=mpr(x,0),y2=mpr(x,inf);
int a,b,c,d;
split(root,a,b,y1),split(b,b,d,y2);
pii p=data[kth(b,1)];
split(b,b,c,p);
rb.push(b);
root=merge(merge(a,c),d);
}
int irank(int x){
int a,b,ans;
split(root,a,b,mpr(x,0));
ans=siz[a]+1;
root=merge(a,b);
return ans;
}
int pre(int x){
int a,b,ans;pii p(x,0);
split(root,a,b,p);
ans=data[kth(a,siz[a])].fir;
root=merge(a,b);
return ans;
}
int suf(int x){
int a,b,ans;pii p(x,inf);
split(root,a,b,p);
ans=data[kth(b,1)].fir;
root=merge(a,b);
return ans;
}
}fhq;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
n=rd();
q=rd();
fp(i,1,n)
fhq.insert(rd());
ll sum=0;
while(q--){
int op=rd(),x=rd();
x^=ans;
if(op==1) fhq.insert(x);
if(op==2) fhq.del(x);
if(op==3) ans=fhq.irank(x);
if(op==4) ans=fhq.data[fhq.kth(fhq.root,x)].fir;
if(op==5) ans=fhq.pre(x);
if(op==6) ans=fhq.suf(x);
if(op!=2&&op!=1) sum^=ans;
}
cout << sum << '\n';
return 0;
}