樹套樹學習筆記
吐槽一下：
其實感覺并沒有什麼好寫的，但好歹是個資料結構，不寫不好将題分類啊！
而且目前隻做了線段樹套平衡樹的題目，其它的就以後慢慢填坑吧！ 其實就隻打了洛谷樹套樹模闆，QAQ部落客還是太弱了。
話說帶修改主席樹算不算樹狀數組套線段樹，部落客太弱了，請各位大佬解惑。
1.線段樹套平衡樹：
例題：洛谷P3380 【模闆】二逼平衡樹（樹套樹）
隻有第二個操作值得一說吧，不過也隻要二分數的大小，套用1操作，看排名是否等于k了。
1 // luogu-judger-enable-o2
2 #include<bits/stdc++.h>
3 #define re register
4 using namespace std;
5 const int N=50006,M=1600006,inf=2147483647;
6 int n,m,t,t1,t2,t3,cnt=0,a[N],f[M],rnd[M],rt[N<<2],son[M][2],w[M],num[M],siz[M];
7 inline int read(){
8 int T=0,F=1; char ch=getchar();
9 while(ch<'0'||ch>'9'){if(ch=='-') F=-1; ch=getchar();}
10 while(ch>='0'&&ch<='9') T=(T<<3)+(T<<1)+(ch-48),ch=getchar();
11 return F*T;
12 }
13 inline void pushup(int x){siz[x]=siz[son[x][0]]+siz[son[x][1]]+num[x]; }
14 void rotate(int &u,int d)
15 {
16 int p=son[u][d^1]; son[u][d^1]=son[p][d]; son[p][d]=u; pushup(u); pushup(p); u=p;
17 }
18 int cmp(int u,int x)
19 {
20 if(w[u]==x) return -1;
21 return w[u]<x;
22 }
23 int ins(int &u,int x)
24 {
25 if(!u){u=++cnt; w[u]=x; rnd[u]=rand()%inf; siz[u]=1,num[u]=1; return cnt;}
26 else
27 {
28 ++siz[u];
29 int d=cmp(u,x);
30 if(d==-1){++num[u]; return u;}
31 int oo=ins(son[u][d],x);
32 if(rnd[u]<rnd[son[u][d]]) rotate(u,d^1);
33 return oo;
34 }
35 }
36 void del(int &u,int x)
37 {
38 int d=cmp(u,x);
39 if(d==-1)
40 {
41 if(num[u]>1){--num[u],--siz[u]; return;}
42 if(!(son[u][0]*son[u][1])){u=son[u][0]+son[u][1]; return;}
43 else
44 {
45 int d2=(rnd[son[u][0]]>rnd[son[u][1]]?1:0);
46 rotate(u,d2); del(son[u][d2],x);
47 }
48 }
49 else del(son[u][d],x);
50 pushup(u);
51 }
52 int pre(int u,int x)
53 {
54 int d=cmp(u,x);
55 if(!u) return -inf;
56 if(d==-1) return pre(son[u][0],x);
57 if(d) return max(pre(son[u][1],x),w[u]);
58 return pre(son[u][0],x);
59 }
60 int nxt(int u,int x)
61 {
62 int d=cmp(u,x);
63 if(!u) return inf;
64 if(d==-1) return nxt(son[u][1],x);
65 if(!d) return min(nxt(son[u][0],x),w[u]);
66 return nxt(son[u][1],x);
67 }
68 int rnk(int x,int y){
69 int sum=0,z=rt[y];
70 while(z){
71 if(w[z]==x) return sum+siz[son[z][0]];
72 if(w[z]>x) z=son[z][0];
73 else sum+=siz[son[z][0]]+num[z],z=son[z][1];
74 }
75 return sum;
76 }
77 void build(int l,int r,int x){
78 for(int i=l;i<=r;++i) ins(rt[x],a[i]);
79 if(l==r) return;
80 int mid=((l+r)>>1);
81 build(l,mid,x<<1),build(mid+1,r,x<<1|1);
82 }
83 int query_rank(int l,int r,int p,int q,int x,int k){
84 if(p<=l&&r<=q) return rnk(k,x);
85 int mid=((l+r)>>1);
86 if(p>mid) return query_rank(mid+1,r,p,q,x<<1|1,k);
87 if(q<=mid) return query_rank(l,mid,p,q,x<<1,k);
88 return query_rank(l,mid,p,q,x<<1,k)+query_rank(mid+1,r,p,q,x<<1|1,k);
89 }
90 int query_num(int l,int r,int p,int q,int x){
91 if(l==r) return l;
92 int mid=((l+r+1)>>1);
93 if(query_rank(1,n,p,q,1,mid)+1>x) return query_num(l,mid-1,p,q,x);
94 else return query_num(mid,r,p,q,x);
95 }
96 void query_update(int l,int r,int p,int x,int y){
97 del(rt[x],a[p]); ins(rt[x],y);
98 int mid=((l+r)>>1);
99 if(l==r){a[p]=y; return;}
100 if(p<=mid) query_update(l,mid,p,x<<1,y);
101 else query_update(mid+1,r,p,x<<1|1,y);
102 }
103 int query_pre(int l,int r,int p,int q,int x,int y){
104 if(p<=l&&r<=q){t1=ins(rt[x],y),t2=pre(rt[x],y),del(rt[x],y); return t2;}
105 int mid=((l+r)>>1);
106 if(q<=mid) return query_pre(l,mid,p,q,x<<1,y);
107 if(p>mid) return query_pre(mid+1,r,p,q,x<<1|1,y);
108 return max(query_pre(l,mid,p,q,x<<1,y),query_pre(mid+1,r,p,q,x<<1|1,y));
109 }
110 int query_nxt(int l,int r,int p,int q,int x,int y){
111 if(p<=l&&r<=q){t1=ins(rt[x],y),t2=nxt(rt[x],y),del(rt[x],y); return t2;}
112 int mid=((l+r)>>1);
113 if(q<=mid) return query_nxt(l,mid,p,q,x<<1,y);
114 if(p>mid) return query_nxt(mid+1,r,p,q,x<<1|1,y);
115 return min(query_nxt(l,mid,p,q,x<<1,y),query_nxt(mid+1,r,p,q,x<<1|1,y));
116 }
117 int main(){
118 srand(time(NULL));
119 n=read(),m=read();
120 for(re int i=1;i<=n;++i) a[i]=read();
121 build(1,n,1);
122 for(re int i=1;i<=m;++i){
123 t=read(),t1=read(),t2=read();
124 switch(t){
125 case 1:t3=read();printf("%d\n",query_rank(1,n,t1,t2,1,t3)+1);break;
126 case 2:t3=read();printf("%d\n",query_num(0,1e8,t1,t2,t3));break;
127 case 3:query_update(1,n,t1,1,t2);break;
128 case 4:t3=read();printf("%d\n",query_pre(1,n,t1,t2,1,t3));break;
129 case 5:t3=read();printf("%d\n",query_nxt(1,n,t1,t2,1,t3));break;
130 }
131 }
132 return 0;
133 } 轉載于:https://www.cnblogs.com/ljk123-de-bo-ke/p/11288144.html