肥宅快乐主席树
目錄
- 靜態(tài)主席樹
- 算法理解
- 例題
- 講解
- 練習
- 樹上第k小
- 毒瘤逆序對
- 求區(qū)間種類
- 簡單詢問
- 簡單查詢
- 矩陣主席樹大暴力！！！
- 算法理解
- 動態(tài)主席樹
- 講解
- 例題
- 算法講解
- 代碼
- 練習
- 不是動態(tài)主席樹的帶修題。
- 講解
- 可持久化主席樹
- 例題
- 思路
- 單點修改
- 區(qū)間修改
- 代碼
- 小結
- 小結
- 查錯
靜態(tài)主席樹
算法理解
例題
時間限制: 1 Sec 內存限制: 128 MB 【問題描述】 給n（1<=n<=100000）個數(shù)字a[1],a[2],......,a[n]（0<=a[i]<=1000000000）,m（1<=m<=100000）次詢問l到r之間的第k小的值。 【輸入文件】 第一行為n和m。 接下來一行輸入n個數(shù)。 接下來m行，每行三個數(shù)l,r和k。 【輸出文件】 m行，每行對應一個答案。 【輸入樣例】 7 3 1 5 2 6 3 7 4 2 5 3 4 4 1 1 7 3 【輸出樣例】 5 6 3講解
例題思路
首先，看到這道題目，我們是懵逼的，甚至很迷茫。
但是仔細思考，我們都知道線段樹是維護整段的區(qū)間第\(k\)大，但是如何找到一段呢？
這是有個想法閃過，就是我們可以將\(l-r\)區(qū)間內的數(shù)字扔到一個權值線段樹內進行查詢。
這便是一種較暴力的做法了。
主席樹？前綴和？
主席樹本質上可以說是缺了許多東西的線段樹（不嚴謹），但是這樣子讓主席樹更加的靈活，具有更多的功能。
但同時伴隨的常數(shù)大的問題。
主席樹主要支持這些操作：
我們要提取\(l-r\)區(qū)間內的數(shù)字，而主席樹又支持加減，這不由讓我們想到了前綴和。
想到了個思路我們就要去實現(xiàn)他。
插點link
主席樹是棵殘缺的線段樹，也就是說只有一條鏈也是可以的，那我們就把每個位置都當成一棵權值主席樹，然后把這個點插進去。
如下圖（注意是權值線段樹）：
圖好丑博主手繪差就不多吐槽了，好吧。
代碼如下：
void link(int &now,int l,int r,int c) {if(!now)now=++len;tr[now].c++;if(l==r)return ;int mid=(l+r)/2;if(c<=mid)link(tr[now].lc,l,mid,c);else link(tr[now].rc,mid+1,r,c); }你可以認為這是一個數(shù)組，那么他離前綴和數(shù)組還有一個步驟，就是從前加到后，也就是\(merge\)
merge
合并是什么東西？
先說合并的限制：合并的話一般限于兩棵主席樹維護范圍相同、維護值的意義是相同的，且目前兩棵主席樹里面維護的點不重復（有時候可以重，看是權值還是位置）。
而合并，也是有點講究的。
如圖是一個將第一個主席樹\(A\)合并到第二棵主席樹\(B\)里面的一個例子，首先，我們需要將\(A\)相同的節(jié)點（指維護范圍一樣的點）的\(c\)值添加到\(B\)的節(jié)點里面去，同時給\(B\)補上\(B\)沒有\(A\)有的點，補得方法不是新建節(jié)點，而是直接把兒子認到\(A\)的節(jié)點上面，也就是說上圖合并完后樹的樣子應長這樣：
而主席樹或者線段樹一般都是跳兒子的，這樣做貌似也沒多大問題喲。
那么我們就可以從前到后合并的。
但是同時也有個問題，不要把三棵樹合并在一棵樹上，不然總會有個節(jié)點會被改變，導致前面的主席樹改過了，出現(xiàn)一坨鍋，所以主席樹最好不要把許多樹合并到一棵樹上（但可以按順序合并），當然也存在特殊情況，畢竟總有萬一。
那么這些前綴和是可以預處理的，復雜度也是\(O(nlogn)\)，因為一條鏈你再怎么跳也只能跳到\(logn\)個節(jié)點，然后合并\(n\)次。
順便提一提：合并只要你不改變前面樹的形態(tài)，在不改變時間復雜度的方法，可以有一些其他的方法進行建樹（也是前綴和，但是可能每棵樹有好幾條鏈）。
void merge(int &x,int y)//y合并到x里面去 {if(x==0){x=y;return ;}if(y==0)return ;tr[x].c+=tr[y].c;merge(tr[x].l,tr[y].l);merge(tr[x].r,tr[y].r); }快樂加減
加法一般要求兩棵主席樹維護的點沒有重合，而減法一般是要求減樹維護的點集是被減樹的子集，同時一般要求維護的東西相同，范圍相同。
當然，這里維護的點的意思一般是位置，不如說一個維護的是1、3、5號點，另外一個是2、4號點，而不是權值重復，即使是權值主席樹，一般也是這樣的。
利用加減，有時候我們可以進行容斥原理來得到我們想要的點的子集。
這里我們就用類似前綴和的方法：拿\(r\)的主席樹減去\(l-1\)的主席樹，就得出了區(qū)間的主席樹，然后查詢。
int cale(int x/*減樹*/,int y/*被減樹*/,int l,int r,int k) {if(l==r)return ls[l].x;int mid=(l+r)/2,kc=tr[tr[x].l].c-tr[tr[y].l].c;//左邊區(qū)間有多少個數(shù)字。if(k<=kc)return cale(tr[x].l,tr[y].l,l,mid,k);else return cale(tr[x].r,tr[y].r,mid+1,r,k-kc); }完整代碼
既然詢問代碼都出來了，那就代碼一起貼出來吧，當然你樂意的話加個離散化也是可以的。
#include<cstdio> #include<cstring> #define N 110000 #define M 5100000 #define INF 1000000000//數(shù)字的范圍 using namespace std; struct node {int lc,rc,c; }tr[M];int len=0,rt[N]/*根節(jié)點數(shù)組*/; void link(int &now,int l,int r,int c) {if(!now)now=++len;//新建節(jié)點tr[now].c++;if(l==r)return ;int mid=(l+r)/2;if(c<=mid)link(tr[now].lc,l,mid,c);else link(tr[now].rc,mid+1,r,c); } void merge(int &x,int y) {if(!x){x=y;return ;}if(!y)return ;tr[x].c+=tr[y].c;merge(tr[x].lc,tr[y].lc);merge(tr[x].rc,tr[y].rc); } int calc(int x,int y,int l,int r,int k) {if(l==r)return l;int zhe=tr[tr[y].lc].c-tr[tr[x].lc].c,mid=(l+r)/2;if(zhe<k)return calc(tr[x].rc,tr[y].rc,mid+1,r,k-zhe);else return calc(tr[x].lc,tr[y].lc,l,mid,k); } int n,m; int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int x;scanf("%d",&x);link(rt[i],0,INF,x);merge(rt[i],rt[i-1]);}for(int i=1;i<=m;i++){int l,r,k;scanf("%d%d%d",&l,&r,&k);printf("%d\n",calc(rt[l-1],rt[r],0,INF,k));}return 0; }練習
樹上第k小
時間限制: 2 Sec 內存限制: 128 MB 【題目描述】 給定一棵N（1<=N<=100000）個節(jié)點的樹，每個點有一個權值，對于M（1<=M<=100000）個詢問(x,y,k)，你需要回答x和y這兩個節(jié)點間第k小的點權。 【輸入數(shù)據(jù)】 第一行兩個整數(shù)N,M。 第二行有N個整數(shù)，其中第i個整數(shù)表示點i的權值。 后面N-1行每行兩個整數(shù)(x,y)，表示點x到點y有一條無向邊。 最后M行每行兩個整數(shù)(x,y,k)，表示一組詢問。 【輸出數(shù)據(jù)】 M行，表示每個詢問的答案。 【輸入樣例】 8 5 105 2 9 3 8 5 7 7 1 2 1 3 1 4 3 5 3 6 3 7 4 8 2 5 1 1 5 2 7 8 3 1 6 3 3 4 2 【輸出樣例】 2 9 7 105 9一看就就是一道毒瘤題，我們可以發(fā)現(xiàn)\(x->y\)的路徑可以分為兩部分（設\(z=lca(x,y)\)）：\(x->z,y->z\)（\(z\)重合了，在后面的容斥原理中會解決這問題），那么我們仍然要把\(x->y\)提取出來，那么我們就設\(x\)的主席樹代表的\(x\)到根節(jié)點這些點權值的主席樹，那么就可以一個DFS解決主席樹預處理的問題了，提取的話我們也可以用容斥原理解決:
(\([x]\)代表\(x\)的主席樹，以此類推)\([x]+[y]-[z]-[fa(z)]\)。這樣不就好起來了嗎？（滑稽）
//這里的LCA是用ST表的 #include<cstdio> #include<cstring> #include<algorithm> #define M 410000 #define NN 5100000 using namespace std; struct node {int y,next; }a[M];int len,last[M]; inline void ins(int x,int y){len++;a[len].y=y;a[len].next=last[x];last[x]=len;} int st[25][M],log2[M],in[M],out[M],dep[M],cnt,fa[M]; void dfs(int x) {st[0][++cnt]=x;in[x]=cnt;for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(fa[x]!=y){fa[y]=x;dep[y]=dep[x]+1;dfs(y);st[0][++cnt]=x;}}out[x]=cnt; }//設1為根節(jié)點，處理DFS序 inline int myminz(int x,int y){return dep[x]<dep[y]?x:y;} void first() {dfs(1);for(int i=2;i<=cnt;i++)log2[i]=log2[i>>1]+1;for(int i=1;i<=log2[cnt];i++){for(int j=cnt-(1<<i)+1;j>=1;j--)st[i][j]=myminz(st[i-1][j],st[i-1][j+(1<<(i-1))]);} }//ST表預處理 inline int lca(int x,int y) {int tx=out[x],ty=in[y];tx>ty?tx^=ty^=tx^=ty:0;int k=log2[ty-tx+1];return myminz(st[k][tx],st[k][ty-(1<<k)+1]); } //LCA struct TREE {int lc,rc,c; }tr[NN];int trlen; void link(int &x,int l,int r,int c) {if(!x)x=++trlen;tr[x].c++;if(l==r)return ;int mid=(l+r)/2;if(c<=mid)link(tr[x].lc,l,mid,c);else link(tr[x].rc,mid+1,r,c); } void merge(int &x,int y) {if(!x){x=y;return ;}if(!y)return ;tr[x].c+=tr[y].c;merge(tr[x].lc,tr[y].lc);merge(tr[x].rc,tr[y].rc); } int ask(int x,int y,int z1,int z2,int l,int r,int k)//x+y-z1-z2 {if(l==r)return l;int zhe=tr[tr[x].lc].c+tr[tr[y].lc].c-tr[tr[z1].lc].c-tr[tr[z2].lc].c,mid=(l+r)/2;if(zhe<k)return ask(tr[x].rc,tr[y].rc,tr[z1].rc,tr[z2].rc,mid+1,r,k-zhe);else return ask(tr[x].lc,tr[y].lc,tr[z1].lc,tr[z2].lc,l,mid,k); }//主席樹 int n,m,rt[M],zhi[M]/*原數(shù)*/; int qwq[M]/*存編號*/,qaq[M]/*離散化后的值*/;//這不是離散化嗎 void ddfs(int x) {for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(fa[x]!=y){link(rt[y],1,n,qaq[y]);merge(rt[y],rt[x]);ddfs(y);}} }//處理每個點的主席樹 inline bool cmp(int x,int y){return zhi[x]<zhi[y];} int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&zhi[i]);qwq[i]=i;}for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);ins(x,y);ins(y,x);}sort(qwq+1,qwq+n+1,cmp);for(int i=1;i<=n;i++)qaq[qwq[i]]=i;first();link(rt[1],1,n,qaq[1]);ddfs(1);for(int i=1;i<=m;i++){int l,r,k;scanf("%d%d%d",&l,&r,&k);if(l>r)l^=r^=l^=r;//異或的靈性交換int x=lca(l,r);printf("%d\n",zhi[qwq[ask(rt[l],rt[r],rt[fa[x]],rt[x],1,n,k)]]);}return 0; }毒瘤逆序對
時間限制: 3 Sec 內存限制: 256 MB 【題目描述】 給你N（1<=N<=50000）個數(shù)，M（1<=M<=50000）個詢問，每個詢問(l,r)求l到r的逆序對數(shù)。 注：逆序指的是a[i]>a[j]并且i<j 【輸入數(shù)據(jù)】 第一行兩個整數(shù)N,M。 第二行有N個整數(shù)。 最后M行每行一組操作。 【輸出數(shù)據(jù)】 M行，表示每個詢問的答案。 【輸入樣例】 5 3 3 1 2 5 4 1 3 2 1 3 5 【輸出樣例】 2 1 1 【提示】 如果被卡常，請加上 #pragma GCC optimize("Ofast")你以為這是一道SB題？不，他不是，他是分塊加主席樹暴力AC的題目。
首先，我們思考一下，如果我們能預處理\(ans[i][j]\)表示\(i\)到\(j\)的逆序對數(shù)，不就好起來了嗎？
不談時間，空間都讓你崩潰的一批，而\(O(n^{2}logn)\)的預處理時間更是黃（TLE的顏色是黃色，MLE也是，在那個OJ上）的飛起。
那么我們就應該考慮一些毒瘤的優(yōu)化，這時，我們就想到了\(ans[i][j]\)表示\(i\)到\(i+(1<<j)-1\)的位置上有多少逆序對數(shù)。
將詢問分成兩段，解決前半段，后半段用快樂主席樹。
但是如何預處理便成了一大難題。
于是我們想到了減復雜度的好幫手，分塊！
\(ans[i][j]\)表示的是\(i\)塊的開頭到\(j\)有幾個逆序對。
用樹狀數(shù)組預處理就可以解決了。
而前半段也是用主席樹輕輕松松搞定的事情。
#pragma GCC optimize("Ofast")//毒瘤優(yōu)化 #include<cstdio> #include<cstring> #include<algorithm> #define sN 310 #define N 51000 #define M 1100000 using namespace std; int n,m; struct node {int lc,rc,c; }tr[M];int len=0,rt[N]; void link(int &now,int l,int r,int c) {if(!now)now=++len;tr[now].c++;if(l==r)return ;int mid=(l+r)/2;if(c<=mid)link(tr[now].lc,l,mid,c);else link(tr[now].rc,mid+1,r,c); } void merge(int &x,int y) {if(!x){x=y;return ;}if(!y)return ;tr[x].c+=tr[y].c;merge(tr[x].lc,tr[y].lc);merge(tr[x].rc,tr[y].rc); } int calc(int x,int y,int k,int l,int r) {if(l==r)return 0;int mid=(l+r)/2;if(k<=mid)return calc(tr[x].lc,tr[y].lc,k,l,mid);else return calc(tr[x].rc,tr[y].rc,k,mid+1,r)+(tr[tr[y].lc].c-tr[tr[x].lc].c); } //快樂主席樹 int bst[N]; int lowbit(int x){return x&-x;} void change(int x,int c) {while(x<=n){bst[x]+=c;x+=lowbit(x);} } int getsum(int x) {int ans=0;while(x){ans+=bst[x];x-=lowbit(x);}return ans; } //樹狀數(shù)組 int ans[sN][N],id[N],ll[sN],rr[sN],cnt,a[N],cc; int sor[N],LS[N]; inline bool cmp(int x,int y){return a[x]<a[y];} void fenkuai(int l,int r) {ll[++cnt]=l;rr[cnt]=r;for(int i=l;i<=r;i++)id[i]=cnt;for(int i=1;i<=n;i++)bst[i]=0;for(int i=l;i<=n;i++){change(LS[i],1);ans[cnt][i]=ans[cnt][i-1]+(i-l+1-getsum(LS[i]));} } //處理塊的信息 inline int mymin(int x,int y){return x<y?x:y;} int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){sor[i]=i;scanf("%d",&a[i]);}sort(sor+1,sor+n+1,cmp);for(int i=1;i<=n;i++)a[sor[i]]==a[sor[i-1]]?LS[sor[i]]=LS[sor[i-1]]:LS[sor[i]]=i;//離散化for(int i=1;i<=n;i++){if(i*i>=n){cc=i;break;}}int now=0;for(now=1;now<=n;now+=cc)fenkuai(now,mymin(now+cc-1,n));//分塊for(int i=1;i<=n;i++){link(rt[i],1,n,LS[i]);merge(rt[i],rt[i-1]);}for(int i=1;i<=m;i++){int l,r;scanf("%d%d",&l,&r);if(l>r)l^=r^=l^=r; int x=id[l-1]+1;int answer=ans[x][r],ed=mymin(rr[x-1],r);if(l<=ed){for(int i=l;i<=ed;i++)answer+=calc(rt[i-1],rt[r],LS[i],1,n);}printf("%d\n",answer);}return 0; }求區(qū)間種類
時間限制: 1 Sec 內存限制: 128 MB 【題目描述】 給n（1<=n<=50000）個數(shù)，a[1],a[2],......,a[n]（0<=a[i]<=1000000），m（1<=m<=200000）個詢問。每個詢問包含兩個數(shù)l和r，求這個區(qū)間內不同數(shù)字的個數(shù)。 【輸入數(shù)據(jù)】 第一行兩個數(shù)n和m。 接下來一行n個數(shù)。 接下來m行，每行兩個數(shù)l和r。 【輸出數(shù)據(jù)】 m行，對應相應的詢問。 【輸入樣例】 6 1 2 3 4 3 5 3 1 2 3 5 2 6 【輸出樣例】 2 2 4這道題就是很明顯的不同的建樹方式。
這道題的思路是什么呢？
這個區(qū)間只有\(r\)個數(shù)的話，這道題很明顯會簡單不少，畢竟如果這個數(shù)字是最后出現(xiàn)的話，就給他設為\(1\)，否則為\(0\)，然后前綴和一下。
估計這樣的題目大部分人都會，但是放到這里就不會了。
前面的主席樹都是幫助我們把區(qū)間提出來，這里不一樣了，是在確定\(r\)的情況下\(logn\)的時間求前綴和。
也就是說假設這個點的權值出現(xiàn)過，那么我們在這棵主席樹不僅要將這個點設為\(1\)，還要去前面設為\(0\)。
這不就好起來了嗎？
#include<cstdio> #include<cstring> #define N 51000 #define M 1100000 using namespace std; struct node {int lc,rc,c; }tr[M];int len=0,rt[N]; void link(int &now,int l,int r,int c,int k) {if(!now)now=++len;tr[now].c+=k;if(l==r)return ;int mid=(l+r)/2;if(c<=mid)link(tr[now].lc,l,mid,c,k);else link(tr[now].rc,mid+1,r,c,k); } void merge(int &x,int y) {if(!x){x=y;return ;}if(!y)return ;tr[x].c+=tr[y].c;merge(tr[x].lc,tr[y].lc);merge(tr[x].rc,tr[y].rc); } int calc(int now,int x,int l,int r) {if(l==r)return tr[now].c&(l==x);int mid=(l+r)/2;if(x<=mid)return calc(tr[now].lc,x,l,mid);else return calc(tr[now].rc,x,mid+1,r)+tr[tr[now].lc].c; } int mp[M]; int n,m; int main() {scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);if(mp[x]){link(rt[i],1,n,mp[x],-1);link(rt[i],1,n,i,1);merge(rt[i],rt[i-1]);//有過這個點}else{link(rt[i],1,n,i,1);merge(rt[i],rt[i-1]);//新點}mp[x]=i;}scanf("%d",&m);for(int i=1;i<=m;i++){int l,r;scanf("%d%d",&l,&r);printf("%d\n",calc(rt[r],r,1,n)-calc(rt[r],l-1,1,n));//1-r的區(qū)間}return 0; }簡單詢問
時間限制: 2 Sec 內存限制: 128 MB 【題目描述】 給你n（1<=n<=100000）個數(shù)，并給出m（1<=m<=100000)個詢問，每次給出（x,y,k），就是讓你求x到y(tǒng)這個區(qū)間，有多少個數(shù)小于等于k。 【輸入數(shù)據(jù)】 第一行兩個數(shù)n，m。 第二行有n個數(shù)。 接下來一行，每行一個詢問。 【輸出數(shù)據(jù)】 m行，每行對應一個詢問。 【輸入樣例】 10 10 0 5 2 7 5 4 3 8 7 7 3 9 6 4 5 0 2 4 1 2 10 4 1 2 0 4 6 5 6 6 1 5 7 3 2 6 7 6 8 3 【輸出樣例】 4 0 0 3 1 2 0 1 5 1弱智題，直接跳權值主席樹不就行了？
#include<cstdio> #include<cstring> #include<algorithm> #define N 110000 #define M 3100000 using namespace std; struct node {int l,r,c; }tr[M];int root[N],cnt; int rt[N]; struct LSnode {int x,y; }ls[N]; int n,m; bool cmp(LSnode x,LSnode y){return x.x<y.x;}//離散化排序 void add(int &x,int l,int r,int k) {if(x==0)x=++cnt;tr[x].c++;if(l==r)return ;int mid=(l+r)/2;if(k<=mid)add(tr[x].l,l,mid,k);else add(tr[x].r,mid+1,r,k); } void merge(int &x,int y) {if(x==0){x=y;return ;}if(y==0)return ;tr[x].c+=tr[y].c;merge(tr[x].l,tr[y].l);merge(tr[x].r,tr[y].r); } int cale(int x,int y,int l,int r,int k) {if(l==r)return (tr[y].c-tr[x].c)&(l<k);//有一種情況是k>n，所以這里相當于一次特判int mid=(l+r)/2;if(k<=mid)return cale(tr[x].l,tr[y].l,l,mid,k);else return cale(tr[x].r,tr[y].r,mid+1,r,k)+(tr[tr[y].l].c-tr[tr[x].l].c); } int erfen(int x)//求在原數(shù)列中x的前驅的離散化值 {int l=1,r=n,mid,ans=-1;while(l<=r){mid=(l+r)/2;if(ls[mid].x<=x)ans=mid,l=mid+1;else r=mid-1;}return ans+1; } int main() { // freopen("1.in","r",stdin); // freopen("1.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&ls[i].x);ls[i].y=i;}sort(ls+1,ls+n+1,cmp);for(int i=1;i<=n;i++)rt[ls[i].y]=i;//離散化QMQfor(int i=1;i<=n;i++){add(root[i],1,n,rt[i]);merge(root[i],root[i-1]);}for(int i=1;i<=m;i++){int x,y,k;scanf("%d%d%d",&x,&y,&k);if(x>y)x^=y^=x^=y;printf("%d\n",cale(root[x-1],root[y],1,n,erfen(k)));}return 0; }簡單查詢
時間限制: 2 Sec 內存限制: 1024 MB 【題目描述】 給一個長度為n（1<=n<=100000）的序列a1,a2,a3,......,an（1<=ai<=100000）。 m（1<=m<=100000）組詢問，每次詢問一個區(qū)間[l,r]。 詢問是否存在一個數(shù)在[l,r]中出現(xiàn)的次數(shù)大于(r-l+1)/2。如果存在，輸出這個數(shù)，否則輸出0。 【輸入數(shù)據(jù)】 第一行兩個數(shù)n，m。 第二行n個數(shù)。 接下來m行，每行兩個數(shù)l,r，表示詢問[l,r]這個區(qū)間。 【輸出數(shù)據(jù)】 m行，每行對應一個詢問的答案。 【輸入樣例】 7 5 1 1 3 2 3 4 3 1 3 1 4 3 7 1 7 6 6 【輸出樣例】 1 0 3 0 4一樣權值主席樹
往下跳看左子樹有木有滿足條件，滿足去左兒子，不滿足看右兒子，這種數(shù)字在區(qū)間內最多只有一個，左右兒子都沒有直接輸出\(false\)
#include<cstdio> #include<cstring> #define N 110000 #define M 3100000 using namespace std; int xnum=0; inline int mymax(int x,int y){return x>y?x:y;} struct node {int lc,rc,c; }tr[M];int len=0,rt[N]; void link(int &now,int l,int r,int c) {if(!now)now=++len;tr[now].c++;if(l==r)return ;int mid=(l+r)/2;if(c<=mid)link(tr[now].lc,l,mid,c);else link(tr[now].rc,mid+1,r,c); } void merge(int &x,int y) {if(!x){x=y;return ;}if(!y)return ;tr[x].c+=tr[y].c;merge(tr[x].lc,tr[y].lc);merge(tr[x].rc,tr[y].rc); } int calc(int x,int y,int l,int r,int k) {if(l==r)return l;int mid=(l+r)>>1;if(tr[tr[y].lc].c-tr[tr[x].lc].c>k)calc(tr[x].lc,tr[y].lc,l,mid,k);//左兒子符不符合條件？else if(tr[tr[y].rc].c-tr[tr[x].rc].c>k)calc(tr[x].rc,tr[y].rc,mid+1,r,k);//右兒子符不符合條件？else return 0;//都不符合 } int n,m,a[N]; int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);xnum=mymax(xnum,a[i]);}for(int i=1;i<=n;i++)link(rt[i],1,xnum,a[i]),merge(rt[i],rt[i-1]);for(int i=1;i<=m;i++){int l,r;scanf("%d%d",&l,&r);printf("%d\n",calc(rt[l-1],rt[r],1,xnum,(r-l+1)>>1));}return 0; }矩陣主席樹大暴力！！！
時間限制: 1 Sec 內存限制: 128 MB 【問題描述】 給一個n*n的矩陣，給m個詢問，每次詢問(x1,y1)到(x2,y2)之間的第k小值。 這幾天做題遇到了一道這樣的題，原題是國家集訓隊梁盾的《矩陣乘法》，而原題必須要用整體二分，這對于一個天天寫主席樹的我非常痛苦，于是強迫癥的出了道強制在線弱化版本。【輸入文件】 第一行兩個數(shù)N,Q，表示矩陣大小和詢問組數(shù)； 接下來N行N列一共N*N個數(shù)，表示這個矩陣； 再接下來Q行每行5個數(shù)描述一個詢問：x1,y1,x2,y2,k表示找到以(x1,y1)為左上角、以(x2,y2)為右下角的子矩形中的第K小數(shù)。 這一組的x1,y1,x2,y2,k需異或lastans才可得到，lastans指的是上一組的答案，初始時為0。【輸出文件】 對于每組詢問輸出第K小的數(shù)。【輸入樣例】 2 2 2 1 3 4 1 2 1 2 1 0 0 3 3 2【輸出樣例】 1 3【數(shù)據(jù)范圍】 100%的數(shù)據(jù)：N<=100,Q<=40000。 保證異或后的點位置正確提示 強制在線一開始看到這道題，慌張的一批，打算在預處理上做功夫，打了個代碼，中途想起來合并了多次會炸掉，重新理清思路，發(fā)現(xiàn)\(n\)很小，也就是說我們可以在詢問上打暴力！
\((i,j)\)的主席樹表示的是在第\(j\)列中，\(1-i\)行的數(shù)字集合。（也是權值主席樹）
那么我們在查詢\((x1,y1),(x2,y2)\)的時候，將\(y1->y2\)列的\(x2\)行主席樹全部弄到一個\(list\)里面，表示加法的主席樹，而將\(x1\)行的主席樹丟到另外一個\(list\)里面，表示的是減法的主席樹，然后每一層查詢的時候暴力查，加個離散化，時間復雜度：\((Qnlogn)\)（注：\(logn^{2}=2logn\)，所以在這里省略了\(2\)）。
//在校園網(wǎng)上還能拿次優(yōu)解，笑死我了 #include<cstdio> #include<cstring> #include<algorithm> #define N 110 #define NN 11000 #define M 1100000 using namespace std; inline int mymax(int x,int y){return x>y?x:y;} struct node {int lc,rc,c; }tr[M];int len=0,rt[N][N]; void link(int &now,int l,int r,int c) {if(!now)now=++len;tr[now].c++;if(l==r)return ;int mid=(l+r)/2;if(c<=mid)link(tr[now].lc,l,mid,c);else link(tr[now].rc,mid+1,r,c); } void merge(int &x,int y) {if(!x){x=y;return ;}if(!y)return ;tr[x].c+=tr[y].c;merge(tr[x].lc,tr[y].lc);merge(tr[x].rc,tr[y].rc); } int li1[N],li2[N],top; inline void turn(int x) {if(x==0)for(int i=1;i<=top;i++)li1[i]=tr[li1[i]].lc,li2[i]=tr[li2[i]].lc;else for(int i=1;i<=top;i++)li1[i]=tr[li1[i]].rc,li2[i]=tr[li2[i]].rc; } int calc(int l,int r,int k) {if(l==r)return l;int mid=(l+r)/2,zz=0;for(int i=1;i<=top;i++)zz+=tr[tr[li1[i]].lc].c-tr[tr[li2[i]].lc].c;//暴力計算if(zz>=k){turn(0);return calc(l,mid,k);}else{turn(1);return calc(mid+1,r,k-zz);} } //主席樹 int n,m,nn,a[NN]; int id[NN],zhi[NN],cnt,ys[NN]; inline int num(int x,int y){return (x-1)*n+y-1;} inline bool cmp(int x,int y){return a[x]<a[y];} int main() {scanf("%d%d",&n,&m);nn=n*n-1;for(int i=0;i<=nn;i++){scanf("%d",&a[i]);id[i]=i;}sort(id,id+nn+1,cmp);a[0]=-999999999;for(int i=0;i<=nn;i++)zhi[id[i]]=(a[id[i]]==a[id[i-1]]?cnt:(ys[cnt+1]=a[id[i]],++cnt));for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)link(rt[i][j],1,cnt,zhi[num(i,j)]),merge(rt[i][j],rt[i-1][j]);//向上合并}int lastans=0;for(int i=1;i<=m;i++){int x1,y1,x2,y2,k;scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k);x1^=lastans;x2^=lastans;y1^=lastans;y2^=lastans;k^=lastans;top=0;for(int j=y1;j<=y2;j++)li1[++top]=rt[x2][j],li2[top]=rt[x1-1][j];//將要用到的主席樹塞進去lastans=ys[calc(1,cnt,k)];printf("%d\n",lastans);}return 0; }動態(tài)主席樹
講解
例題
時間限制: 1 Sec 內存限制: 256 MB 【問題描述】 給n(1<=n<=50000)個數(shù)字，進行m(1<=m<=10000)次操作，有兩種操作： Q l r k：詢問l到r第k小的數(shù)。 C x k：改變第x個數(shù)的值為k。 【輸入文件】 第一行為n和m。 接下來一行n個數(shù)。 接下來m行為m個操作。 【輸出文件】 遇到Q操作就輸出。 【輸入樣例】 5 3 1 2 3 4 5 Q 2 5 2 C 4 9 Q 3 5 3 【輸出樣例】 3 9算法講解
靜態(tài)主席樹就跟前綴和一樣，所以我們要修改就會很咕咕。
這是就有大佬瞬間想到，樹套樹不就行了？
對，就是樹套樹，樹狀數(shù)組套主席樹。
但是靜態(tài)主席樹也要保留，不如說樹套樹保存的是修改的結果。
保留靜態(tài)主席樹是為了空間更小一點，畢竟樹套樹的空間一次就是\(log^{2}n\)。
\(rt\)根數(shù)組要開兩倍，一個是靜態(tài)的，一個是與樹狀數(shù)組每個節(jié)點一一對應的。
而樹狀數(shù)組每個節(jié)點的權值主席樹維護的則是樹狀數(shù)組維護區(qū)域的數(shù)字。
當修改了\(i\)的值的時候，我們就在樹狀數(shù)組上查找維護\(i\)的節(jié)點，然后進入到主席樹中，將原來的數(shù)字的\(c\)減去\(1\)，將現(xiàn)在的數(shù)字增加\(1\)。
同時查詢的時候，用前綴和的方法，在樹狀數(shù)組中得出這個區(qū)間目前增加或減少了多少個數(shù)字。
更多的細節(jié)在代碼中標記出來了。
代碼
#include<cstdio> #include<cstring> #define N 51000 #define NN 110000 #define INF 10000000 #define M 5100000 using namespace std; int n,m; struct node {int lc,rc,c; }tr[M];int len; int a[N],rt[NN]; void link(int &x,int l,int r,int c,int k) {if(!x)x=++len;tr[x].c+=k;if(l==r)return ;int mid=(l+r)/2;if(c<=mid)link(tr[x].lc,l,mid,c,k);else link(tr[x].rc,mid+1,r,c,k); } inline int lowbit(int x){return x&-x;} int list[N],top,hehe[N],ti/*時間戳*/; inline void turn(int id)//細節(jié)1：為了在calc中跟著他一起跳設計的函數(shù)。 {for(int i=1;i<=top;i++){int x=list[i];if(id==0)a[x]=rt[x+n];else if(id==1)a[x]=tr[a[x]].lc;else if(id==2)a[x]=tr[a[x]].rc;} } inline void tiao(int x) {while(x){if(hehe[x]!=ti)list[++top]=x;hehe[x]=ti;/*這個點有木有跳過？*/x-=lowbit(x);} } void change(int x,int c,int k) {while(x<=n){link(rt[x+n],0,INF,c,k);x+=lowbit(x);} } int getsum(int x) {int ans=0;while(x){ans+=tr[tr[a[x]].lc].c;x-=lowbit(x);}return ans; } int calc(int x,int y,int ll,int rr,int l,int r,int k) {if(l==r)return l;int zhe=tr[tr[x].lc].c-tr[tr[y].lc].c+getsum(rr)-getsum(ll),mid=(l+r)/2;if(zhe<k){turn(2);return calc(tr[x].rc,tr[y].rc,ll,rr,mid+1,r,k-zhe);}else{turn(1);return calc(tr[x].lc,tr[y].lc,ll,rr,l,mid,k);} } int zhi[N]; void merge(int &x,int y) {if(!x){x=y;return ;}if(!y)return ;tr[x].c+=tr[y].c;merge(tr[x].lc,tr[y].lc);merge(tr[x].rc,tr[y].rc); } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&zhi[i]);link(rt[i],0,INF,zhi[i],1);merge(rt[i],rt[i-1]);}for(int i=1;i<=m;i++){char st[20];int x,y,z;scanf("%s",st+1);if(st[1]=='C'){scanf("%d%d",&x,&y);change(x,zhi[x],-1);zhi[x]=y;change(x,zhi[x],1);}else{scanf("%d%d%d",&x,&y,&z);if(x>y)x^=y^=x^=y;ti++;top=0;tiao(x-1);tiao(y);turn(0);printf("%d\n",calc(rt[y],rt[x-1],x-1,y,0,INF,z));}}return 0; }練習
不是動態(tài)主席樹的帶修題。
時間限制: 3 Sec 內存限制: 256 MB 【問題描述】 最近復習了一下帶修主席樹，于是出道水題給大家做，問題很簡單： 1、詢問區(qū)間k小值； 2、交換相鄰兩個數(shù)的權值。 【輸入文件】 第一行兩個數(shù)N,Q，表示序列大小和詢問組數(shù)； 第一行輸入n個數(shù)，表示原始序列。 接下來Q行， 當opt = 1時輸入三個數(shù) l，r，k詢問l~r區(qū)間第k小的數(shù) 當opt = 2時輸入一個數(shù)p 交換p和p + 1位置上的權值。 對于任何修改或詢問都需異或一個lastans， lastans表示上一個答案，初始值為0。 【輸出文件】 對于每組詢問輸出第K小的數(shù)。 【輸入樣例】 7 3 1 5 2 6 3 7 4 1 2 5 3 2 4 1 7 0 6 【輸出樣例】 5 3 【數(shù)據(jù)范圍】 如果被卡常，請使用#pragma GCC optimize("Ofast") 100%的數(shù)據(jù)：N<=500000,Q<=500000。千萬不要信出題人，我就打了動態(tài)主席樹。。。（滿嘴粗話...）
提一提：不用理\(x=n\)的情況。
我們會發(fā)現(xiàn)交換其實對后面的樹是沒有影響的，有影響的只是\(x\)號點的主席樹而已。
所以我們只要修改他就行了。
這里提供三種思路：
可持久化主席樹
很多大佬都會說主席樹就是用來可持久化的，仔細想想也有道理，畢竟\(link\)的可操作性讓他支持了可持久化。
例題
【題目描述】 給出一個長度為n（1<=n<=100000）的序列a[1],a[2],a[3]......,a[n]（1<=a[i]<=1000000000），有m個操作（1<=m<=100000）。 操作類型分為4種。 1 l r k：給l到r之間的數(shù)都加上k（1<=k<=10000）。 2 l r：詢問當前l(fā)到r的和。 3 l r h：詢問第h次修改（修改只指1操作）時l到r的和。 4 h：回到第h次修改的時候不再返回。（意思：接下來的修改是建立在第h次修改的模型上） 【輸入數(shù)據(jù)】 第一行兩個數(shù)n和m(n,m<=10^5)。 接下來一行n個數(shù)。 接下來m行m個操作。 【輸出數(shù)據(jù)】 每行對應一個詢問。 【輸入樣例】 10 5 1 2 3 4 5 6 7 8 9 10 2 4 4 2 1 10 2 2 4 1 3 6 3 2 2 4 【輸出樣例】 4 55 9 15某有練習啦，博主太菜啦，做題太少了。
思路
單點修改
首先考慮給一個點加上\(k\)的話要怎么做？
在不修改以前的操作的話要保留現(xiàn)在操作的節(jié)點，我們不可能說新建一個主席樹。
但是，我們想起來主席樹有一種騷操作就是一個兒子可以是許多人的兒子。（綠~~）
那么，也就是說我們只需要把涉及到需要修改\(c\)的節(jié)點新建，然后不需要的節(jié)點直接指向原來的就行了。
LOOK，圖中標著\(1,2\)的代表的就是每個時間代表的主席樹的根節(jié)點。
區(qū)間修改
博主博主，區(qū)間修改莫不是一次次單點修改。你怎么這么聰明。
區(qū)間修改，你一看到這個你一定要跳出一句代碼：
#define 區(qū)間修改 lazy我們也是一樣的，把會改變的點復制出來，但是如果發(fā)現(xiàn)一個點的區(qū)間與目前的完全吻合，就打上懶標記，在單點查詢的時候，再把查詢時需要用到的點建出來，而區(qū)間查詢也是如此，空間復雜度就是\(O((n+m)logc)\)（\(c\)為值域）。
但是，有更優(yōu)秀的做法，當我們在打上標記的時候，查詢時不建點，而是選擇個東西存起來，讓下面點知道有標記，但不等同于下傳，只是在記錄答案的時候用一下，當時我驕傲的跟機房大佬說就叫\(Monkey\) \(Lazy\)，然后就被大佬各種石錘：“這TM明明是永久化標記。”，然后就被大佬D爆了，QAQ。
這種方法還有一個更NB的地方，回到第\(h\)次操作我們是可以直接等于到那次的\(len\)實現(xiàn)暴力刪點，而前面那種做法就得很難受的打內存池了。
代碼
總體思路是這樣，但我寫的挺丑的，仔細想想會發(fā)現(xiàn)有更優(yōu)美的寫法，所以我還是比同機房的大佬差了這么一點點的時間。
//怎么感覺主席樹的代碼怎么加都是這么短 #include<cstdio> #include<cstring> #define N 110000 #define M 3100000 using namespace std; typedef long long LL; struct node {int lc,rc;LL c,la; }tr[M];int len,rt[N],cnt/*目前有幾次操作*/; int new_dian(){++len;tr[len].lc=tr[len].rc=tr[len].c=tr[len].la=0;return len;} LL ch;//你可以認為這是眾多函數(shù)中的輔助變量 void link(int &now,LL c,int l,int r) {if(!now)now=new_dian();tr[now].c+=ch;if(l==r)return ;LL mid=(l+r)/2;if(c<=mid)link(tr[now].lc,c,l,mid);else link(tr[now].rc,c,mid+1,r); } void change(int &now,int x,int l,int r,int ll,int rr) {if(!now)now=new_dian(),tr[now].c=tr[x].c,tr[now].la=tr[x].la;tr[now].c+=(rr-ll+1)*ch/*要增加多少值*/;if(l==ll && r==rr){tr[now].la+=ch;tr[now].lc=tr[x].lc;tr[now].rc=tr[x].rc;return ;}int mid=(l+r)/2;if(rr<=mid)change(tr[now].lc,tr[x].lc,l,mid,ll,rr),tr[now].rc=tr[x].rc;else if(mid+1<=ll)change(tr[now].rc,tr[x].rc,mid+1,r,ll,rr),tr[now].lc=tr[x].lc;else change(tr[now].lc,tr[x].lc,l,mid,ll,mid),change(tr[now].rc,tr[x].rc,mid+1,r,mid+1,rr); } //記錄答案 //這里其實是可以不用存在ch中的，可以直接(rr-ll+1)*lazy LL getsum(int now,int l,int r,int ll,int rr) {if(l==ll && r==rr)return tr[now].c+(r-l+1)*ch/*lazy非下傳下傳法*/;int mid=(l+r)/2;ch+=tr[now].la;if(rr<=mid)return getsum(tr[now].lc,l,mid,ll,rr);else if(mid+1<=ll)return getsum(tr[now].rc,mid+1,r,ll,rr);else{LL hehe=ch,ans=getsum(tr[now].lc,l,mid,ll,mid);ch=hehe;return getsum(tr[now].rc,mid+1,r,mid+1,rr)+ans;} } int n,m; int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%lld",&ch);link(rt[0],i,1,n);}for(int i=1;i<=m;i++){int type,x,y,z;scanf("%d",&type);if(type==1){scanf("%d%d%lld",&x,&y,&ch);rt[++cnt]=0;change(rt[cnt],rt[cnt-1],1,n,x,y);}else if(type==2){scanf("%d%d",&x,&y);ch=0;printf("%lld\n",getsum(rt[cnt],1,n,x,y));}else if(type==3){scanf("%d%d%d",&x,&y,&z);ch=0;printf("%lld\n",getsum(rt[z],1,n,x,y));}else{scanf("%d",&x);if(x!=cnt)len=rt[x+1]-1;cnt=x;}}return 0; }小結
有人也許會問可持久化帶修區(qū)間第\(k\)小的\(rt\)為什么要開兩維，是不是我學了個假的可持久化，沒有。博主很良心的
其實這個問題我也問了下機房的大佬，他是這么回答我的：
主席樹支持可持久化原本就是因為他可以支持共用節(jié)點，比如\(FHQ\)就是一個活生生的例子。
而區(qū)間第\(k\)小原本就是利用了主席樹的可持久化特性，用類似前綴和的方法做的，本身就相當于調用了主席樹可持久化的性質，再套個可持久化不就是雙重可持久化，那二維不也很正常嘛？
所以大佬還是大佬呀。
//怎么感覺主席樹的代碼怎么加都是這么短 #include<cstdio> #include<cstring> #define N 110000 #define M 3100000 using namespace std; typedef long long LL; struct node {int lc,rc;LL c,la; }tr[M];int len,rt[N],cnt/*目前有幾次操作*/; int new_dian(){++len;tr[len].lc=tr[len].rc=tr[len].c=tr[len].la=0;return len;} LL ch;//你可以認為這是眾多函數(shù)中的輔助變量 void link(int &now,LL c,int l,int r) {if(!now)now=new_dian();tr[now].c+=ch;if(l==r)return ;LL mid=(l+r)/2;if(c<=mid)link(tr[now].lc,c,l,mid);else link(tr[now].rc,c,mid+1,r); } void change(int &now,int x,int l,int r,int ll,int rr) {if(!now)now=new_dian(),tr[now].c=tr[x].c,tr[now].la=tr[x].la;tr[now].c+=(rr-ll+1)*ch/*要增加多少值*/;if(l==ll && r==rr){tr[now].la+=ch;tr[now].lc=tr[x].lc;tr[now].rc=tr[x].rc;return ;}int mid=(l+r)/2;if(rr<=mid)change(tr[now].lc,tr[x].lc,l,mid,ll,rr),tr[now].rc=tr[x].rc;else if(mid+1<=ll)change(tr[now].rc,tr[x].rc,mid+1,r,ll,rr),tr[now].lc=tr[x].lc;else change(tr[now].lc,tr[x].lc,l,mid,ll,mid),change(tr[now].rc,tr[x].rc,mid+1,r,mid+1,rr); } //記錄答案 //這里其實是可以不用存在ch中的，可以直接(rr-ll+1)*lazy LL getsum(int now,int l,int r,int ll,int rr) {if(l==ll && r==rr)return tr[now].c+(r-l+1)*ch/*lazy非下傳下傳法*/;int mid=(l+r)/2;ch+=tr[now].la;if(rr<=mid)return getsum(tr[now].lc,l,mid,ll,rr);else if(mid+1<=ll)return getsum(tr[now].rc,mid+1,r,ll,rr);else{LL hehe=ch,ans=getsum(tr[now].lc,l,mid,ll,mid);ch=hehe;return getsum(tr[now].rc,mid+1,r,mid+1,rr)+ans;} } int n,m; int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%lld",&ch);link(rt[0],i,1,n);}for(int i=1;i<=m;i++){int type,x,y,z;scanf("%d",&type);if(type==1){scanf("%d%d%lld",&x,&y,&ch);rt[++cnt]=0;change(rt[cnt],rt[cnt-1],1,n,x,y);}else if(type==2){scanf("%d%d",&x,&y);ch=0;printf("%lld\n",getsum(rt[cnt],1,n,x,y));}else if(type==3){scanf("%d%d%d",&x,&y,&z);ch=0;printf("%lld\n",getsum(rt[z],1,n,x,y));}else{scanf("%d",&x);if(x!=cnt)len=rt[x+1]-1;cnt=x;}}return 0; }小結
有人也許會問可持久化帶修區(qū)間第\(k\)小的\(rt\)為什么要開兩維，是不是我學了個假的可持久化，沒有。博主很良心的
其實這個問題我也問了下機房的大佬，他是這么回答我的：
主席樹支持可持久化原本就是因為他可以支持共用節(jié)點，比如\(FHQ\)就是一個活生生的例子。
而區(qū)間第\(k\)小原本就是利用了主席樹的可持久化特性，用類似前綴和的方法做的，本身就相當于調用了主席樹可持久化的性質，再套個可持久化不就是雙重可持久化，那二維不也很正常嘛？
所以大佬還是大佬呀。
查錯
其實之前的話存在一點錯誤。
不管你用什么方法建樹，比如從前往后合并，或者是兩個兩個合并，只要區(qū)間永遠不重復就可以了，并且只合并\(n-1\)次，并且每個點只被合并給別人一次，我們就可以保證時間復雜度是\(O(nlogn)\)的。
為什么，我們考慮進入一點的有效情況（兩個主席樹都有這個點），而我的證明只限于一種情況，就是當集合合并到另外一個大的集合時，以后都只有這個大集合帶著這個小集合（或者一些特殊情況），所以以后這個大集合的被合并的話，只要這個點被有效訪問，這個集合就會進一步變大，而一個點只要區(qū)域內的數(shù)字都被添加了，這個點就不會被有效訪問，也就是說每層的點只會有效訪問\(n\)次，\(log\)層，時間復雜度自然就是\(O(nlogn)\)。
但是，還是有無效訪問的，常數(shù)比較小的自然還是從左往右合并啦。
轉載于:https://www.cnblogs.com/zhangjianjunab/p/11346849.html
總結
- 上一篇： 算法学习：最小圆覆盖
- 下一篇： 【FJOI2015】最小覆盖双圆问题