線段樹套平衡樹
可能后面還會寫其他型別的樹套樹，這里寫的是線段樹套平衡樹，
這里看一下某谷的模板題https://www.luogu.com.cn/problem/P3380
其實作為蒟蒻，我是沒有看出來樹套樹的，在大佬們的幫助下，我理解了思路，
其實特別好做（才怪，調了一晚上，碼量很難受）
基本上就是splay和線段樹的模版
對于整個的理解，就是線段數上的每個區間，都有一棵與之對應的平衡樹，通過線段樹找到相對應的區間后，在splay上進行操作，
其中需要改動和注意以下幾個地方
1.root的存盤
因為對應的是區間，所以splay中的root，現在改用一個陣列來放每一個區間的根，即root[i]表示線段數上的第i個區間的splay樹的根，
2.查詢區間內第k大的數權值
這個函式我理解了很久，說明一下，
這個我們需要用到二分來實作，我們不能講詢問區間拆成兩個區間，因為合并不了答案啊，所以我們依靠二分來實作，
了解這個函式要先細品seg_rank和Splay_rank這兩個函式，這里求的ans只是區間內比k小的數的總個數，所以當ans=k-1的時候，其實已經求得答案，
但是二分中，判斷條件是ans<k，因此會繼續二分，最后l==r時得到的是第k位數+1，強烈建議手推幾組資料，因為我也說不清楚，淦~~~
3.最后一點，碼量極大（對我這種蒟蒻來說），除錯的時候注意眼睛和心態
其余就沒什么特別注意的，代碼有注釋
//這里打的是線段樹上加平衡樹 //即每一個線段樹的節點上都有一棵splay樹 #include<cstdio> #include<iostream> #include<cctype> #include<cstring> #include<algorithm> using namespace std; inline int read(){ int s=0;bool flag=true;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')flag=false;ch=getchar();} while(isdigit(ch)){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();} return flag?s:-s; } inline void print_ans(int x){ if(x<0)putchar('-'),x=-x; if(x>9)print_ans(x/10); putchar(x%10+'0'); } inline void print(int x){print_ans(x),puts("");} #define Max(a,b) a=max(a,b) #define Min(a,b) a=min(a,b) const int N=4e6+5; const int inf=2147483647; int MAX,n,m,ans,w[N]; //----------上面是基礎資料，輸入優化等亂七八糟的東西 int tot,root[N]; struct Splay_tree{int son[2],val,size,cnt,father;}T[N]; #define ls(x) T[x].son[0] #define rs(x) T[x].son[1] #define val(x) T[x].val #define sze(x) T[x].size #define cnt(x) T[x].cnt #define fa(x) T[x].father //不為別的，看小括號比看中括號爽 inline void Splay_update(int x){ sze(x)=(ls(x)?sze(ls(x)):0)+(rs(x)?sze(rs(x)):0)+cnt(x); } inline void Splay_clear(int x){ls(x)=rs(x)=fa(x)=cnt(x)=sze(x)=val(x)=0;} inline void Splay_rotate(int x){ int y=fa(x),z=fa(y); int jud_x=(rs(y)==x),jud_y=(rs(z)==y); int w=T[x].son[jud_x^1]; T[y].son[jud_x]=w;if(w) fa(w)=y; if(z)T[z].son[jud_y]=x;fa(x)=z; T[x].son[jud_x^1]=y;fa(y)=x; Splay_update(y),Splay_update(x); } inline void Splay_splay(int id,int x,int goal=0){ while(fa(x)!=goal){ int y=fa(x),z=fa(y); if(z!=goal)(ls(z)==y)^(ls(y)==x)?Splay_rotate(x):Splay_rotate(y); Splay_rotate(x); } if(!goal) root[id]=x; } inline int Splay_find(int id,int x){ int u=root[id]; while(x){ if(val(u)==x){Splay_splay(id,u);return u;} u=T[u].son[x>val(u)]; } return 0; } inline void Splay_insert(int id,int x){ int u=root[id]; if(!root[id]){ root[id]=u=++tot; ls(u)=rs(u)=0,val(u)=x,sze(u)=cnt(u)=1,fa(u)=0; return ; } int pre=0; while(true){ if(val(u)==x){cnt(u)++;Splay_update(pre);break;} pre=u,u=T[u].son[x>val(u)]; if(!u){ u=++tot; T[pre].son[x>val(pre)]=u; ls(u)=rs(u)=0,val(u)=x,sze(u)=cnt(u)=1,fa(u)=pre; Splay_update(pre);break; } } Splay_splay(id,u); } inline int Splay_rank(int id,int k){ //以線段樹上的id節點為根的splay樹上尋找權值k的排名 int x=root[id],sum=0; while(x){ if(val(x)==k) return sum+(ls(x) ? sze(ls(x)) : 0); else if(val(x)<k){ sum+=(ls(x) ? sze(ls(x)) : 0)+cnt(x); x=rs(x); } else x=ls(x); } return sum; } inline int Splay_Getpre(int id,int x){ int u=root[id]; while(u){ if(val(u)<x){Max(ans,val(u));u=rs(u);} else u=ls(u); } return ans; } inline int Splay_Getsuf(int id,int x){ int u=root[id]; while(u){ if(val(u)>x){Min(ans,val(u));u=ls(u);} else u=rs(u); } return ans; } inline int Splay_pre(int id){int x=ls(root[id]);while(rs(x))x=rs(x);return x;}//根節點的前驅，用于delete操作 inline void Splay_delete(int id,int x){ int u=Splay_find(id,x); if(cnt(u)>1){cnt(u)--;Splay_update(u);return ;} if(!ls(u) && !rs(u)){Splay_clear(root[id]);root[id]=0;return ;} if(!ls(u)){root[id]=rs(u),fa(rs(u))=0;return ;} if(!rs(u)){root[id]=ls(u),fa(ls(u))=0;return ;} int Pre=Splay_pre(id),Father=root[id]; Splay_splay(id,Pre,0); rs(root[id])=rs(Father); fa(rs(Father))=root[id]; Splay_clear(Father),Splay_update(root[id]); } //----------上面是關于splay的函式，下面是關于segment tree的函式 #define lc (id<<1) #define rc (id<<1|1) #define mid ((l+r)>>1) inline void seg_insert(int id,int l,int r,int pos,int k){ Splay_insert(id,k); if(l==r) return ; if(pos<=mid) seg_insert(lc,l,mid,pos,k); else seg_insert(rc,mid+1,r,pos,k); } inline void seg_rank(int id,int l,int r,int L,int R,int k){ //在整棵線段樹上找到該splay的區間 if(l==L&&r==R){ans+=Splay_rank(id,k);return ;} if(R<=mid) seg_rank(lc,l,mid,L,R,k); else if(L>mid) seg_rank(rc,mid+1,r,L,R,k); else seg_rank(lc,l,mid,L,mid,k),seg_rank(rc,mid+1,r,mid+1,R,k); } inline void seg_modify(int id,int l,int r,int pos,int k){ //單點修改權值，splay同時更新 Splay_delete(id,w[pos]);Splay_insert(id,k); if(l==r){w[pos]=k;return ;} if(pos<=mid) seg_modify(lc,l,mid,pos,k); else seg_modify(rc,mid+1,r,pos,k); } inline void seg_pre(int id,int l,int r,int L,int R,int k){ //查詢權值為k的前驅 if(l==L&&r==R){Max(ans,Splay_Getpre(id,k));return ;} if(R<=mid) seg_pre(lc,l,mid,L,R,k); else if(L>mid) seg_pre(rc,mid+1,r,L,R,k); else seg_pre(lc,l,mid,L,mid,k),seg_pre(rc,mid+1,r,mid+1,R,k); } inline void seg_suf(int id,int l,int r,int L,int R,int k){ //查詢權值為k的后驅 if(l==L&&r==R){Min(ans,Splay_Getsuf(id,k));return ;} if(R<=mid) seg_suf(lc,l,mid,L,R,k); else if(L>mid) seg_suf(rc,mid+1,r,L,R,k); else seg_suf(lc,l,mid,L,mid,k),seg_suf(rc,mid+1,r,mid+1,R,k); } //----------其他情況的函式 inline int search_value(int L,int R,int kth){ //尋求L，R區間第k大的數，即區間第k大 int l=0,r=MAX+1,m; while(l<r){ m=(l+r)>>1;ans=0; seg_rank(1,1,n,L,R,m); if(ans<kth) l=m+1; else r=m; } return l-1; } signed main(){ n=read(),m=read();MAX=-inf; for(int i=1;i<=n;i++){ w[i]=read(); seg_insert(1,1,n,i,w[i]); Max(MAX,w[i]); } while(m--){ int opt=read(); switch(opt){ case 1:{//區間查k值的排名 int L=read(),R=read(),k=read();ans=0; seg_rank(1,1,n,L,R,k); print(ans+1); break; } case 2:{//區間查第k大 int L=read(),R=read(),kth=read(); print(search_value(L,R,kth)); break; } case 3:{//單點修改 int pos=read(),k=read(); seg_modify(1,1,n,pos,k); break; } case 4:{//k的前驅 int L=read(),R=read(),k=read();ans=-inf; seg_pre(1,1,n,L,R,k); print(ans); break; } case 5:{//k的后驅 int L=read(),R=read(),k=read();ans=inf; seg_suf(1,1,n,L,R,k); print(ans); break; } } } return 0; }
特別鳴謝這篇題解及其作者
https://www.luogu.com.cn/blog/Qiu/qian-tan-shu-tao-shu-xian-duan-shu-tao-ping-heng-shu-post
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/38514.html
標籤：C++
上一篇：測量C++程式運行時間
下一篇：螺旋矩陣問題