主席樹學習筆記

---

說在前邊：

之前了解過主席樹的基礎的思想，但是沒有系統學習過，所以打算通過一些題目重新學習。

---

POJ2104

題意：靜態區間查詢 k-th number

思路：對每個位置開一顆權值線段樹，維護前綴區間每個數字出現的次數，這樣只需實現兩棵線段樹相減，利用簡單的二分思想即可求出 k-th number。

問題：內存不足以開n顆線段樹，時間自然也不夠。

解決方法：注意到相鄰兩個位置，只會一個位置不同，那么發生改變的只有包含這個位置的一條鏈。那建樹時，可以把新建這一條鏈，其他的邊都接在上一個位置的線段樹上即可。通過這樣的方式我們保存了歷史版本的線段樹。

#include <iostream> #include <cstdio> #include <algorithm> #define rep(i,a,b) for(int i=a;i<=b;++i) typedef long long ll; const int N = 1e5 + 100; using namespace std; int n, m; struct node{ll v; int id;}a[N]; bool cmp(node a,node b){return a.v<b.v;} int root[N], fid[N], tot; struct tree{int l,r,num;}T[N*20]; void ins(int &x,int p,int l,int r) {T[++tot]=T[x]; x = tot; ++T[x].num;if(l == r) return;int mid = (l + r) >> 1;if(p <= mid) ins(T[x].l,p,l,mid);else ins(T[x].r,p,mid+1,r); } int ask(int pl,int pr,int k,int l,int r) {if(l==r)return l;int mid = (l+r)>>1;if(T[T[pr].l].num-T[T[pl].l].num>=k) return ask(T[pl].l,T[pr].l,k,l,mid);else return ask(T[pl].r, T[pr].r,k-(T[T[pr].l].num-T[T[pl].l].num),mid+1,r); } int main() {scanf("%d%d",&n,&m);rep(i,1,n)scanf("%lld",&a[i].v),a[i].id=i;sort(a+1,a+1+n,cmp);rep(i,1,n)fid[a[i].id]=i;rep(i,1,n)root[i]=root[i-1],ins(root[i],fid[i],1,n);rep(i,1,m) {int l,r,k;scanf("%d%d%d",&l,&r,&k);printf("%lld\n",a[ask(root[l-1],root[r],k,1,n)]);}return 0; }

---

BZOJ1901

題意：動態區間查詢 k-th number

思路：利用靜態主席樹思想維護權值線段樹的前綴和，而本題要維護動態前綴和，那就可以想到利用樹狀數組，維護動態前綴和。

實現：

• 實現單點修改操作：主席樹的關鍵 - 保存歷史版本，所以顯然不能在已經建好的樹上操作。需要新開一個節點作為這個位置新的根，在這個位置原來的位置上加一條新鏈。這個操作我們在實現靜態前綴和的時候已經掌握了。前綴和時第i棵樹是由第i-1棵樹修改得到的，而修改操作中，新的這棵樹是由它原先這個位置的值修改得到的。他們的本質都是修改操作。
• 實現動態前綴和：T[i]表示樹狀數組中的下表為i代表的區間。利用主席樹維護每個位置，前綴和利用樹狀數組來完成

