算法筆記（2）FHQtreap
原發(fā)布于我的個人博客
前言
FHQtreap絕對是平衡樹里最好寫，最實用的，他幾乎能做所有splay或其它平衡樹能做的事，還能可持久化！
這篇文章將會介紹FHQtreap的基本操作和維護區(qū)間的操作，并附上例題。
基本操作
FHQtreap的基本操作只有兩個，分裂和合并。
有些讀者可能會問，分裂和合并和平衡樹有什么關(guān)系？
想想一下，如果要插入一個數(shù)3，在正常的平衡樹里應該是找到3的位置，然后讓他的\(cnt\)值\(+1\)，在FHQtreap里可不是這樣，所謂插入，就是把平衡樹按照3分裂成兩棵樹，然后把3這個數(shù)的節(jié)點合并進去。
刪除呢？直接按照3分裂，然后在左子樹里把3“摳出去”，再合并。
其它操作也大同小異，你會發(fā)現(xiàn)，大部分平衡樹的操作，都可以用分裂和合并來表示，這就是FHQtreap的特點，這種思想被稱為“函數(shù)式編程”。
節(jié)點結(jié)構(gòu)
FHQtreap每個節(jié)點要保存的信息有權(quán)值（這個數(shù)），優(yōu)先級（隨機數(shù))，子樹大小，左右子樹的編號。
struct node{//節(jié)點結(jié)構(gòu)體
int x,rnd,size;
int ls,rs;
}tr[N];
注意：FHQtreap不需要存儲\(cnt\)，它把權(quán)值相同的節(jié)點看成多個節(jié)點 。
pushup操作
也叫maintain 操作，調(diào)整子樹大小。
inline void pushup(int x){
tr[x].size=tr[tr[x].ls].size+tr[tr[x].rs].size+1;
}
分裂
FHQtreap的分裂操作有兩種，一種是通過權(quán)值分裂（小于等于\(x\)的分到左子樹，大于\(x\)的分到右子樹），一種是通過大小分裂（前\(size\)個數(shù)分到左子樹，剩下的分到右子樹）
如圖，將一棵樹按7分裂成兩棵樹。
分裂后，就產(chǎn)生了\(\{x|x\le 7\}\)和\(\{x|x> 7\}\)兩顆樹。
按權(quán)值分裂代碼
void split(int u,int &x,int &y,int val){//x和y用引用形式，是要分裂成的兩棵樹
if(!u){
x=y=0;//遞歸終止條件
return;
}
if(tr[u].x<=val) x=u,split(tr[x].rs,tr[x].rs,y,val);//當前權(quán)值小于等與要分裂的值，遞歸分裂右子樹
else y=u,split(tr[y].ls,x,tr[y].ls,val);//遞歸分裂左子樹
pushup(u);//最后別忘了pushup一下。
}
FHQtreap也可以按照大小分裂，將在區(qū)間操作的部分提到，這里給出代碼。
按大小分裂代碼
void split(int u,int &x,int &y,int size){
if(!u){
x=y=0;
return;
}
if(tr[tr[u].ls].size<size) x=u,split(tr[u].rs,tr[u].rs,y,size-tr[tr[u].ls].size-1);//注意，這里傳的值要減去左子樹大小
else y=u,split(tr[u].ls,x,tr[y].ls,size);
pushup(u);
}
合并
FHQtreap的合并操作很像是線段樹合并，是一種啟發(fā)式合并。
如圖，合并操作可以有多種合并方式，這取決于每個節(jié)點所附帶的優(yōu)先級（隨機值），使這顆樹的優(yōu)先級符合\(heap\)性質(zhì)（感興趣的可以了解一下treap的平衡方式，這里不細講了）
合并操作代碼
int merge(int x,int y){
if(!x||!y) return x+y;
//這個x+y實際上就是返回x和y中不為空的一個
if(tr[x].rnd<tr[y].rnd){//通過優(yōu)先級調(diào)整
tr[x].rs=merge(tr[x].rs,y);//啟發(fā)式合并
pushup(x);//更新節(jié)點信息
return x;//合并后的節(jié)點就變成了x
}
else{
tr[y].ls=merge(x,tr[y].ls);
pushup(y);
return y;
}
}
其它操作
學會了基本的分裂和合并操作，我們就可以做到插入，刪除這些操作了。
新建節(jié)點
這個新建節(jié)點的操作大概是本人獨有的，大部分oier都不會這么寫，但是這么寫的好處就是簡短清晰（只需兩行）。
int newNode(int x){
tr[++tot]={x,rand(),1,0,0};//結(jié)構(gòu)體的賦值方法，分別傳入權(quán)值、優(yōu)先級、大小和左右子樹編號（0）
return tot;//返回新建節(jié)點的編號
}
插入
如圖，若插入一個\(x\)，先按\(x\)分裂，然后新建一個節(jié)點\(x\)合并進去。
插入代碼
void insert(int x){
int l,r;
split(root,l,r,x);
root=merge(merge(l,newNode(x)),r);
}
刪除
刪除操作比較復雜，如圖，先按\(x\)分裂成兩顆子樹（樹1和樹2）。
再按\(x-1\)分裂成兩棵子樹（樹3和樹4）。
此時樹4的根就是我們要找的\(x\)，把樹4的根挑出去，然后合并樹342即可。
刪除代碼
void del(int x){
int l,r,xx,yy;//分別代表數(shù)1234
split(root,l,r,x);//按x分裂
split(l,xx,yy,x-1);//按x-1分裂
yy=merge(tr[yy].ls,tr[yy].rs);//把樹4的根挑出去
root=merge(merge(xx,yy),r);//合并
}
查詢一個數(shù)的排名
排名的定義是"小于這個數(shù)的個數(shù)\(+1\)"。
按照定義，按\(x-1\)分裂，左子樹的大小\(+1\)就是排名。
int rnk(int x){
int l,r;
split(root,l,r,x-1);
int tmp=tr[l].size+1;
root=merge(l,r);
return tmp;
}
查詢排名為k的數(shù)
這個操作無法用按權(quán)值分裂來解決，一般來說有兩種寫法，一種是使用按大小分裂的方法，分裂出前k個數(shù)；另一種是二分解決，這里給出后者的代碼。
查詢第k大代碼
int kth(int u,int k){
int p=tr[tr[u].ls].size+1;
if(p==k) return tr[u].x;
if(p<k) return kth(tr[u].rs,k-p);
return kth(tr[u].ls,k);
}
前驅(qū)和后繼
前驅(qū)
前驅(qū)定義為小于\(x\)的最大的數(shù)，按照定義，我們按\(x-1\)分裂，左子樹最大的一個數(shù)（即\(kth(l_{size})\))就是\(x\)的前驅(qū)。
求前驅(qū)代碼
int pre(int x){
int l,r;
split(root,l,r,x-1);
int tmp=kth(l,tr[l].size);
root=merge(l,r);
return tmp;
}
后繼
同理，按照\(x\)分裂，右子樹的最小值就是\(x\)的后繼。
求后繼代碼
int nxt(int x){
int l,r;
split(root,l,r,x);
int tmp=kth(r,1);
root=merge(l,r);
return tmp;
}
維護區(qū)間
區(qū)間操作一般由線段樹維護，但是，有些問題（如區(qū)間翻轉(zhuǎn)）用線段樹維護就比較麻煩，那么該用什么維護呢？
平衡樹。
事實上，平衡樹除了可以作為”排序樹“，也可以作為”區(qū)間樹“，以在數(shù)列中的序號為權(quán)值建一棵平衡樹（這顆平衡樹的中序遍歷就是原數(shù)列），就可以輕易地修改和查詢一段區(qū)間的信息。
那么我們?nèi)绾翁崛〕鲆欢螀^(qū)間呢？如果按值分裂，分裂后的操作很可能不符合平衡樹性質(zhì)（如區(qū)間翻轉(zhuǎn)），所以我們用到了另一種分裂方式——按大小（排名）分裂。
假如有一個區(qū)間\([l,r]\)，那么先按照\(r-1\)分裂成樹1和樹2，在把樹1按\(l\)分裂成數(shù)3和樹4，那么區(qū)間\([l,r]\)就是樹4所表示的區(qū)間。
于是我們就可以修改或者查詢樹4的信息了！
區(qū)間翻轉(zhuǎn)
FHQtreap如何實現(xiàn)區(qū)間翻轉(zhuǎn)？
假如有一個序列\(\{1,1,4,5,1,4\}\)，我們想翻轉(zhuǎn)\([2,5]\)區(qū)間。
先把[2,5]分裂出來。
你會發(fā)現(xiàn)，所謂區(qū)間翻轉(zhuǎn)，就是把樹2自頂向下交換左右子樹。
所以就可以用分裂區(qū)間\(\to\)自頂向下交換左右子樹\(\to\)合并，來維護一段區(qū)間的翻轉(zhuǎn)。
但是如果要依次交換這段區(qū)間內(nèi)的每一個左右子樹，時間復雜度就會達到\(O(n)\)，所以我們可以使用懶標記的方式（默認你會）維護。
給要翻轉(zhuǎn)的區(qū)間樹打上標記，再合并進去，這樣就不影響復雜度了！
具體實現(xiàn)見例題·文藝平衡樹。
習題
P3369 普通平衡樹
模板題，沒什么好講的。
AC代碼
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node{
int x,rnd,size;
int ls,rs;
}tr[N];
int tot=0,root=0;
void pushup(int x){
tr[x].size=tr[tr[x].ls].size+tr[tr[x].rs].size+1;
}
int newNode(int x){
tr[++tot]={x,rand(),1,0,0};
return tot;
}
void split(int u,int &x,int &y,int val){
if(!u){
x=y=0;
return;
}
if(tr[u].x<=val) x=u,split(tr[x].rs,tr[x].rs,y,val);
else y=u,split(tr[y].ls,x,tr[y].ls,val);
pushup(u);
}
int merge(int x,int y){
if(!x||!y) return x+y;
if(tr[x].rnd<tr[y].rnd){
tr[x].rs=merge(tr[x].rs,y);
pushup(x);
return x;
}
else{
tr[y].ls=merge(x,tr[y].ls);
pushup(y);
return y;
}
}
void insert(int x){
int l,r;
split(root,l,r,x);
root=merge(merge(l,newNode(x)),r);
}
void del(int x){
int l,r,xx,yy;
split(root,l,r,x);
split(l,xx,yy,x-1);
yy=merge(tr[yy].ls,tr[yy].rs);
root=merge(merge(xx,yy),r);
}
int rnk(int x){
int l,r;
split(root,l,r,x-1);
int tmp=tr[l].size+1;
root=merge(l,r);
return tmp;
}
int kth(int u,int k){
int p=tr[tr[u].ls].size+1;
if(p==k) return tr[u].x;
if(p<k) return kth(tr[u].rs,k-p);
return kth(tr[u].ls,k);
}
int pre(int x){
int l,r;
split(root,l,r,x-1);
int tmp=kth(l,tr[l].size);
root=merge(l,r);
return tmp;
}
int nxt(int x){
int l,r;
split(root,l,r,x);
int tmp=kth(r,1);
root=merge(l,r);
return tmp;
}
int n;
int main(){
cin>>n;
while(n--){
int opt,x;
cin>>opt>>x;
if(opt==1) insert(x);
if(opt==2) del(x);
if(opt==3) cout<<rnk(x)<<endl;
if(opt==4) cout<<kth(root,x)<<endl;
if(opt==5) cout<<pre(x)<<endl;
if(opt==6) cout<<nxt(x)<<endl;
}
}
P1486 郁悶的出納員
設(shè)置一個\(\Delta\)把工資的調(diào)整記錄下來。
\(I\)操作插入新節(jié)點時直接插入\(x-\Delta\)。
\(S\)操作時，先改\(\Delta\)，然后把小于\(\min-\Delta\)的刪掉（這個用fhq做就很方便）
輸出的時候別忘了加上\(\Delta\)。
AC代碼（古早時期的代碼，碼風可能有點差別）
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node{
int ls,rs;
int x,rnd,size;
}tr[N];
int tot=0,root=0;
int newNode(int x){
tr[++tot]={0,0,x,rand(),1};
return tot;
}
inline void pushup(int x){
tr[x].size=tr[tr[x].ls].size+tr[tr[x].rs].size+1;
}
void split(int u,int &x,int &y,int val){
if(!u){
x=y=0;
return;
}
if(tr[u].x<=val) x=u,split(tr[x].rs,tr[x].rs,y,val);
else y=u,split(tr[y].ls,x,tr[y].ls,val);
pushup(u);
}
int merge(int x,int y){
if(!x||!y) return x+y;
if(tr[x].rnd<tr[y].rnd){
tr[x].rs=merge(tr[x].rs,y);
pushup(x);
return x;
}
else{
tr[y].ls=merge(x,tr[y].ls);
pushup(y);
return y;
}
}
int tag=0;//tag表示工資調(diào)整
void insert(int x){
int l,r;
split(root,l,r,x);
root=merge(l,merge(newNode(x),r));
}
int getNum(int u,int k){
int p=tr[tr[u].ls].size+1;
if(p==k) return tr[u].x;
if(p>k) return getNum(tr[u].ls,k);
return getNum(tr[u].rs,k-p);
}
int n,minn,ans=0;
void del(int x){
int l,r,xx,yy;
split(root,l,r,x);
split(l,xx,yy,x-1);
yy=merge(tr[yy].ls,tr[yy].rs);
root=merge(merge(xx,yy),r);
}
int main(){
char op;
int x;
cin>>n>>minn;
for(int i=1;i<=n;i++){
cin>>op>>x;
if(op=='I'){
if(x>=minn) insert(x-tag);
}
else if(op=='A') tag+=x;
else if(op=='S'){
tag-=x;
int l=0,r=0;
split(root,l,r,minn-tag-1);
ans+=tr[l].size;
root=r;
}
else{
if(tr[root].size<x) cout<<-1<<endl;
else cout<<getNum(root,tr[root].size-x+1)+tag<<endl;
}
}
cout<<ans<<endl;
}
P5338 甲苯先生的滾榜
題目要求排序時有兩個關(guān)鍵詞，用平衡樹怎么做呢？
正常使用sort或者優(yōu)先隊列的時候，如果有多個關(guān)鍵詞，我們一般會使用重載運算符，而這種多關(guān)鍵詞的平衡樹問題，我們也可以使用重載運算符，注意要重載\(<\)和\(\le\)兩個運算符。
AC代碼
#include <bits/stdc++.h>
using namespace std;
struct cmp{
//重載運算符的結(jié)構(gòu)體
int cnt,tim;
bool operator<=(const cmp b)const{
if(cnt==b.cnt) return tim<=b.tim;
return cnt>=b.cnt;
}
bool operator<(const cmp b)const{
if(cnt==b.cnt) return tim<b.tim;
return cnt>b.cnt;
}
};
const int N=2e6+10;
struct node{
cmp x;
int rnd,size;
int ls,rs;
}tr[N];
cmp peo[N];
int tot=0,root;
inline void pushup(int x){
tr[x].size=tr[tr[x].ls].size+tr[tr[x].rs].size+1;
}
int newNode(cmp x){
tr[++tot]={x,rand(),1,0,0};
return tot;
}
void split(int u,int &x,int &y,cmp val){
if(!u){
x=y=0;
return;
}
if(tr[u].x<=val) x=u,split(tr[x].rs,tr[x].rs,y,val);
else y=u,split(tr[y].ls,x,tr[y].ls,val);
pushup(u);
}
int merge(int x,int y){
if(!x||!y) return x+y;
if(tr[x].rnd<tr[y].rnd){
tr[x].rs=merge(tr[x].rs,y);
pushup(x);
return x;
}
else{
tr[y].ls=merge(x,tr[y].ls);
pushup(y);
return y;
}
}
void del(cmp x){
int l,r,xx,yy;
split(root,l,r,x);
split(l,xx,yy,{x.cnt,x.tim-1});//造成正常平衡樹x-1的效果
yy=merge(tr[yy].ls,tr[yy].rs);
root=merge(merge(xx,yy),r);
}
void insert(cmp x){
int l,r;
split(root,l,r,x);
root=merge(merge(l,newNode(x)),r);
}
void clear(){
//多組數(shù)據(jù)，清空直接讓根指向0就行
root=tot=0;
}
typedef unsigned int ui;
int m,n;
ui seed;
ui randNum( ui& seed , ui last , const ui m){
//題目要求的隨機數(shù)種子（千萬不要把ui什么的改了，會出錯的?。? seed = seed * 17 + last ; return seed % m + 1;
}
int T,last=7;
int main(){
cin>>T;
while(T--){
clear();
cin>>m>>n>>seed;
for(int i=1;i<=m;i++){
peo[i]={0,0};
insert(peo[i]);
}
for(int i=1;i<=n;i++){
int ria=randNum(seed,last,m),rib=randNum(seed,last,m);
del(peo[ria]);
peo[ria].cnt++,peo[ria].tim+=rib;
insert(peo[ria]);
int l,r;
split(root,l,r,{peo[ria].cnt,peo[ria].tim-1});
last=tr[l].size;
cout<<last<<endl;
root=merge(l,r);
}
}
return 0;
}
P3850 書架
每次插入一個數(shù)，后面每一個數(shù)的排名都會\(+1\)，可以把排名當成權(quán)值，每次插入就用懶標記給后面的數(shù)\(+1\)。
注意要保存一個書名的映射（最好直接把書名放到結(jié)構(gòu)體里）
AC代碼
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+211;
struct node{
int x,rnd,size;
int ls,rs;
int add;//懶標記
string name;//書名
}tr[N];
int tot=0,root;
int newNode(string str,int i){
tr[++tot]={i,rand(),1,0,0,0,str};
return tot;
}
inline void pushup(int x){
tr[x].size=tr[tr[x].ls].size+tr[tr[x].rs].size+1;
}
inline void pushdown(int x){
tr[tr[x].ls].x+=tr[x].add,tr[tr[x].rs].x+=tr[x].add;
tr[tr[x].ls].add+=tr[x].add,tr[tr[x].rs].add+=tr[x].add;
tr[x].add=0;
}
void split(int u,int &x,int &y,int val){
if(!u){
x=y=0;
return;
}
pushdown(u);//在分裂和并時都要下放懶標記
if(tr[u].x<=val) x=u,split(tr[x].rs,tr[x].rs,y,val);
else y=u,split(tr[y].ls,x,tr[y].ls,val);
pushup(u);
}
int merge(int x,int y){
if(!x||!y) return x+y;
if(tr[x].rnd<tr[y].rnd){
pushdown(x);
tr[x].rs=merge(tr[x].rs,y);
pushup(x);
return x;
}
else{
pushdown(y);
tr[y].ls=merge(x,tr[y].ls);
pushup(y);
return y;
}
}
int kth(int u,int k){
int p=tr[tr[u].ls].size+1;
if(p==k) return tr[u].x;
if(p<k) return kth(tr[u].rs,k-p);
return kth(tr[u].ls,k);
}
int n,m,q;
int main(){
cin>>n;
for(int i=0;i<n;i++){
string str;
cin>>str;
root=merge(root,newNode(str,i));//因為插入時排名就是單調(diào)的，所以可以這樣直接建樹
}
cin>>m;
while(m--){
string str;
int x,l,r;
cin>>str>>x;
split(root,l,r,x-1);
tr[r].add++,tr[r].x++;//給后面的數(shù)排名加上1
r=merge(newNode(str,x),r);
root=merge(l,r);
}
cin>>q;
while(q--){
int x,l,r,xx,yy;
cin>>x;
split(root,l,r,x);
split(l,xx,yy,x-1);
cout<<tr[yy].name<<endl;
root=merge(merge(xx,yy),r);
}
return 0;
}
P3391 文藝平衡樹
平衡樹區(qū)間翻轉(zhuǎn)的模板，我們剛剛已經(jīng)講過，直接放代碼。
AC代碼
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node{
int x,rnd,size;
int ls,rs;
int add;
}tr[N];
int tot=0,root=0;
inline void pushup(int x){
tr[x].size=tr[tr[x].ls].size+tr[tr[x].rs].size+1;
}
inline void pushdown(int x){
//pushdown和線段樹的差不多
if(tr[x].add){
swap(tr[x].ls,tr[x].rs);
tr[x].add=0;
if(tr[x].ls) tr[tr[x].ls].add^=1;
if(tr[x].rs) tr[tr[x].rs].add^=1;
}
}
int newNode(int x){
tr[++tot]={x,rand(),1,0,0};
return tot;
}
void split(int u,int &x,int &y,int size){
if(!u){
x=y=0;
return;
}
pushdown(u);//每次分裂合并前都要下放標記
if(tr[tr[u].ls].size<size) x=u,split(tr[u].rs,tr[u].rs,y,size-tr[tr[u].ls].size-1);
else y=u,split(tr[u].ls,x,tr[u].ls,size);
pushup(u);
}
int merge(int x,int y){
if(!x||!y) return x+y;
if(tr[x].rnd<tr[y].rnd){
pushdown(x);
tr[x].rs=merge(tr[x].rs,y);
pushup(x);
return x;
}
else{
pushdown(y);
tr[y].ls=merge(x,tr[y].ls);
pushup(y);
return y;
}
}
void put(int x){
if(!x) return;
pushdown(x);//輸出時也要先下放標記
put(tr[x].ls);
cout<<tr[x].x<<" ";
put(tr[x].rs);
}
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
root=merge(root,newNode(i));
for(int i=1;i<=m;i++){
int l,r;
cin>>l>>r;
int x,y,xx,yy;
split(root,x,y,l-1);
split(y,xx,yy,r-l+1);
tr[xx].add^=1;
y=merge(xx,yy);
root=merge(x,y);
}
put(root);
}
P4146 序列終結(jié)者
平衡樹維護區(qū)間信息的模板題。
大意是要維護區(qū)間最大值，另外要維護區(qū)間加和區(qū)間翻轉(zhuǎn)。
維護兩個懶標記即可，每個節(jié)點維護一個最大值，表示當前子樹內(nèi)最大的數(shù)。
AC代碼
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
struct node{
int val,maxx,tag,add;
int rnd,size;
int ls,rs;
}tr[N];
int tot=0,root;
void pushup(int x){
tr[x].size=tr[tr[x].ls].size+tr[tr[x].rs].size+1;
tr[x].maxx=max({tr[x].val,tr[tr[x].ls].maxx,tr[tr[x].rs].maxx});
//這里的pushup操作除了維護子樹大小，還要維護一個區(qū)間最大值
}
void pushdown(int x){
if(tr[x].add){
//區(qū)間加懶標記，和線段樹差不多，但是要加上節(jié)點本身
tr[tr[x].ls].maxx+=tr[x].add,tr[tr[x].rs].maxx+=tr[x].add;
tr[tr[x].ls].val+=tr[x].add,tr[tr[x].rs].val+=tr[x].add;
tr[tr[x].ls].add+=tr[x].add,tr[tr[x].rs].add+=tr[x].add;
tr[x].add=0;
}
if(tr[x].tag){
//區(qū)間翻轉(zhuǎn)
swap(tr[x].ls,tr[x].rs);
tr[tr[x].ls].tag^=1,tr[tr[x].rs].tag^=1;
tr[x].tag=0;
}
}
int newNode(int x){
tr[++tot]={x,x,0,0,rand(),1,0,0};
return tot;
}
void split(int u,int &x,int &y,int size){
if(!u){
x=y=0;
return;
}
pushdown(u);//每次分裂合并前都要下傳標記
if(tr[tr[u].ls].size<size) x=u,split(tr[u].rs,tr[u].rs,y,size-tr[tr[u].ls].size-1);
else y=u,split(tr[u].ls,x,tr[u].ls,size);
pushup(u);
}
int merge(int x,int y){
if(!x||!y) return x+y;
if(tr[x].rnd<tr[y].rnd){
pushdown(x);
tr[x].rs=merge(tr[x].rs,y);
pushup(x);
return x;
}
else{
pushdown(y);
tr[y].ls=merge(x,tr[y].ls);
pushup(y);
return y;
}
}
int n,m;
signed main(){
cin>>n>>m;
tr[0].maxx=-1e18;
for(int i=1;i<=n;i++) root=merge(root,newNode(0));
for(int i=1;i<=m;i++){
int opt,l,r,v;
int x,y,z,k;
cin>>opt>>l>>r;
if(opt==1){
//區(qū)間加
cin>>v;
split(root,x,y,r);
split(x,z,k,l-1);
//和線段樹懶標記差不多
tr[k].add+=v,tr[k].maxx+=v,tr[k].val+=v;
x=merge(z,k);
root=merge(x,y);
}
if(opt==2){
//區(qū)間翻轉(zhuǎn)
split(root,x,y,r);
split(x,z,k,l-1);
tr[k].tag^=1;
x=merge(z,k);
root=merge(x,y);
}
if(opt==3){
//直接輸出區(qū)間最大值
split(root,x,y,r);
split(x,z,k,l-1);
cout<<tr[k].maxx<<endl;
x=merge(z,k);
root=merge(x,y);
}
}
return 0;
}
P4008 文本編輯器
刪除區(qū)間，插入?yún)^(qū)間，輸出區(qū)間。
這題的輸入比較坑，需要注意。
AC代碼
#include <bits/stdc++.h>
using namespace std;
const int N=2e6+10;
struct node{
char ch;
int rnd,size;
int ls,rs;
}tr[N];
int tot=0,root;
inline void pushup(int x){
tr[x].size=tr[tr[x].ls].size+tr[tr[x].rs].size+1;
}
int newNode(char ch){
tr[++tot]={ch,rand(),1,0,0};
return tot;
}
void split(int u,int &x,int &y,int size){
if(!u){
x=y=0;
return;
}
if(tr[tr[u].ls].size<size) x=u,split(tr[u].rs,tr[u].rs,y,size-tr[tr[u].ls].size-1);
else y=u,split(tr[u].ls,x,tr[y].ls,size);
pushup(u);
}
int merge(int x,int y){
if(!x||!y) return x+y;
if(tr[x].rnd<tr[y].rnd){
tr[x].rs=merge(tr[x].rs,y);
pushup(x);
return x;
}
else{
tr[y].ls=merge(x,tr[y].ls);
pushup(y);
return y;
}
}
void put(int x){
if(!x) return;
put(tr[x].ls);
putchar(tr[x].ch);
put(tr[x].rs);
}
int build(int n,string s){
int u=newNode(s[0]);
for(int i=1;i<n;i++) u=merge(u,newNode(s[i]));
return u;
}
int gb=0,T;
int main(){
cin>>T;
for(int i=1;i<=T;i++){
string opt;
int l,r,xx,yy,n;
cin>>opt;
if(opt=="Move") cin>>gb;
if(opt=="Insert"){
cin>>n;
string tmp={};
for(int i=0;i<n;i++){
char ch=getchar();
while(ch<32||ch>126) ch=getchar();
tmp+=ch;
}
int u=build(n,tmp);
split(root,l,r,gb);
root=merge(merge(l,u),r);
}
if(opt=="Delete"){
cin>>n;
split(root,l,r,n+gb);
split(l,xx,yy,gb);
root=merge(xx,r);
}
if(opt=="Get"){
cin>>n;
split(root,l,r,n+gb);
split(l,xx,yy,gb);
put(yy);//中序遍歷輸出
putchar('\n');
root=merge(merge(xx,yy),r);
}
if(opt=="Prev") gb--;
if(opt=="Next") gb++;
}
}
P3372 【模板】線段樹 1
達成成就，用線段樹寫平衡樹，用平衡樹寫線段樹……
AC代碼
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
struct node{
int val,sum,add;
int rnd,size;
int ls,rs;
}tr[N];
inline void pushup(int x){
tr[x].size=tr[tr[x].ls].size+tr[tr[x].rs].size+1;
tr[x].sum=tr[tr[x].ls].sum+tr[tr[x].rs].sum+tr[x].val;
}
inline void pushdown(int x){
tr[tr[x].ls].sum+=tr[tr[x].ls].size*tr[x].add;
tr[tr[x].rs].sum+=tr[tr[x].rs].size*tr[x].add;
tr[tr[x].ls].add+=tr[x].add,tr[tr[x].rs].add+=tr[x].add;
tr[tr[x].ls].val+=tr[x].add,tr[tr[x].rs].val+=tr[x].add;
tr[x].add=0;
}
int tot=0,root;
int newNode(int x){
tr[++tot]={x,x,0,rand(),1,0,0};
return tot;
}
void split(int u,int &x,int &y,int size){
if(!u){
x=y=0;
return;
}
pushdown(u);
if(tr[tr[u].ls].size<size) x=u,split(tr[u].rs,tr[u].rs,y,size-tr[tr[u].ls].size-1);
else y=u,split(tr[u].ls,x,tr[u].ls,size);
pushup(u);
}
int merge(int x,int y){
if(!x||!y) return x+y;
if(tr[x].rnd<tr[y].rnd){
pushdown(x);
tr[x].rs=merge(tr[x].rs,y);
pushup(x);
return x;
}
else{
pushdown(y);
tr[y].ls=merge(x,tr[y].ls);
pushup(y);
return y;
}
}
int n,m;
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int x;
cin>>x;
root=merge(root,newNode(x));
}
while(m--){
int opt,x,y,k,l,r,xx,yy;
cin>>opt>>x>>y;
if(opt==1){
cin>>k;
split(root,l,r,y);
split(l,xx,yy,x-1);
tr[yy].add+=k;
tr[yy].sum+=tr[yy].size*k;
tr[yy].val+=k;
root=merge(merge(xx,yy),r);
}
else{
split(root,l,r,y);
split(l,xx,yy,x-1);
cout<<tr[yy].sum<<endl;
root=merge(merge(xx,yy),r);
}
}
return 0;
}
P3380 二逼平衡樹（樹套樹）
這種動態(tài)的區(qū)間排名問題一般用樹套樹（線段樹套平衡樹）解決。
樹套樹，就是先建一顆平衡樹，在每個節(jié)點內(nèi)建一顆平衡樹，插入這個區(qū)間內(nèi)的所有樹，均攤空間復雜度大概是\(O(\log n)\)
查詢\(k\)在區(qū)間內(nèi)的排名，可以在所有包含區(qū)間內(nèi)找小于\(k\)的數(shù)的個數(shù)，都加起來在\(+1\)。時間復雜度\(O(\log^2 n)\)。
修改某一位值上的數(shù)值，找所有包含這這個數(shù)的節(jié)點，在這些節(jié)點上刪去這個數(shù)，在插入新的數(shù)。時間復雜度也是\(O(\log^2 n)\)。
查詢\(k\)在區(qū)間內(nèi)的前驅(qū)，在所有包含區(qū)間內(nèi)找\(k\)的前驅(qū)，取最大值；同理，后繼就是取最小值了。時間復雜度是\(O(\log^2 n)\)。
唯一復雜的是查詢區(qū)間內(nèi)排名為\(k\)的值，我們可以用二分答案的方法，在\([0,10^8]\)的范圍內(nèi)二分，判斷這個數(shù)排名是不是\(k\)，時間復雜度是\(O(\log^3 n)\)。
樹套樹寫起來比較復雜，可以鍛煉碼力和調(diào)試能力（我當時調(diào)了兩周）
AC代碼
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+10,inf=2147483647;
namespace FHQ{
//把平衡樹封裝
struct node{
int x,rnd,size;
int ls,rs;
}tr[N<<6];
int tot=0;
class fhq{
public:
int root;
int newNode(int x){
tr[++tot]={x,rand(),1,0,0};
return tot;
}
inline void pushup(int x){
tr[x].size=tr[tr[x].ls].size+tr[tr[x].rs].size+1;
}
void split(int u,int &x,int &y,int val){
if(!u){
x=y=0;
return;
}
if(tr[u].x<=val) x=u,split(tr[x].rs,tr[x].rs,y,val);
else y=u,split(tr[y].ls,x,tr[y].ls,val);
pushup(u);
}
int merge(int x,int y){
if(!x||!y) return x+y;
if(tr[x].rnd<tr[y].rnd){
tr[x].rs=merge(tr[x].rs,y);
pushup(x);
return x;
}
else{
tr[y].ls=merge(x,tr[y].ls);
pushup(y);
return y;
}
}
void insert(int x){
int l,r;
split(root,l,r,x);
root=merge(l,merge(newNode(x),r));
}
void del(int x){
int l,r,xx,yy;
split(root,l,r,x);
split(l,xx,yy,x-1);
yy=merge(tr[yy].ls,tr[yy].rs);
root=merge(merge(xx,yy),r);
}
int rnk(int x){
int l,r;
split(root,l,r,x-1);
int tmp=tr[l].size+1;
root=merge(l,r);
return tmp;
}
int kth(int u,int k){
int p=tr[tr[u].ls].size+1;
if(k==p) return tr[u].x;
if(k<p) return kth(tr[u].ls,k);
return kth(tr[u].rs,k-p);
}
inline int getKth(int x){
return kth(root,x);
}
int pre(int x){
int l,r;
split(root,l,r,x-1);
int tmp=kth(l,tr[l].size);
root=merge(l,r);
return tmp;
}
int nxt(int x){
int l,r;
split(root,l,r,x);
int tmp=kth(r,1);
root=merge(l,r);
return tmp;
}
};
}
struct node{
int l,r;
int maxx,minn;
}tr[N<<2];
FHQ::fhq tree[N<<2];
int a[N];
int n,m;
inline void pushup(int x){
tr[x].maxx=max(tr[x*2].maxx,tr[x*2+1].maxx);
tr[x].minn=min(tr[x*2].minn,tr[x*2+1].minn);
}
void build(int x,int l,int r){
tr[x].l=l,tr[x].r=r;
for(int i=l;i<=r;i++) tree[x].insert(a[i]);
if(l==r){
tr[x].maxx=tr[x].minn=a[l];
return;
}
int mid=(l+r)/2;
build(x*2,l,mid),build(x*2+1,mid+1,r);
pushup(x);
}
int rnk(int x,int l,int r,int k){
if(tr[x].l>=l&&tr[x].r<=r) return tree[x].rnk(k);
int mid=(tr[x].l+tr[x].r)/2,res=1;
if(l<=mid) res+=rnk(x*2,l,r,k)-1;
if(r>mid) res+=rnk(x*2+1,l,r,k)-1;
return res;
}
int kth(int l,int r,int k){
int x=0,y=1e8+10,ans=0;
while(x<=y){
int mid=(x+y)/2,tmp=rnk(1,l,r,mid);
if(tmp<=k) x=mid+1,ans=mid;
else y=mid-1;
}
return ans;
}
int pre(int x,int l,int r,int k){
if(tr[x].l>=l&&tr[x].r<=r){
if(tr[x].minn>=k) return -inf;
return tree[x].pre(k);
}
int mid=(tr[x].l+tr[x].r)/2,maxx=-inf;
if(l<=mid) maxx=max(maxx,pre(x*2,l,r,k));
if(r>mid) maxx=max(maxx,pre(x*2+1,l,r,k));
return maxx;
}
int nxt(int x,int l,int r,int k){
if(tr[x].l>=l&&tr[x].r<=r){
if(tr[x].maxx<=k) return inf;
return tree[x].nxt(k);
}
int mid=(tr[x].l+tr[x].r)/2,minn=inf;
if(l<=mid) minn=min(minn,nxt(x*2,l,r,k));
if(r>mid) minn=min(minn,nxt(x*2+1,l,r,k));
return minn;
}
void change(int x,int k,int p){
tree[x].del(a[k]);
tree[x].insert(p);
if(tr[x].l==tr[x].r){
tr[x].maxx=tr[x].minn=a[k]=p;
return;
}
int mid=(tr[x].l+tr[x].r)/2;
if(k<=mid) change(x*2,k,p);
else change(x*2+1,k,p);
pushup(x);
}
signed main(){
srand(19260817);
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
build(1,1,n);
while(m--){
int opt,l,r,k;
scanf("%lld%lld%lld",&opt,&l,&r);
if(opt!=3) scanf("%lld",&k);
if(opt==1) printf("%lld\n",rnk(1,l,r,k));
if(opt==2) printf("%lld\n",kth(l,r,k));
if(opt==3) change(1,l,r);
if(opt==4) printf("%lld\n",pre(1,l,r,k));
if(opt==5) printf("%lld\n",nxt(1,l,r,k));
}
}
后記
本文所有配圖都是作者自己畫的，如果想使用，請不要刪去水印。
浙公網(wǎng)安備 33010602011771號