P4175题解
jiqimao
2019-11-28 21:37:45
一些套路的综合应用:
要求第k大,主席树。
要查两点间路径,处理到根的前缀和,求出lca后差分。
要带修,发现每次改的是子树。那么可以考虑dfs序,就成了每次改区间。
改区间,再差分一下就成了单点修改查询前缀。直接上树套树即可。
(其实写这篇题解是因为被我自己写的树套树优美到了,谁说树套树只能恶心码量大?)
```c++
#include<bits/stdc++.h>
using namespace std;
const int N=8e4+50,M=2e7+50,K=1e8;
int n,q,a[N],ver[N*2],nxt[N*2],head[N],tot,f[N][17],d[N],dfn[N],rr[N],cnt,r[N];
int lc[M],rc[M],sum[M];
struct node{
int n,a[N];
int calc(){int ret=0;for(int i=1;i<=n;i++)ret+=sum[rc[a[i]]];return ret;}
void L(){for(int i=1;i<=n;i++)a[i]=lc[a[i]];}
void R(){for(int i=1;i<=n;i++)a[i]=rc[a[i]];}
void init(int x){n=0;for(;x;x-=x&-x)a[++n]=r[x];}
}A,B,C,D;
int in(){
int x=0,c;
while(!isdigit(c=getchar()));
while(isdigit(c))x=x*10+(c^48),c=getchar();
return x;
}
void add(int x,int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;}
void dfs(int x,int ff){
f[x][0]=ff;d[x]=d[ff]+1;dfn[x]=++cnt;
for(int i=0;i<16;i++)f[x][i+1]=f[f[x][i]][i];
for(int i=head[x],y;i;i=nxt[i])if((y=ver[i])!=ff)dfs(y,x);
rr[x]=cnt;
}
int lca(int x,int y){
if(d[x]<d[y])swap(x,y);
for(int i=16;~i;i--)if(d[f[x][i]]>=d[y])x=f[x][i];
if(x==y)return x;
for(int i=16;~i;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[x][0];
}
void change(int &x,int l,int r,int p,int d){
if(!x)x=++cnt;sum[x]+=d;
if(l==r)return;int mid=(l+r)>>1;
if(p<=mid)change(lc[x],l,mid,p,d);
else change(rc[x],mid+1,r,p,d);
}
void change(int x,int p,int d){for(;x<=n;x+=x&-x)change(r[x],1,K,p,d);}
int query(int l,int r,int d){
if(l==r)return l;
int mid=(l+r)>>1,dat=A.calc()+B.calc()-C.calc()-D.calc();
if(dat>=d){A.R(),B.R(),C.R(),D.R();return query(mid+1,r,d);}
A.L(),B.L(),C.L(),D.L();return query(l,mid,d-dat);
}
int main(){
n=in();q=in();
for(int i=1;i<=n;i++)a[i]=in();
for(int i=1,x,y;i<n;i++)add(x=in(),y=in()),add(y,x);
dfs(1,0);cnt=0;
for(int i=1;i<=n;i++)change(dfn[i],a[i],1),change(rr[i]+1,a[i],-1);
for(int i=1,k,x,y;i<=q;i++){
k=in();x=in();y=in();
if(k){
int z=lca(x,y);if(d[x]+d[y]-2*d[z]+1<k){puts("invalid request!");continue;}
A.init(dfn[x]);B.init(dfn[y]);C.init(dfn[z]);D.init(dfn[f[z][0]]);
printf("%d\n",query(1,K,k));
}
else change(dfn[x],a[x],-1),change(rr[x]+1,a[x],1),change(dfn[x],a[x]=y,1),change(rr[x]+1,y,-1);
}
return 0;
}
```