//bzoj1901 ac #include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define pb push_back #define mem(W) memset(W,0,sizeof(W)) const int N = 6e4+5; const int M = 1e4+5; inline int read() {char c=getchar(); int x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } using namespace std; int n,m,a[N]; vector<int> v; int num; int id(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1;} struct node{int l,r,k;bool opt;} A[M]; struct tree{int l,r,num;}T[N*200]; int root[N],tot; void ins(int &rt,int pre,int p,int l,int r,int d) {rt=++tot;T[rt]=T[pre];T[rt].num+=d;if(l==r)return;int mid=(l+r)>>1;if(p<=mid) ins(T[rt].l,T[pre].l,p,l,mid,d);else ins(T[rt].r,T[pre].r,p,mid+1,r,d); } void update(int p,int v) {for(int i=p;i<=n;i+=(i&-i)) ins(root[i],root[i],id(a[p]),1,num,-1);for(int i=p;i<=n;i+=(i&-i)) ins(root[i],root[i],id(v),1,num,1);a[p]=v; } int L[N],R[N],cntl,cntr; int qury(int l,int r,int k) {if(l==r)return l;int mid=(l+r)>>1,sum=0;rep(i,1,cntr) sum+=T[T[R[i]].l].num;rep(i,1,cntl) sum-=T[T[L[i]].l].num;if(k<=sum) {rep(i,1,cntl) L[i]=T[L[i]].l;rep(i,1,cntr) R[i]=T[R[i]].l;return qury(l,mid,k);}else {rep(i,1,cntl) L[i]=T[L[i]].r;rep(i,1,cntr) R[i]=T[R[i]].r;return qury(mid+1,r,k-sum);} } int main() {int K;scanf("%d",&K);while(K--) {char s[5];scanf("%d%d",&n,&m); v.clear(); tot=0; mem(root);mem(T);rep(i,1,n) scanf("%d",a+i), v.pb(a[i]);rep(i,1,m) {scanf(" %s",s);if(s[0]=='Q')A[i].opt=1,scanf("%d%d%d",&A[i].l,&A[i].r,&A[i].k);else A[i].opt=0,scanf("%d%d",&A[i].l,&A[i].r),v.pb(A[i].r);}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());num = v.size();rep(i,1,n) for(int j=i;j<=n;j+=(j&(-j))) ins(root[j],root[j],id(a[i]),1,num,1);rep(ti,1,m) {if(A[ti].opt) {cntl=cntr=0;for(int i=A[ti].l-1;i;i-=(i&(-i))) L[++cntl]=root[i];for(int i=A[ti].r;i;i-=(i&(-i))) R[++cntr]=root[i];printf("%d\n",v[qury(1,num,A[ti].k)-1]);}elseupdate(A[ti].l,A[ti].r);}}return 0; }

---

ZOJ2112

題意：與BZOJ1901相同，動態區間查詢 k-th number，內存限制

思路：如果用上題的做法，內存無法接受。那么思考有什么地方可以減少節點的數量。注意到一開始讀入的n個數，完全可以與后面的操作獨立開，一顆靜態的主席樹，一顆用來修改，查詢時將兩棵樹的信息合并即可。這樣這n棵數的空間復雜度少了一個樹狀數組的log

