线段树合并/分裂

你说的对，但是你理应会动态开点线段树是什么东西。

合并很简单，两棵线段树一块搜，然后逐个节点合并。

分裂的话可以按照 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;
}