P5494

发表于 分类于
【模板】线段树分裂

【模板】线段树分裂

线段树分裂，如其名，是将线段树上代表某一区间的所有子区间分裂出去，并与新建的几个节点组成新的线段树。

因为是动态开点线段树，这一操作变得容易完成。

因为找到线段树上被某一区间完全覆盖的信息是容易的，未被完全覆盖的子区间只要复制一个空的版本送给新的线段树即可。

容易想到这个单次分裂的复杂度是 $O(\log n)$ 的。

剩下几个操作比较 Trivial，略了。。。

合并的复杂度 $O((n+m)\log n)$，挺显然的。。。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x) {write(x);putchar(10);}

const ll N=2e5,M=2e7;

ll n,m,cnt,cntrt;
ll rt[N+5];

struct Sgt{
  ll ls,rs,dat;
  #define ls(x) tree[x].ls
  #define rs(x) tree[x].rs
  #define dat(x) tree[x].dat
}tree[M+5];

inline void Pushup(ll p) {
  if(ls(p)&&!rs(p)) dat(p)=dat(ls(p));
  else if(!ls(p)&&rs(p)) dat(p)=dat(rs(p));
  else dat(p)=dat(ls(p))+dat(rs(p));
}

inline void Add(ll p,ll lp,ll rp,ll x,ll k) {
  if(lp==rp) {dat(p)+=k;return;}
  ll mid=(lp+rp)>>1;
  if(x<=mid) {if(!ls(p)) {cnt++;ls(p)=cnt;}Add(ls(p),lp,mid,x,k);}
  else {if(!rs(p)) {cnt++;rs(p)=cnt;}Add(rs(p),mid+1,rp,x,k);}
  Pushup(p);
}

inline void Split(ll &x,ll &y,ll lp,ll rp,ll l,ll r) {
  if(!x) return;
  if(lp>=l&&rp<=r) {y=x;x=0;return;}
  if(!y) {cnt++;y=cnt;}ll mid=(lp+rp)>>1;
  if(l<=mid) Split(ls(x),ls(y),lp,mid,l,r);
  if(r>mid) Split(rs(x),rs(y),mid+1,rp,l,r);
  Pushup(x);Pushup(y);
}

inline ll Merge(ll x,ll y,ll lp,ll rp) {
  if(!x||!y) return x|y;
  if(lp==rp) {dat(x)=dat(x)+dat(y);return x;}
  ll mid=(lp+rp)>>1;
  ls(x)=Merge(ls(x),ls(y),lp,mid);
  rs(x)=Merge(rs(x),rs(y),mid+1,rp);
  Pushup(x);return x;
}

inline ll Ask(ll p,ll lp,ll rp,ll l,ll r) {
  if(lp>=l&&rp<=r) return dat(p);
  ll mid=(lp+rp)>>1,tmpl=0,tmpr=0;
  if(l<=mid&&ls(p)) tmpl=Ask(ls(p),lp,mid,l,r);
  if(r>mid&&rs(p)) tmpr=Ask(rs(p),mid+1,rp,l,r);
  return tmpl+tmpr;
}

inline ll Kth(ll p,ll lp,ll rp,ll k) {
  if(lp==rp) return lp;ll mid=(lp+rp)>>1;
  if(k>dat(ls(p))) {k-=dat(ls(p));return Kth(rs(p),mid+1,rp,k);}
  else return Kth(ls(p),lp,mid,k);
}

int main() {

  n=read();m=read();cntrt=1;cnt=1;rt[1]=1;
  for(ll i=1;i<=n;i++) {
    ll x;x=read();Add(rt[1],1,n,i,x);
  }

  while(m--) {
    ll op=read();
    if(op==0) {
      ll p,x,y;p=read();x=read();y=read();
      cntrt++;Split(rt[p],rt[cntrt],1,n,x,y);
    }
    if(op==1) {
      ll p,t;p=read();t=read();
      rt[p]=Merge(rt[p],rt[t],1,n);rt[t]=0;
    }
    if(op==2) {
      ll p,x,q;p=read();x=read();q=read();
      Add(rt[p],1,n,q,x);
    }
    if(op==3) {
      ll p,x,y;p=read();x=read();y=read();
      writeln(Ask(rt[p],1,n,x,y));
    }
    if(op==4) {
      ll p,k;p=read();k=read();
      if(k>dat(rt[p])) {writeln(-1);continue;}
      else writeln(Kth(rt[p],1,n,k));
    }
  }

  return 0;
}