//bzoj1901 ac //zoj2112 ac #include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define pb push_back #define mem(W) memset(W,0,sizeof(W)) const int N = 6e4+5; const int M = 1e4+5; inline int read() {char c=getchar(); int x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } using namespace std; int n,m,a[N]; vector<int> v; int num; int id(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1;} struct node{int l,r,k;bool opt;} A[M]; struct tree{int l,r,num;}T[N*32]; int root[N],root0[N],tot; void ins(int &rt,int pre,int p,int l,int r,int d) {rt=++tot;T[rt]=T[pre];T[rt].num+=d;if(l==r)return;int mid=(l+r)>>1;if(p<=mid) ins(T[rt].l,T[pre].l,p,l,mid,d);else ins(T[rt].r,T[pre].r,p,mid+1,r,d); } void update(int p,int v) {for(int i=p;i<=n;i+=(i&-i)) ins(root[i],root[i],id(a[p]),1,num,-1);for(int i=p;i<=n;i+=(i&-i)) ins(root[i],root[i],id(v),1,num,1);a[p]=v; } int L[N],R[N],cntl,cntr; int qury(int l,int r,int ls,int rs,int k) {if(l==r)return l;int mid=(l+r)>>1,sum=0;rep(i,1,cntr) sum+=T[T[R[i]].l].num;rep(i,1,cntl) sum-=T[T[L[i]].l].num;sum += (T[T[rs].l].num-T[T[ls].l].num);if(k<=sum) {rep(i,1,cntl) L[i]=T[L[i]].l;rep(i,1,cntr) R[i]=T[R[i]].l;return qury(l,mid,T[ls].l,T[rs].l,k);}else {rep(i,1,cntl) L[i]=T[L[i]].r;rep(i,1,cntr) R[i]=T[R[i]].r;return qury(mid+1,r,T[ls].r,T[rs].r,k-sum);} } int main() {int K;scanf("%d",&K);while(K--) {char s[5];scanf("%d%d",&n,&m); v.clear(); tot=0; mem(root);mem(T);rep(i,1,n) scanf("%d",a+i), v.pb(a[i]);rep(i,1,m) {scanf(" %s",s);if(s[0]=='Q')A[i].opt=1,scanf("%d%d%d",&A[i].l,&A[i].r,&A[i].k);else A[i].opt=0,scanf("%d%d",&A[i].l,&A[i].r),v.pb(A[i].r);}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());num = v.size();rep(i,1,n) root0[i]=root0[i-1],ins(root0[i],root0[i],id(a[i]),1,num,1);rep(ti,1,m) {if(A[ti].opt) {cntl=cntr=0;for(int i=A[ti].l-1;i;i-=(i&(-i))) L[++cntl]=root[i];for(int i=A[ti].r;i;i-=(i&(-i))) R[++cntr]=root[i];printf("%d\n",v[qury(1,num,root0[A[ti].l-1],root0[A[ti].r],A[ti].k)-1]);}elseupdate(A[ti].l,A[ti].r);}}return 0; }

---

洛谷P3567

題意：靜態區間查詢出現大于(r-l+1)/2次的數。

思路：出現超過(r-l+1)/2次的數至多有一個，所以直接在靜態主席樹上查詢，區間內大于(r-l+1)/2的位置即可，與靜態區間第k大的區別就是遞歸到右邊時，不修改k值

#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define pb push_back typedef long long ll; const int N = 500000+100; using namespace std; int n,m,a[N]; struct chair_tree{int l,r,num;}T[N*30]; int root[N],tot; void ins(int &rt,int pre,int p,int d,int l,int r) {rt=++tot;T[rt]=T[pre];T[rt].num+=d;if(l==r)return;int mid = (l+r)>>1;if(p<=mid) ins(T[rt].l,T[pre].l,p,d,l,mid);else ins(T[rt].r,T[pre].r,p,d,mid+1,r); } int ask(int rtl,int rtr,int l,int r,int X) {if(l==r) return l;int mid = (l+r)>>1;if((T[T[rtr].l].num-T[T[rtl].l].num)*2>X) return ask(T[rtl].l,T[rtr].l,l,mid,X);else if((T[T[rtr].r].num-T[T[rtl].r].num)*2>X) return ask(T[rtl].r,T[rtr].r,mid+1,r,X);else return 0; } int main() {scanf("%d%d",&n,&m);rep(i,1,n)scanf("%d",&a[i]);rep(i,1,n)ins(root[i],root[i-1],a[i],1,1,n);rep(i,1,m) {int l,r;scanf("%d%d",&l,&r);printf("%d\n",ask(root[l-1],root[r],1,n,r-l+1));}return 0; }

---

BZOJ2588

題意：無修改樹上查詢路徑上的第k大

思路：考慮如何樹上主席樹，對每個從根節點延伸出的鏈，建前綴的主席樹。那么這條路徑上就是：
\(u的值 + v的值 - lca(u,v)的值 - fa[lca(u,v)]的值\), 其他與靜態區間第k大一致。

lca求法：倍增5260 ms，樹剖3900 ms

倍增lca

