c/c++语言开发共享[CTSC2008] 网络管理

树上路径带修第k大问题，没有强制在线。

主体思想：l[x]为点x的dfs序，r[x]为子树x中最后一个节点的dfs序，sum[i]为dfs序为1~i的节点的某种和，d为x,y的lca，则路径x~y的和=sum[l[x]]+sum[l[y]]-sum[l[d]]-sum[l[fa[d]]]。单点修改是对子树范围差分即l[x]处+=w,r[x]+1处-=w。

这道题sum用主席树维护，查询时值域上二分即可。

#include <bits/stdc++.h> #define trvl(x,i,y) for(int i=ehd[x],y; y=to[i],i; i=lst[i])  using namespace std; const int n=8e4+10; const int m=8e6+10;  int n,m,t,a[n],b[n*2]; int ect,ehd[n],to[n*2],lst[n*2]; int cid,lid[n],rid[n],fa[n][20],dep[n]; int cnt,rt[n],siz[m],lc[m],rc[m];  void insert(int x,int y) {     to[++ect]=y,lst[ect]=ehd[x],ehd[x]=ect;     to[++ect]=x,lst[ect]=ehd[y],ehd[y]=ect; } void dfs(int x,int p) {     lid[x]=++cid;     dep[x]=dep[fa[x][0]=p]+1;     for(int i=1; (1<<i)<=dep[x]; ++i) fa[x][i]=fa[fa[x][i-1]][i-1];     trvl(x,i,y) if(y!=p) dfs(y,x);     rid[x]=cid; } int get_lca(int x,int y) {     if(dep[x]<dep[y]) swap(x,y);     int dif=dep[x]-dep[y];     for(int i=19; ~i; --i) if((dif>>i)&1) x=fa[x][i];     if(x==y) return x;     for(int i=19; ~i; --i) if(fa[x][i]!=fa[y][i])          x=fa[x][i],y=fa[y][i];     return fa[x][0]; } void mdf(int&x,int l,int r,int p,int w) {     if(!x) x=++cnt;      siz[x]+=w; if(l==r) return;     int mid=(l+r)>>1;      if(p<=mid) mdf(lc[x],l,mid,p,w);     else mdf(rc[x],mid+1,r,p,w); } void mdf(int x,int p,int w) {     for(; x<=n; x+=x&-x) mdf(rt[x],1,t,p,w); } int top[2],d[2][n]; int kth(int l,int r,int k) {     if(l==r) return l;     int mid=(l+r)>>1,s=0;     for(int i=1; i<=top[0]; ++i) s+=siz[lc[d[0][i]]];     for(int i=1; i<=top[1]; ++i) s-=siz[lc[d[1][i]]]; //  printf("<%d,%d,%d> %dn",l,r,k,s);          if(k<=s) {         for(int i=1; i<=top[0]; ++i) d[0][i]=lc[d[0][i]];         for(int i=1; i<=top[1]; ++i) d[1][i]=lc[d[1][i]];         return kth(l,mid,k);     } else {         for(int i=1; i<=top[0]; ++i) d[0][i]=rc[d[0][i]];         for(int i=1; i<=top[1]; ++i) d[1][i]=rc[d[1][i]];         return kth(mid+1,r,k-s);     } }  int qk[n],qa[n],qb[n];  int main() {     scanf("%d%d",&n,&m); t=n;     for(int i=1; i<=n; ++i) scanf("%d",a+i),b[i]=a[i];     for(int x,y,i=n; --i; ) scanf("%d%d",&x,&y),insert(x,y);     for(int i=1; i<=m; ++i) {         scanf("%d%d%d",qk+i,qa+i,qb+i);         if(!qk[i]) b[++t]=qb[i];     }     dfs(1,0);     sort(b+1,b+t+1);     t=unique(b+1,b+t+1)-b-1;     for(int i=1; i<=n; ++i) {         a[i]=lower_bound(b+1,b+t+1,a[i])-b;         mdf(lid[i],a[i],1);         mdf(rid[i]+1,a[i],-1);     }     for(int i=1; i<=m; ++i) {         if(!qk[i]) {             int x=qa[i];             mdf(lid[x],a[x],-1);             mdf(rid[x]+1,a[x],1);             a[x]=lower_bound(b+1,b+t+1,qb[i])-b;             mdf(lid[x],a[x],1);             mdf(rid[x]+1,a[x],-1);         } else {             top[0]=top[1]=0;             int lca=get_lca(qa[i],qb[i]);              //          printf("%d,%d,%d,%dn",qa[i],qb[i],lca,fa[lca][0]);                          for(int x=lid[qa[i]]; x; x-=x&-x) d[0][++top[0]]=rt[x];             for(int x=lid[qb[i]]; x; x-=x&-x) d[0][++top[0]]=rt[x];             for(int x=lid[lca]; x; x-=x&-x) d[1][++top[1]]=rt[x];             for(int x=lid[fa[lca][0]]; x; x-=x&-x) d[1][++top[1]]=rt[x];             int s=dep[qa[i]]+dep[qb[i]]-dep[lca]-dep[fa[lca][0]];             if(s<qk[i]) puts("invalid request!");             else printf("%dn",b[kth(1,t,s-qk[i]+1)]);         }     }     return 0; }