BZOJ2588: Count on a tree 主席树

题意

强制在线的树链上第K小

解题思路

树链上第k大问题很容易能想到树链剖分和主席树。如果我们对树深度优先遍历一遍，每遍历到一个结点u就在它父亲结点的基础上更新，那么T[u]这一棵树就维护了从u到根节点这一条链上的信息，再结合树的性质，从u到v这一条链上的信息就可以由u，v，lca(u,v)，fa[lca(u,v)]计算得出。查询操作和区间第K小相类似。

AC代码

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=1e5+5;
int n,m;
int w[maxn],t[maxn],vnum;



int T[maxn<<5],L[maxn<<5],R[maxn<<5],sum[maxn<<5],tnum;
int build(int l,int r){
	int rt=++tnum;
	sum[rt]=0;
	if(l<r){
		int mid=(l+r)/2;
		L[rt]=build(l,mid);
		R[rt]=build(mid+1,r);
	}
	return rt;
}
int update(int rt,int l,int r,int x){
	int nrt=++tnum;
	L[nrt]=L[rt];R[nrt]=R[rt];sum[nrt]=sum[rt]+1;
	if(l<r){
		int mid=(l+r)/2;
		if(x<=mid)L[nrt]=update(L[rt],l,mid,x);
		else R[nrt]=update(R[rt],mid+1,r,x);
	}
	return nrt;
}
int query(int u,int v,int uv,int fuv,int l,int r,int k){
	if(l==r)return l;
	int tmp=sum[L[u]]+sum[L[v]]-sum[L[uv]]-sum[L[fuv]];
	int mid=(l+r)/2;
	if(k<=tmp)return query(L[u],L[v],L[uv],L[fuv],l,mid,k);
	else return query(R[u],R[v],R[uv],R[fuv],mid+1,r,k-tmp);
}



int tot,head[maxn];
struct Edge{
	int v,nxt;
}e[maxn<<1];
void init(){
	tot=0;
	memset(head,-1,sizeof(head));
}
void addedge(int u,int v){
	e[tot].v=v;e[tot].nxt=head[u];head[u]=tot++;
	e[tot].v=u;e[tot].nxt=head[v];head[v]=tot++;
}



int sz[maxn],son[maxn],fa[maxn],h[maxn],top[maxn];
void dfs1(int u,int f){
	sz[u]=1;son[u]=0;fa[u]=f;h[u]=h[f]+1;
	
	T[u]=update(T[f],1,vnum,w[u]);
	
	for(int i=head[u];i!=-1;i=e[i].nxt){
		int v=e[i].v;
		if(v==f)continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[son[u]]<sz[v])son[u]=v;
	}
}
void dfs2(int u,int f,int k){
	top[u]=k;
	if(son[u])dfs2(son[u],u,k);
	for(int i=head[u];i!=-1;i=e[i].nxt){
		int v=e[i].v;
		if(v==f || v==son[u])continue;
		dfs2(v,u,v);
	}
}
int LCA(int u,int v){
	while(top[u]!=top[v]){
		if(h[top[u]]<h[top[v]])swap(u,v);
		u=fa[top[u]];
	}
	if(h[u]>h[v])swap(u,v);
	return u; 
}




int main()
{
//#ifndef ONLINE_JUDGE
//	freopen("in.txt","r",stdin);
//#endif
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&w[i]),t[i]=w[i];
	sort(t+1,t+1+n);
	vnum=unique(t+1,t+1+n)-(t+1);
	for(int i=1;i<=n;i++)w[i]=lower_bound(t+1,t+1+vnum,w[i])-t;
	int u,v,k;
	init();
	for(int i=1;i<=n-1;i++){
		scanf("%d %d",&u,&v);
		addedge(u,v);
	}
	
	
	
	
	T[0]=build(1,vnum);
	dfs1(1,0);dfs2(1,0,1);
	
	
	int lans=0,lca;
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&u,&v,&k);
		u^=lans;lca=LCA(u,v);
		lans=t[query(T[u],T[v],T[lca],T[fa[lca]],1,vnum,k)];
		printf("%d\n",lans);
	}
    return 0;
}