#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define pb push_back typedef long long ll; const int N = 1e5 + 100; using namespace std; int n,m,a[N]; vector<int> v; int num; int id(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1;} struct edge{int e,nxt;}E[N<<1]; int h[N],cc; void add(int u,int v) {++cc;E[cc].e=v;E[cc].nxt=h[u];h[u]=cc; } int fa[N][20],dep[N]; int lca(int u,int v) {if(dep[u]<dep[v])swap(u,v);for(int i=17;i>=0;--i)if(dep[fa[u][i]]>=dep[v])u=fa[u][i];if(u==v)return u;for(int i=17;i>=0;--i) {if(fa[v][i]!=fa[u][i])v=fa[v][i],u=fa[u][i];}return fa[v][0]; } struct chair_tree{int l,r,num;}T[N*20]; int root[N], tot; void ins(int &rt,int pre,int p,int d,int l,int r) {rt=++tot;T[rt]=T[pre];T[rt].num+=d;if(l==r)return;int mid=(l+r)>>1;if(p<=mid) ins(T[rt].l,T[pre].l,p,d,l,mid);else ins(T[rt].r,T[pre].r,p,d,mid+1,r); } int vis[N]; void build_T() {queue<int> q;q.push(0);vis[0]=1;dep[0]=0;while(!q.empty()) {int u=q.front();q.pop();for(int i=1;i<=17;i++) fa[u][i]=fa[fa[u][i-1]][i-1];for(int i=h[u];~i;i=E[i].nxt) {int v=E[i].e;if(!vis[v]) {vis[v]=1;fa[v][0]=u;dep[v]=dep[u]+1;ins(root[v],root[u],id(a[v]),1,1,num);q.push(v);}}} } int ask(int ur,int vr,int lcar,int lcafr,int k,int l,int r) {if(l==r) return l;int mid=(l+r)>>1,sum=0;sum = T[T[ur].l].num - T[T[lcar].l].num + T[T[vr].l].num - T[T[lcafr].l].num;if(sum>=k) return ask(T[ur].l,T[vr].l,T[lcar].l,T[lcafr].l,k,l,mid);else return ask(T[ur].r,T[vr].r,T[lcar].r,T[lcafr].r,k-sum,mid+1,r); } int main() {scanf("%d%d",&n,&m);rep(i,1,n) scanf("%d",&a[i]),v.pb(a[i]);sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());num = v.size();memset(h,-1,sizeof(h));rep(i,1,n-1) {int u,v;scanf("%d%d",&u,&v);add(u,v),add(v,u);}a[0]=0; add(0,1),add(1,0);build_T();int lastans=0;rep(ti,1,m) {int x,y,k;scanf("%d%d%d",&x,&y,&k);x^=lastans;lastans = v[ask(root[x],root[y],root[lca(x,y)],root[fa[lca(x,y)][0]],k,1,num)-1];printf("%d\n",lastans);}return 0; }

樹剖lca

