Bzoj2588 spoj 10628. count on a tree

Posted by yjjr's blog on December 25, 2017

标签:主席树,LCA

题目

题目传送门

Description 给定一棵N个节点的树,每个点有一个权值,对于M个询问(u,v,k),你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案,初始为0,即第一个询问的u是明文。

Input 第一行两个整数N,M。 第二行有N个整数,其中第i个整数表示点i的权值。 后面N-1行每行两个整数(x,y),表示点x到点y有一条边。 最后M行每行两个整数(u,v,k),表示一组询问。

Output

M行,表示每个询问的答案。最后一个询问不输出换行符 Sample Input 8 5

105 2 9 3 8 5 7 7

1 2

1 3

1 4

3 5

3 6

3 7

4 8

2 5 1

0 5 2

10 5 3

11 5 4

110 8 2

Sample Output 2

8

9

105

7

HINT

HINT:

N,M<=100000

暴力自重。。。

Source

鸣谢seter

分析

树上不带修改的第k小数,把主席树建在树的dfs序上

完全转化为线性问题了

但是每次要查询四棵子树root[x],root[y],root[lca(x,y)],root[fa[lca(x,y)]]

查询时候比较v和t的大小再次写错了,WA了好几次,goodbye 我的AC率

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=1e5+6,maxm=2e6+6;
int n,m,tot,sz,cnt,ind,now,num[maxn],pos[maxn],v[maxn],tmp[maxn],hash[maxn],root[maxn];
int last[maxn],deep[maxn],fa[maxn][17],ls[maxm],rs[maxm],sum[maxm];
struct edge{int to,next;}e[maxm];

void insert(int u,int v){
	e[++cnt]=(edge){v,last[u]};last[u]=cnt;
	e[++cnt]=(edge){u,last[v]};last[v]=cnt;
}

inline int find(int x){
	int l=1,r=tot,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(hash[mid]<x)l=mid+1;else r=mid-1;
	}
	return l;
}
void dfs(int x){
	num[++ind]=x;pos[x]=ind;
	rep(i,1,16)if((1<<i)<=deep[x])fa[x][i]=fa[fa[x][i-1]][i-1];else break;
	reg(x)
		if(fa[x][0]!=e[i].to){
			deep[e[i].to]=deep[x]+1;
			fa[e[i].to][0]=x;
			dfs(e[i].to);
		}
}
int lca(int x,int y){
	if(deep[x]<deep[y])swap(x,y);
	int t=deep[x]-deep[y];
	rep(i,0,16)if((1<<i)&t)x=fa[x][i];
	dep(i,16,0)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	if(x==y)return x;else return fa[x][0];
}
void update(int l,int r,int x,int &y,int v){
	y=++sz;sum[y]=sum[x]+1;
	if(l==r)return;
	ls[y]=ls[x];rs[y]=rs[x];int mid=(l+r)>>1;
	if(v<=mid)update(l,mid,ls[x],ls[y],v);else update(mid+1,r,rs[x],rs[y],v);
}
int query(int x,int y,int rank){
	int a=x,b=y,c=lca(x,y),d=fa[c][0];
	a=root[pos[a]],b=root[pos[b]],c=root[pos[c]],d=root[pos[d]];
	int l=1,r=tot,mid;
	while(l<r){
		mid=(l+r)>>1;
		int t=sum[ls[a]]+sum[ls[b]]-sum[ls[c]]-sum[ls[d]];
		if(t>=rank)r=mid,a=ls[a],b=ls[b],c=ls[c],d=ls[d];
		else rank-=t,l=mid+1,a=rs[a],b=rs[b],c=rs[c],d=rs[d];
	}
	return hash[l];
}
	
int main()
{
	n=read(),m=read();
	rep(i,1,n)v[i]=read(),tmp[i]=v[i];
	sort(tmp+1,tmp+1+n);hash[++tot]=tmp[1];
	rep(i,2,n)
		if(tmp[i]!=tmp[i-1])hash[++tot]=tmp[i];
	rep(i,1,n)v[i]=find(v[i]);
	rep(i,1,n-1){
		int u=read(),v=read();
		insert(u,v);
	}
	dfs(1);
	rep(i,1,n){
		int t=num[i];update(1,tot,root[pos[fa[t][0]]],root[i],v[t]);
	}
	rep(i,1,m){
		int x=read(),y=read(),rank=read();
		x^=now;now=query(x,y,rank);
		if(i!=m)printf("%d\n",now);else printf("%d",now);
	}
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr