题解 P5494 【【模板】线段树分裂】

chenxinyang2006 · 2020-03-28 15:38:43 · 题解

• 闲话

  线段树又有新板子了，这是好的

  但我开始写后，连续爆零了6次，我太菜了

  这次要支持的操作分别是：

  1.线段树分裂

  2.线段树合并

  3.单点加

  4.区间求和

  5.全局kth，也就是线段树内二分

  2 ~ 5 操作都是比较常见的，主要说一下1操作怎么办

• 线段树分裂

  比如你有这颗线段树（节点上写的是区间和），然后你要把 [2,4] 分裂出来

  那么应该有这几个步骤：

  1.找出要分裂的几个子树的根，也就是 9,5,6 节点

  2.删去原线段树上这几个区间的贡献

  3.把新线段树上层的一些节点建好，（指pushup），然后指向分裂出的子树的根

  分裂完是这样的，红色节点表示新建，红色边表示新连：（编号神隐了）

  感觉超级像主席树

  也确实可以学习主席树的做法，用一个数组来存每颗线段树的根

• 合并复杂度分析

  因为线段树合并的复杂度貌似挺玄学的，我来普及一下线段树合并的复杂度分析

  仅当两颗线段树在相同的节点都有值时，合并才需要花费时间，否则可以直接返回有值的一边

  也就是说，合并一次，总节点数量减少1

  一操作会在新线段树上，增加 \log n 个节点

  三操作会增加一条链的节点，也是 \log n 个

  所以总节点数不超过 n + m \log n，合并总复杂度不超过 n + m \log n

code：

#include <cstdio>
#define ll long long
#define ls tree[rt].l
#define rs tree[rt].r
int n,m;
int c = 1;
int T[200005];

int cnt;
struct node{
    ll val;
    int l,r;
}tree[400005 << 5];

int Q(int &x) {if(x == 0) x = ++cnt;}

void pushup(int rt){
    tree[rt].val = tree[ls].val + tree[rs].val;
}

int build(int l,int r){
    int rt = ++cnt;
    if(l == r){
        scanf("%lld",&tree[rt].val);
        return rt;
    }
    int mid = l + r >> 1;
    ls = build(l,mid);
    rs = build(mid + 1,r);
    pushup(rt);
    return rt;
}

int spilt(int Q,int l,int r,int L,int R){
    int rt = ++cnt;
    if(l == L && r == R){
        tree[rt] = tree[Q];
        tree[Q].val = tree[Q].l = tree[Q].r = 0;
        return rt;
    }
    int mid = l + r >> 1;
    if(R <= mid){
        ls = spilt(tree[Q].l,l,mid,L,R);
    }else if(L > mid){
        rs = spilt(tree[Q].r,mid+1,r,L,R);
    }else{
        ls = spilt(tree[Q].l,l,mid,L,mid);
        rs = spilt(tree[Q].r,mid+1,r,mid+1,R);
    }
    pushup(rt);pushup(Q);
    return rt;
}

int merge(int x,int y){
    if(!x) return y;
    if(!y) return x;
    int rt = ++cnt;
    tree[rt].val = tree[x].val + tree[y].val;
    ls = merge(tree[x].l,tree[y].l);
    rs = merge(tree[x].r,tree[y].r);
    return rt;
}

void upload(int rt,int l,int r,int id,int C){
    tree[rt].val += C;
    if(l == r){
        return;
    }
    int mid = l + r >> 1;
    if(id <= mid){
        Q(ls);
        upload(ls,l,mid,id,C);
    }else{
        Q(rs);
        upload(rs,mid+1,r,id,C);
    }
}

ll 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;
    if(R <= mid){
        return query(ls,l,mid,L,R);
    }else if(L > mid){
        return query(rs,mid+1,r,L,R);
    }else{
        return query(ls,l,mid,L,mid) + query(rs,mid+1,r,mid+1,R);
    }
}

int kth(int rt,int l,int r,ll k){
    if(l == r){
        return l;
    }
    int mid = l + r >> 1;
    if(tree[ls].val >= k){
        return kth(ls,l,mid,k);
    }else{
        return kth(rs,mid+1,r,k - tree[ls].val);
    }
}

int main(){
    scanf("%d%d",&n,&m);
    T[1] = build(1,n);
    int opt,p,x,y;
    for(int i = 1;i <= m;i++){
        scanf("%d%d",&opt,&p);
        if(opt == 0){
            scanf("%d%d",&x,&y);
            T[++c] = spilt(T[p],1,n,x,y);
        }else if(opt == 1){
            scanf("%d",&x);
            T[p] = merge(T[p],T[x]);
        }else if(opt == 2){
            scanf("%d%d",&x,&y);
            upload(T[p],1,n,y,x);
        }else if(opt == 3){
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(T[p],1,n,x,y));
        }else{
            ll k;
            scanf("%lld",&k);
            if(query(T[p],1,n,1,n) < k) printf("-1\n");
            else printf("%d\n",kth(T[p],1,n,k));
        }
    }
    return 0;
}

这个线段树分裂的复杂度是比平衡树优秀的，平衡树貌似又少了个优势