#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define pb push_back typedef long long ll; const int N = 1e5 + 100; using namespace std; int n,m,a[N]; vector<int> v; int num; int id(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1;} struct chair_tree{int l,r,num;}T[N*50]; int root[N], tot; void ins(int &rt,int pre,int p,int d,int l,int r) {rt=++tot;T[rt]=T[pre];T[rt].num+=d;if(l==r)return;int mid=(l+r)>>1;if(p<=mid) ins(T[rt].l,T[pre].l,p,d,l,mid);else ins(T[rt].r,T[pre].r,p,d,mid+1,r); }struct edge{int e,nxt;}E[N<<1]; int h[N],cc; void add(int u,int v) {++cc;E[cc].e=v;E[cc].nxt=h[u];h[u]=cc; } int dep[N],fa[N],son[N],sz[N],top[N]; void dfs1(int u,int pre,int d) {dep[u]=d;fa[u]=pre;sz[u]=1;for(int i=h[u];~i;i=E[i].nxt) {int v=E[i].e;if(v!=pre) {ins(root[v],root[u],id(a[v]),1,1,num);dfs1(v,u,d+1);sz[u]+=sz[v];if(son[u]==-1||sz[v]>sz[son[u]]) son[u]=v;}} } void dfs2(int u,int sp) {top[u]=sp;if(son[u]==-1)return;dfs2(son[u],sp);for(int i=h[u];~i;i=E[i].nxt) {int v=E[i].e;if(v!=fa[u]&&v!=son[u])dfs2(v,v);} } void init() {memset(son,-1,sizeof(son));dfs1(0,-1,1);dfs2(0,0); } int lca(int u,int v) {while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]])swap(u,v);u=fa[top[u]];}if(dep[u]>dep[v])swap(u,v);return u; } int ask(int ur,int vr,int lcar,int lcafr,int k,int l,int r) {if(l==r) return l;int mid=(l+r)>>1,sum=0;sum = T[T[ur].l].num - T[T[lcar].l].num + T[T[vr].l].num - T[T[lcafr].l].num;if(sum>=k) return ask(T[ur].l,T[vr].l,T[lcar].l,T[lcafr].l,k,l,mid);else return ask(T[ur].r,T[vr].r,T[lcar].r,T[lcafr].r,k-sum,mid+1,r); } int main() {scanf("%d%d",&n,&m);rep(i,1,n) scanf("%d",&a[i]),v.pb(a[i]);sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());num = v.size();memset(h,-1,sizeof(h));rep(i,1,n-1) {int u,v;scanf("%d%d",&u,&v);add(u,v),add(v,u);}a[0]=0; add(0,1),add(1,0);init();int lastans=0;rep(ti,1,m) {int x,y,k;scanf("%d%d%d",&x,&y,&k);x^=lastans;lastans = v[ask(root[x],root[y],root[lca(x,y)],root[fa[lca(x,y)]],k,1,num)-1];if(ti!=m)printf("%d\n",lastans);else printf("%d",lastans);}return 0; }

---

洛谷P4175

題意：帶修改樹上查詢路徑上的第k大

思路1：在前一題的基礎上，考慮如何修改。當一個節點更新之后受影響的只有它的子樹，處理dfs序，對于節點i相當于要修改\([ L[i],R[i] ]\)這個區間的值，樹狀數組差分實現區間修改單點查詢。

詢問方法：看大佬Blog都是，直接將[1,L[i]]當作樹上根到節點i的前綴，套用常規靜態的方法。講道理，感覺很奇怪。。。但還是過了

思路2：把修改改成單點修改，樹剖的做法，也可以過，這個正確性很顯然了。

做法1：

