luogu2633 Count on a tree

主席树放到树上而已
#include <algorithm>

#include <iostream>

#include <cstdio>

using namespace std;

int n, m, lstans, uu, vv, a[100005], b[100005], rnk[100005], rem, cnt;

int lson[2200005], rson[2200005], sum[2200005], rot[100005], qwq, ww;

int fa[100005][19], dep[100005], hea[100005], tt[5];

struct Edge{

	int too, nxt;

}edge[200005];

void add_edge(int fro, int too){

	edge[++qwq].nxt = hea[fro];

	edge[qwq].too = too;

	hea[fro] = qwq;

}

int build(int l, int r){

	int rt=++cnt;

	int mid=(l+r)>>1;

	if(l==r)	return rt;

	if(l<=mid)	lson[rt] = build(l, mid);

	if(mid<r)	rson[rt] = build(mid+1, r);

	return rt;

}

int update(int pre, int l, int r, int x){

	int rt=++cnt;

	int mid=(l+r)>>1;

	lson[rt] = lson[pre]; rson[rt] = rson[pre]; sum[rt] = sum[pre] + 1;

	if(l<r){

		if(x<=mid)	lson[rt] = update(lson[pre], l, mid, x);

		if(mid<x)	rson[rt] = update(rson[pre], mid+1, r, x);

	}

	return rt;

}

void dfs(int x, int f){

	fa[x][0] = f;

	dep[x] = dep[f] + 1;

	rot[x] = update(rot[f], 1, rem, rnk[x]);

	for(int i=hea[x]; i; i=edge[i].nxt){

		int t=edge[i].too;

		if(t!=f)	dfs(t, x);

	}

}

int getLca(int uu, int vv){

	if(dep[uu]<dep[vv])	swap(uu, vv);

	for(int i=16; i>=0; i--)

		if(dep[fa[uu][i]]>=dep[vv])

			uu = fa[uu][i];

	if(uu==vv)	return vv;

	for(int i=16; i>=0; i--)

		if(fa[uu][i]!=fa[vv][i]){

			uu = fa[uu][i];

			vv = fa[vv][i];

		}

	return fa[uu][0];

}

int query(int l, int r, int k){

	int tmp=0;

	int mid=(l+r)>>1;

	tmp -= sum[lson[tt[3]]] + sum[lson[tt[4]]];

	tmp += sum[lson[tt[1]]] + sum[lson[tt[2]]];

	if(l==r)	return l;

	if(k<=tmp){

		for(int i=1; i<=4; i++)

			tt[i] = lson[tt[i]];

		return query(l, mid, k);

	}

	else{

		for(int i=1; i<=4; i++)

			tt[i] = rson[tt[i]];

		return query(mid+1, r, k-tmp);

	}

}

int main(){

	cin>>n>>m;

	for(int i=1; i<=n; i++){

		scanf("%d", &a[i]);

		b[i] = a[i];

	}

	for(int i=1; i<n; i++){

		scanf("%d %d", &uu, &vv);

		add_edge(uu, vv);

		add_edge(vv, uu);

	}

	sort(b+1, b+1+n);

	rem = unique(b+1, b+1+n) - (b + 1);

	for(int i=1; i<=n; i++)

		rnk[i] = lower_bound(b+1, b+1+rem, a[i]) - b;

	rot[0] = build(1, rem);

	dfs(1, 0);

	for(int i=1; i<=16; i++)

		for(int j=1; j<=n; j++)

			fa[j][i] = fa[fa[j][i-1]][i-1];

	while(m--){

		scanf("%d %d %d", &uu, &vv, &ww);

		uu ^= lstans;

		int lca=getLca(uu, vv);

		tt[1] = rot[uu]; tt[2] =rot[vv];

		tt[3] = rot[lca]; tt[4] = rot[fa[lca][0]];

		lstans = b[query(1, rem, ww)];

		printf("%d\n", lstans);

	}

	return 0;

}
巴特西

luogu2633 Count on a tree

最新文章

热门文章
