Spoj 10628. Count on a tree
Time Limit: 12 Sec Memory Limit: 128 MB
Submit: 7669 Solved: 1894
[Submit][Status][Discuss]
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
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
8
9
105
7
HINT
HINT：
N,M<=100000
暴力自重。。。
Source
题解，可持久化权值线段树上二分即可，
很好理解的，我自己写的runtime了好久，不知道为什么。
改成hzwer的就过了，GG。
AC代码
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstdio> #define N 100007
#define M 2000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch>''||ch<''){if (ch=='-') f=-;ch=getchar();}
while(ch<=''&&ch>=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n,m,top,sz,ind;
int a[N],zhi[N];
int num[N],fx[N];
int cnt,head[N],next[*N],rea[*N];
int ls[M],rs[M],sum[M],root[N];
int deep[N],fa[N][]; int find(int x)
{
int l=,r=top;
while(l<=r)
{
int mid=(l+r)>>;
if (zhi[mid]==x) return mid;
if (zhi[mid]<x) l=mid+;
else r=mid-;
}
}
void add(int u,int v)
{
next[++cnt]=head[u];
head[u]=cnt;
rea[cnt]=v;
}
void dfs(int u)
{
ind++,num[ind]=u,fx[u]=ind;
for (int i=;i<=;i++)
fa[u][i]=fa[fa[u][i-]][i-];
for (int i=head[u];i!=-;i=next[i])
{
int v=rea[i];
if (fa[u][]!=v)
{
deep[v]=deep[u]+;
fa[v][]=u;
dfs(v);
}
}
}
int lca(int a,int b)
{
if (deep[a]<deep[b]) swap(a,b);
int i;
for (i=;(<<i)<=deep[a];i++);
i--;
for (int j=i;j>=;j--)
if (deep[a]-(<<j)>=deep[b]) a=fa[a][j];
if (a==b) return a;
for (int j=i;j>=;j--)
if (fa[a][j]!=fa[b][j]) a=fa[a][j],b=fa[b][j];
return fa[a][];
}
void change(int l,int r,int x,int &y,int z)
{
y=++sz;
sum[y]=sum[x]+;
if (l==r) return;
ls[y]=ls[x],rs[y]=rs[x];
int mid=(l+r)>>;
if (z<=mid) change(l,mid,ls[x],ls[y],z);
else change(mid+,r,rs[x],rs[y],z);
}
int query(int l,int r,int a,int b,int c,int d,int rank)
{
if (l==r) return zhi[l];
int mid=(l+r)>>,tmp=sum[ls[a]]+sum[ls[b]]-sum[ls[c]]-sum[ls[d]];
if (tmp>=rank) return query(l,mid,ls[a],ls[b],ls[c],ls[d],rank);
else return query(mid+,r,rs[a],rs[b],rs[c],rs[d],rank-tmp); }
int que(int x,int y,int rk)
{
int a=x,b=y,c=lca(x,y),d=fa[c][];
a=root[fx[a]],b=root[fx[b]],c=root[fx[c]],d=root[fx[d]];
int l=,r=top;
while(l<r)
{
int mid=(l+r)>>;
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+,a=rs[a],b=rs[b],c=rs[c],d=rs[d];
}
return zhi[l];
}
int main()
{
memset(head,-,sizeof(head));
n=read(),m=read();
for (int i=;i<=n;i++)
a[i]=read(),zhi[i]=a[i];
sort(zhi+,zhi+n+);
top=;
for (int i=;i<=n;i++)
if (zhi[i]!=zhi[i-]) zhi[++top]=zhi[i];
for (int i=;i<=n;i++)
a[i]=find(a[i]);
for (int i=;i<n;i++)
{
int x=read(),y=read();
add(x,y),add(y,x);
}
dfs();
for (int i=;i<=n;i++)
{
int t=num[i];//从标号的1开始。
change(,top,root[fx[fa[t][]]],root[i],a[t]);
}
int last=;
for(int i=;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");
}
/*for (int i=1;i<=m;i++)
{
int x=read(),y=read(),rank=read();
x^=last;
int a=root[fx[x]],b=root[fx[y]],c=root[fx[lca(x,y)]],d=root[fx[fa[lca(x,y)][0]]];
last=query(1,top,a,b,c,d,rank);
printf("%d",last);
if (i!=m) cout<<endl;
}*/
}
Wrong代码
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstdio> #define N 100007
#define M 3000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch>''||ch<''){if (ch=='-') f=-;ch=getchar();}
while(ch<=''&&ch>=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n,m,top,sz,ind;
int a[N],zhi[N];
int num[N],fx[N];
int cnt,head[N],next[*N],rea[*N];
int ls[M],rs[M],sum[M],root[N];
int deep[N],fa[N][]; int find(int x)
{
int l=,r=top;
while(l<=r)
{
int mid=(l+r)>>;
if (zhi[mid]==x) return mid;
if (zhi[mid]<x) l=mid+;
else r=mid-;
}
}
void add(int u,int v)
{
next[++cnt]=head[u];
head[u]=cnt;
rea[cnt]=v;
}
void dfs(int u)
{
ind++,num[ind]=u,fx[u]=ind;
for (int i=;i<=;i++)
fa[u][i]=fa[fa[u][i-]][i-];
for (int i=head[u];i!=-;i=next[i])
{
int v=rea[i];
if (fa[u][]!=v)
{
deep[v]=deep[u]+;
fa[v][]=u;
dfs(v);
}
}
}
int lca(int a,int b)
{
if (deep[a]<deep[b]) swap(a,b);
int i;
for (i=;(<<i)<=deep[a];i++);
i--;
for (int j=i;j>=;j--)
if (deep[a]-(<<j)>=deep[b]) a=fa[a][j];
if (a==b) return a;
for (int j=i;j>=;j--)
if (fa[a][j]!=fa[b][j]) a=fa[a][j],b=fa[b][j];
return fa[a][];
}
void change(int l,int r,int x,int &y,int z)
{
y=++sz;
sum[y]=sum[x]+;
if (l==r) return;
ls[y]=ls[x],rs[y]=rs[x];
int mid=(l+r)>>;
if (z<=mid) change(l,mid,ls[x],ls[y],z);
else change(mid+,r,rs[x],rs[y],z);
}
int query(int l,int r,int a,int b,int c,int d,int rank)
{
if (l==r) return zhi[l];
int mid=(l+r)>>,tmp=sum[ls[a]]+sum[ls[b]]-sum[ls[c]]-sum[ls[d]];
if (tmp>=rank) return query(l,mid,ls[a],ls[b],ls[c],ls[d],rank);
else return query(mid+,r,rs[a],rs[b],rs[c],rs[d],rank-tmp);
}
int main()
{
memset(head,-,sizeof(head));
n=read(),m=read();
for (int i=;i<=n;i++)
a[i]=read(),zhi[i]=a[i];
sort(zhi+,zhi+n+);
top=;
for (int i=;i<=n;i++)
if (zhi[i]!=zhi[i-]) zhi[++top]=zhi[i];
for (int i=;i<=n;i++)
a[i]=find(a[i]);
for (int i=;i<n;i++)
{
int x=read(),y=read();
add(x,y),add(y,x);
}
dfs();
for (int i=;i<=n;i++)
{
int t=num[i];//从标号的1开始。
change(,top,root[fx[fa[t][]]],root[i],a[t]);
}
int last=;
for (int i=;i<=m;i++)
{
int x=read(),y=read(),rank=read();
x^=last;
int a=root[fx[x]],b=root[fx[y]],c=root[fx[lca(x,y)]],d=root[fx[fa[lca(x,y)][]]];
last=query(,top,a,b,c,d,rank);
printf("%d",last);
if (i!=m) cout<<endl;
}
}