#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define pb push_back typedef long long ll; inline int read() {char c=getchar();int x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } using namespace std; const int N = 1e5 + 100; struct Q{int a,b,k;}q[N]; struct edge{int e,nxt;}E[N<<1]; int h[N],cc; void add(int u,int v) {++cc;E[cc].e=v;E[cc].nxt=h[u];h[u]=cc;} int n,m,a[N]; vector<int> mp; int num; int id(int x){return lower_bound(mp.begin(),mp.end(),x)-mp.begin()+1;}struct chiarman{int l,r,num;}T[N*200]; int tot,rt[N],rtc[N]; void ins(int &rt,int pre,int p,int d,int l,int r) {rt=++tot;T[rt]=T[pre];T[rt].num+=d;if(l==r)return;int mid=(l+r)>>1;if(p<=mid) ins(T[rt].l,T[pre].l,p,d,l,mid);else ins(T[rt].r,T[pre].r,p,d,mid+1,r); }int dep[N],fa[N],son[N],sz[N],top[N],tid[N],L[N],R[N],pos; void dfs1(int u,int pre,int d) {dep[u]=d;fa[u]=pre;sz[u]=1;for(int i=h[u];~i;i=E[i].nxt) {int v=E[i].e;if(v!=pre) {dfs1(v,u,d+1);sz[u]+=sz[v];if(son[u]==-1||sz[v]>sz[son[u]]) son[u]=v;}} } void dfs2(int u,int sp) {top[u]=sp;L[u]=tid[u]=++pos;if(son[u]==-1)return;dfs2(son[u],sp);for(int i=h[u];~i;i=E[i].nxt) {int v=E[i].e;if(v!=fa[u]&&v!=son[u])dfs2(v,v);}R[u]=pos; } void init_tp() {memset(son,-1,sizeof(son));dfs1(1,0,1);dfs2(1,1); } int lca(int u,int v) {while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]])swap(u,v);u=fa[top[u]];}if(dep[u]>dep[v])swap(u,v);return u; }void build(int u){if(u==-1) return;ins(rt[u],rt[fa[u]],id(a[u]),1,1,num);build(son[u]);for(int i=h[u];~i;i=E[i].nxt)if(E[i].e!=fa[u]&&E[i].e!=son[u]) build(E[i].e); }void B_add(int x,int p,int d){for(int i=x;i<=pos;i+=(i&-i)) ins(rtc[i],rtc[i],p,d,1,num); }vector<int> A,B; int ck(int k) {int sum=0;rep(i,0,A.size()-1)sum+=T[A[i]].num;rep(i,0,B.size()-1)sum-=T[B[i]].num;return (sum>=k); } int qury(int l,int r,int k) {if(l==r)return l;int mid=(l+r)>>1,sum=0;rep(i,0,A.size()-1)sum+=T[T[A[i]].r].num;rep(i,0,B.size()-1)sum-=T[T[B[i]].r].num;if(sum>=k) {rep(i,0,A.size()-1)A[i]=T[A[i]].r;rep(i,0,B.size()-1)B[i]=T[B[i]].r;return qury(mid+1,r,k);}else {rep(i,0,A.size()-1)A[i]=T[A[i]].l;rep(i,0,B.size()-1)B[i]=T[B[i]].l;return qury(l,mid,k-sum);} } int cal() {int sum=0;rep(i,0,A.size()-1)sum+=T[T[A[i]].r].num;rep(i,0,B.size()-1)sum-=T[T[B[i]].r].num;return sum; } void chai(int u,int v) {while(top[u]!=top[v]) {if(dep[top[u]]<dep[top[v]]) swap(u,v);for(int i=tid[u];i;i-=(i&-i))A.pb(rtc[i]);for(int i=tid[top[u]]-1;i;i-=(i&-i))B.pb(rtc[i]);u=fa[top[u]];}if(dep[u]>dep[v])swap(u,v);for(int i=tid[v];i;i-=(i&-i))A.pb(rtc[i]);for(int i=tid[u]-1;i;i-=(i&-i))B.pb(rtc[i]);return ; }void ask(int u,int v,int k) {int p=lca(u,v);A.clear();B.clear();A.pb(rt[u]),A.pb(rt[v]),B.pb(rt[p]),B.pb(rt[fa[p]]);chai(u,v);if(!ck(k)) {puts("invalid request!");return;}printf("%d\n",mp[qury(1,num,k)-1]);return; } int main() {scanf("%d%d",&n,&m);memset(h,-1,sizeof(h));memset(son,-1,sizeof(son));rep(i,1,n) a[i] = read(), mp.pb(a[i]);rep(i,1,n-1) {int u=read(),v=read();add(u,v),add(v,u);}rep(i,1,m) {q[i].k=read(),q[i].a=read(),q[i].b=read();if(q[i].k==0)mp.pb(q[i].b);}sort(mp.begin(),mp.end()); mp.erase(unique(mp.begin(),mp.end()),mp.end());num = mp.size();init_tp();build(1);rep(i,1,m) {if(q[i].k==0) {B_add(tid[q[i].a],id(a[q[i].a]),-1);a[q[i].a]=q[i].b;B_add(tid[q[i].a],id(a[q[i].a]),1);}else {ask(q[i].a,q[i].b,q[i].k);}}return 0; }

