本文共 2694 字，大约阅读时间需要 8 分钟。
Time Limit: 1 Sec
Memory Limit: 256 MB
给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。
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
2 8 9 105 7
题意
题解：
树上跑主席树
这类题都是这样搞……
代码来自hzwer:
代码：
//qscqesze#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include typedef long long ll;using namespace std;//freopen("D.in","r",stdin);//freopen("D.out","w",stdout);#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)#define maxn 2000005#define eps 1e-9int Num;//const int inf=0x7fffffff; //§ß§é§à§é¨f§3const int inf=0x3f3f3f3f;inline ll read(){ ll x=0,f=1;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;}//**************************************************************************************#define N 100005#define M 2000005int 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] =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 >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(){ //freopen("test.txt","r",stdin); 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
转载于:https://www.cnblogs.com/qscqesze/p/4785256.html