你说的对,但是你理应会动态开点线段树是什么东西。
合并很简单,两棵线段树一块搜,然后逐个节点合并。
分裂的话可以按照 FHQ Treap 的方法。假如我们将前 \(k\) 小和后边分开成 \(x,y\),首先看左子树,如果比 \(k\) 大那右子树给 \(y\),递归左子树,反之左子树给 \(x\),递归右子树。
真没啥好说的,存个板子得了。值得注意的其实是垃圾回收怎么写,以前没写过。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#define int long long
#define lson tree[rt].ls
#define rson tree[rt].rs
using namespace std;
int n,m,cnt,num,buf[200010<<5];
struct node{
int ls,rs,val;
}tree[200010<<5];
int t,rt[200010];
int New(){
return cnt?buf[cnt--]:++t;
}
void del(int x){
buf[++cnt]=x;tree[x].ls=tree[x].rs=tree[x].val=0;
}
void pushup(int rt){
tree[rt].val=tree[lson].val+tree[rson].val;
}
void update(int &rt,int L,int R,int pos,int val){
if(!rt)rt=New();
if(L==R){
tree[rt].val+=val;return;
}
int mid=(L+R)>>1;
if(pos<=mid)update(lson,L,mid,pos,val);
else update(rson,mid+1,R,pos,val);
pushup(rt);
}
int query(int rt,int L,int R,int l,int r){
if(l<=L&&R<=r)return tree[rt].val;
int mid=(L+R)>>1,val=0;
if(l<=mid)val+=query(lson,L,mid,l,r);
if(mid<r)val+=query(rson,mid+1,R,l,r);
return val;
}
int querykth(int rt,int L,int R,int k){
if(L==R)return L;
int mid=(L+R)>>1;
if(tree[lson].val>=k)return querykth(lson,L,mid,k);
else return querykth(rson,mid+1,R,k-tree[lson].val);
}
int merge(int x,int y,int l,int r){
if(!x||!y)return x|y;
if(l==r){
tree[x].val+=tree[y].val;del(y);
return x;
}
int mid=(l+r)>>1;
tree[x].ls=merge(tree[x].ls,tree[y].ls,l,mid);
tree[x].rs=merge(tree[x].rs,tree[y].rs,mid+1,r);
pushup(x);del(y);
return x;
}
void split(int x,int &y,int k){
if(!x)return;
y=New();
int val=tree[tree[x].ls].val;
if(k>val)split(tree[x].rs,tree[y].rs,k-val);
else swap(tree[x].rs,tree[y].rs);
if(k<val)split(tree[x].ls,tree[y].ls,k);
tree[y].val=tree[x].val-k;tree[x].val=k;
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
int x;scanf("%lld",&x);
update(rt[1],1,n,i,x);
}
num=1;
while(m--){
int od,p,x,y;scanf("%lld",&od);
if(od==0){
scanf("%lld%lld%lld",&p,&x,&y);
int k1=query(rt[p],1,n,1,y),k2=query(rt[p],1,n,x,y);
int tmp=0;
split(rt[p],rt[++num],k1-k2);
split(rt[num],tmp,k2);
rt[p]=merge(rt[p],tmp,1,n);
}
else if(od==1){
scanf("%lld%lld",&x,&y);
rt[x]=merge(rt[x],rt[y],1,n);
}
else if(od==2){
scanf("%lld%lld%lld",&p,&x,&y);
update(rt[p],1,n,y,x);
}
else if(od==3){
scanf("%lld%lld%lld",&p,&x,&y);
printf("%lld\n",query(rt[p],1,n,x,y));
}
else{
scanf("%lld%lld",&p,&x);
if(tree[rt[p]].val<x)puts("-1");
else printf("%lld\n",querykth(rt[p],1,n,x));
}
}
return 0;
}
标签:return,val,rs,int,合并,线段,tree,mid,分裂
From: https://www.cnblogs.com/gtm1514/p/17368010.html