做法2：

#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define pb push_back typedef long long ll; inline int read() {char c=getchar();int x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } using namespace std; const int N = 1e5 + 100; struct Q{int a,b,k;}q[N]; struct edge{int e,nxt;}E[N<<1]; int h[N],cc; void add(int u,int v) {++cc;E[cc].e=v;E[cc].nxt=h[u];h[u]=cc;} int n,m,a[N]; vector<int> mp; int num; int id(int x){return lower_bound(mp.begin(),mp.end(),x)-mp.begin()+1;}struct chiarman{int l,r,num;}T[N*200]; int tot,rt[N],rtc[N]; void ins(int &rt,int pre,int p,int d,int l,int r) {rt=++tot;T[rt]=T[pre];T[rt].num+=d;if(l==r)return;int mid=(l+r)>>1;if(p<=mid) ins(T[rt].l,T[pre].l,p,d,l,mid);else ins(T[rt].r,T[pre].r,p,d,mid+1,r); }int dep[N],fa[N],son[N],sz[N],top[N],tid[N],L[N],R[N],pos; void dfs1(int u,int pre,int d) {dep[u]=d;fa[u]=pre;sz[u]=1;for(int i=h[u];~i;i=E[i].nxt) {int v=E[i].e;if(v!=pre) {dfs1(v,u,d+1);sz[u]+=sz[v];if(son[u]==-1||sz[v]>sz[son[u]]) son[u]=v;}} } void dfs2(int u,int sp) {top[u]=sp;L[u]=tid[u]=++pos;if(son[u]==-1)return;dfs2(son[u],sp);for(int i=h[u];~i;i=E[i].nxt) {int v=E[i].e;if(v!=fa[u]&&v!=son[u])dfs2(v,v);}R[u]=pos; } void init_tp() {memset(son,-1,sizeof(son));dfs1(1,0,1);dfs2(1,1); } int lca(int u,int v) {while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]])swap(u,v);u=fa[top[u]];}if(dep[u]>dep[v])swap(u,v);return u; }void build(int u){if(u==-1) return;ins(rt[u],rt[fa[u]],id(a[u]),1,1,num);build(son[u]);for(int i=h[u];~i;i=E[i].nxt)if(E[i].e!=fa[u]&&E[i].e!=son[u]) build(E[i].e); }void B_add(int x,int p,int d){for(int i=x;i<=pos;i+=(i&-i)) ins(rtc[i],rtc[i],p,d,1,num); }vector<int> A,B; int ck(int k) {int sum=0;rep(i,0,A.size()-1)sum+=T[A[i]].num;rep(i,0,B.size()-1)sum-=T[B[i]].num;return (sum>=k); } int qury(int l,int r,int k) {if(l==r)return l;int mid=(l+r)>>1,sum=0;rep(i,0,A.size()-1)sum+=T[T[A[i]].r].num;rep(i,0,B.size()-1)sum-=T[T[B[i]].r].num;if(sum>=k) {rep(i,0,A.size()-1)A[i]=T[A[i]].r;rep(i,0,B.size()-1)B[i]=T[B[i]].r;return qury(mid+1,r,k);}else {rep(i,0,A.size()-1)A[i]=T[A[i]].l;rep(i,0,B.size()-1)B[i]=T[B[i]].l;return qury(l,mid,k-sum);} } int cal() {int sum=0;rep(i,0,A.size()-1)sum+=T[T[A[i]].r].num;rep(i,0,B.size()-1)sum-=T[T[B[i]].r].num;return sum; } void chai(int u,int v) {while(top[u]!=top[v]) {if(dep[top[u]]<dep[top[v]]) swap(u,v);for(int i=tid[u];i;i-=(i&-i))A.pb(rtc[i]);for(int i=tid[top[u]]-1;i;i-=(i&-i))B.pb(rtc[i]);u=fa[top[u]];}if(dep[u]>dep[v])swap(u,v);for(int i=tid[v];i;i-=(i&-i))A.pb(rtc[i]);for(int i=tid[u]-1;i;i-=(i&-i))B.pb(rtc[i]);return ; }void ask(int u,int v,int k) {int p=lca(u,v);A.clear();B.clear();A.pb(rt[u]),A.pb(rt[v]),B.pb(rt[p]),B.pb(rt[fa[p]]);chai(u,v);if(!ck(k)) {puts("invalid request!");return;}printf("%d\n",mp[qury(1,num,k)-1]);return; } int main() {scanf("%d%d",&n,&m);memset(h,-1,sizeof(h));memset(son,-1,sizeof(son));rep(i,1,n) a[i] = read(), mp.pb(a[i]);rep(i,1,n-1) {int u=read(),v=read();add(u,v),add(v,u);}rep(i,1,m) {q[i].k=read(),q[i].a=read(),q[i].b=read();if(q[i].k==0)mp.pb(q[i].b);}sort(mp.begin(),mp.end()); mp.erase(unique(mp.begin(),mp.end()),mp.end());num = mp.size();init_tp();build(1);rep(i,1,m) {if(q[i].k==0) {B_add(tid[q[i].a],id(a[q[i].a]),-1);a[q[i].a]=q[i].b;B_add(tid[q[i].a],id(a[q[i].a]),1);}else {ask(q[i].a,q[i].b,q[i].k);}}return 0; }

