「BZOJ2588」SPOJ 10628. Count on a tree

2014年6月17日7,8066

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

暴力自重。。。

题解

在树上建主席树，然后就很简单了。。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define inf 0x7fffffff
#define ll long long
#define N 100005
#define M 2000005
using namespace std;
inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,tot,sz,cnt,ind,last;
int num[N],pos[N];
int v[N],tmp[N],hash[N],root[N];
int ls[M],rs[M],sum[M];
int deep[N],fa[N][17];
struct data{int to,next;}e[200005];int head[N];
void ins(int u,int v)
{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;}
void insert(int u,int v)
{ins(u,v);ins(v,u);}
int find(int x)
{
	int l=1,r=tot;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(hash[mid]<x)l=mid+1;
		else if(hash[mid]==x)return mid;
		else r=mid-1;
	}
}
void dfs(int x)
{
	ind++;num[ind]=x;pos[x]=ind;
	for(int i=1;i<=16;i++)
	    if((1<<i)<=deep[x])fa[x][i]=fa[fa[x][i-1]][i-1];
	    else break;
	for(int i=head[x];i;i=e[i].next)
		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];
    for(int i=0;i<=16;i++)
        if((1<<i)&t)x=fa[x][i];
    for(int i=16;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    if(x==y)return x;
    return fa[x][0];
}
void update(int l,int r,int x,int &y,int num)
{
    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(num<=mid)
	    update(l,mid,ls[x],ls[y],num);
	else update(mid+1,r,rs[x],rs[y],num);
}
int que(int x,int y,int rk)
{
	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;
	while(l<r)
	{
		int mid=(l+r)>>1;
		int tmp=sum[ls[a]]+sum[ls[b]]-sum[ls[c]]-sum[ls[d]];
		if(tmp>=rk)r=mid,a=ls[a],b=ls[b],c=ls[c],d=ls[d];
		else rk-=tmp,l=mid+1,a=rs[a],b=rs[b],c=rs[c],d=rs[d];
	}
	return hash[l];
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	    v[i]=read(),tmp[i]=v[i];
	sort(tmp+1,tmp+n+1);
	hash[++tot]=tmp[1];
	for(int i=2;i<=n;i++)
	    if(tmp[i]!=tmp[i-1])hash[++tot]=tmp[i];
	for(int i=1;i<=n;i++)v[i]=find(v[i]);
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();
		insert(u,v);
	}
	dfs(1);
	for(int i=1;i<=n;i++)
	{
		int t=num[i];
		update(1,tot,root[pos[fa[t][0]]],root[i],v[t]);
	}
	for(int i=1;i<=m;i++)
	{
		int x=read(),y=read(),rk=read();
		x^=last;
		last=que(x,y,rk);
		printf("%d",last);
		if(i!=m)printf("\n");
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cstring>

#define inf 0x7fffffff

#define ll long long

#define N 100005

#define M 2000005

using namespace std;

inline ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,tot,sz,cnt,ind,last;

int num[N],pos[N];

int v[N],tmp[N],hash[N],root[N];

int ls[M],rs[M],sum[M];

int deep[N],fa[N][17];

struct data{int to,next;}e[200005];int head[N];

void ins(int u,int v)

{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;}

void insert(int u,int v)

{ins(u,v);ins(v,u);}

int find(int x)

{

int l=1,r=tot;

while(l<=r)

{

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

if(hash[mid]<x)l=mid+1;

else if(hash[mid]==x)return mid;

else r=mid-1;

}

void dfs(int x)

{

ind++;num[ind]=x;pos[x]=ind;

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

if((1<<i)<=deep[x])fa[x][i]=fa[fa[x][i-1]][i-1];

else break;

for(int i=head[x];i;i=e[i].next)

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];

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

if((1<<i)&t)x=fa[x][i];

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

if(fa[x][i]!=fa[y][i])

x=fa[x][i],y=fa[y][i];

if(x==y)return x;

return fa[x][0];

}

void update(int l,int r,int x,int &y,int num)

{

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(num<=mid)

update(l,mid,ls[x],ls[y],num);

else update(mid+1,r,rs[x],rs[y],num);

}

int que(int x,int y,int rk)

{

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;

while(l<r)

{

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

int tmp=sum[ls[a]]+sum[ls[b]]-sum[ls[c]]-sum[ls[d]];

if(tmp>=rk)r=mid,a=ls[a],b=ls[b],c=ls[c],d=ls[d];

else rk-=tmp,l=mid+1,a=rs[a],b=rs[b],c=rs[c],d=rs[d];

}

return hash[l];

}

int main()

{

n=read(),m=read();

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

v[i]=read(),tmp[i]=v[i];

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

hash[++tot]=tmp[1];

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

if(tmp[i]!=tmp[i-1])hash[++tot]=tmp[i];

for(int i=1;i<=n;i++)v[i]=find(v[i]);

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

{

int u=read(),v=read();

insert(u,v);

}

dfs(1);

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

{

int t=num[i];

update(1,tot,root[pos[fa[t][0]]],root[i],v[t]);

}

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

{

int x=read(),y=read(),rk=read();

x^=last;

last=que(x,y,rk);

printf("%d",last);

if(i!=m)printf("\n");

}

return 0;

}

« 「POJ2104」K – th Number 「BZOJ3551」[ONTAK2010] Peaks加强版 »

魏子豪

为什么这个建立主席树还要重新打树上编号？

黄学长的脑残粉

重标号之后一个链上的点才是连续的啊？

魏子豪

觉得直接在父亲那颗树上直接建树就可以了啊

魏子豪

在倍增预处理的同时就同时在父亲节点的基础上建树

invoid

您最后写成功了么，我也有这样的疑问

魏子豪

写成功了，可以不用重新打标记。

hzwer.com _ Home | http://hzwer.com

「BZOJ2588」SPOJ 10628. Count on a tree

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论