---

BZOJ2212

題意：現在有一棵二叉樹，所有非葉子節點都有兩個孩子。在每個葉子節點上有一個權值(有n個葉子節點，滿足這些權值為1..n的一個排列)。可以任意交換每個非葉子節點的左右孩子。要求進行一系列交換，使得最終所有葉子節點的權值按照遍歷序寫出來，逆序對個數最少。

思路：動態開點，給每個葉子節點開一顆權值線段樹，自底向上合并線段樹，合并的過程中通過左右子樹的權值線段樹計算逆序數。

線段樹合并及復雜度分析：大佬的Blog

#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) typedef long long ll; const int N = 8000010; using namespace std; int n,rt; struct tr{int l,r,num;}tree[N],T[N]; int cc,tot,root[N]; void build(int &rt) {rt = ++cc;int x;scanf("%d",&x);if(x) tree[rt].num=x;else build(tree[rt].l),build(tree[rt].r); } void ins(int &rt,int pre,int p,int d,int l,int r){rt=++tot;T[rt]=T[pre];T[rt].num+=d;if(l==r){T[rt].num=1;return;}int mid=(l+r)>>1;if(p<=mid) ins(T[rt].l,T[pre].l,p,d,l,mid);else ins(T[rt].r,T[pre].r,p,d,mid+1,r);T[rt].num = T[T[rt].l].num + T[T[rt].r].num; } ll ans1,ans2,ans; int merge(int x,int y) {if(!x)return y;if(!y)return x;ans1 += 1LL*T[T[x].l].num*T[T[y].r].num;ans2 += 1LL*T[T[x].r].num*T[T[y].l].num;T[x].l = merge(T[x].l,T[y].l);T[x].r = merge(T[x].r,T[y].r);T[x].num = T[T[x].l].num + T[T[x].r].num;return x; } void solve(int rt) {if(tree[rt].num) return;solve(tree[rt].l),solve(tree[rt].r);ans1=ans2=0;root[rt] = merge(root[tree[rt].l],root[tree[rt].r]);ans+=min(ans1,ans2); } int main() {scanf("%d",&n);build(rt);rep(i,1,cc)if(tree[i].num)ins(root[i],root[i],tree[i].num,1,1,n);solve(rt);printf("%lld\n",ans);return 0; }

---

這個專題就先到這了。。。

轉載于:https://www.cnblogs.com/RRRR-wys/p/9211634.html

總結

以上是生活随笔為你收集整理的主席树学习笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。