C55 可持久化线段树+LCA P2633 Count on a tree

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=100005;
#define mid ((l+r)>>1)
int h[N],to[N*2],ne[N*2],idx; //邻接表
void add(int a,int b){
  to[++idx]=b; ne[idx]=h[a]; h[a]=idx;
}
int n,m,bn,last,a[N],b[N]; //b:离散化数组
int f[N][20],dep[N];       //LCA数组
int rt[N],tot;             //根节点,开点个数
int ls[N*20],rs[N*20],sum[N*20]; //可持久化线段树

void change(int &u,int v,int l,int r,int p){ //点修
  u=++tot; //动态开点
  ls[u]=ls[v]; rs[u]=rs[v]; sum[u]=sum[v]+1;
  if(l==r) return;     //双指针同步搜索
  if(p<=mid) change(ls[u],ls[v],l,mid,p);
  else change(rs[u],rs[v],mid+1,r,p);
}
void dfs(int u,int fa){ //预处理
  change(rt[u],rt[fa],1,bn,a[u]); //建可持久线段树
  dep[u]=dep[fa]+1; f[u][0]=fa;
  for(int i=1; i<=18; i++) 
    f[u][i]=f[f[u][i-1]][i-1]; 
  for(int i=h[u];i;i=ne[i])
    if(to[i]!=fa) dfs(to[i],u);
}
int LCA(int u,int v){ //返回LCA
  if(dep[u]<dep[v]) swap(u,v);
  for(int i=18; i>=0; i--)
    if(dep[f[u][i]]>=dep[v]) u=f[u][i];
  if(u==v) return u;
  for(int i=18; i>=0; i--)
    if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
  return f[u][0];
}
int query(int u,int v,int x,int y,int l,int r,int k){ //点查
  if(l==r) return l;              //四指针同步搜索
  int s=sum[ls[u]]+sum[ls[v]]-sum[ls[x]]-sum[ls[y]];
  if(k<=s)return query(ls[u],ls[v],ls[x],ls[y],l,mid,k);
  else return query(rs[u],rs[v],rs[x],rs[y],mid+1,r,k-s);
}
int main(){
  scanf("%d%d",&n,&m); int u,v,k;
  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",&u,&v),add(u,v),add(v,u);
  sort(b+1,b+n+1);
  bn=unique(b+1,b+n+1)-b-1; //去重
  for(int i=1;i<=n;i++)
    a[i]=lower_bound(b+1,b+1+bn,a[i])-b; //离散值
  dfs(1,0); //预处理
  for(int i=1; i<=m; ++i){
    scanf("%d%d%d",&u,&v,&k); u^=last;
    int L=LCA(u,v);
    last=b[query(rt[u],rt[v],rt[L],rt[f[L][0]],1,bn,k)];
    printf("%d\n",last);
  }
}

C55 可持久化线段树+LCA P2633 Count on a tree

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=100005; #define mid ((l+r)>>1) int h[ N],to[ N2],ne[ N2],idx; //邻接表 void add(int a,int b){ to[ ++idx]=b,ne[ idx]=h[ a],h[ a]=idx; } int n,m,bn,last,a[ N],b[ N]; //b:离散化数组 int f[ N][ 20],dep[ N]; //LCA数组 int rt[ N],tot; //根节点,开点个数 int ls[ N20],rs[ N20],sum[ N*20]; //可持久化线段树

void change(int &u,int v,int l,int r,int p){ //点修 u=++tot; //动态开点 ls[ u]=ls[ v]; rs[ u]=rs[ v]; sum[ u]=sum[ v]+1; if(lr) return; //双指针同步搜索 if(p<=mid) change(ls[ u],ls[ v],l,mid,p); else change(rs[ u],rs[ v],mid+1,r,p); } void dfs(int u,int fa){ //预处理 change(rt[ u],rt[ fa],1,bn,a[ u]); //建可持久线段树 dep[ u]=dep[ fa]+1; f[ u][ 0]=fa; for(int i=1; i<=18; i++) f[ u][ i]=f[ f[ u][ i-1]][ i-1]; for(int i=h[ u];i;i=ne[ i]) if(to[ i]!=fa) dfs(to[ i],u); } int LCA(int u,int v){ //返回LCA if(dep[ u]<dep[ v]) swap(u,v); for(int i=18; i>=0; i--) if(dep[ f[ u][ i]]>=dep[ v]) u=f[ u][ i]; if(uv) return u; for(int i=18; i>=0; i--) if(f[ u][ i]!=f[ v][ i]) u=f[ u][ i],v=f[ v][ i]; return f[ u][ 0]; } int query(int u,int v,int x,int y,int l,int r,int k){ //点查 if(l==r) return l; //四指针同步搜索 int s=sum[ ls[ u]]+sum[ ls[ v]]-sum[ ls[ x]]-sum[ ls[ y]]; if(k<=s)return query(ls[ u],ls[ v],ls[ x],ls[ y],l,mid,k); else return query(rs[ u],rs[ v],rs[ x],rs[ y],mid+1,r,k-s); } int main(){ scanf("%d%d",&n,&m); int u,v,k; 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",&u,&v),add(u,v),add(v,u); sort(b+1,b+n+1); bn=unique(b+1,b+n+1)-b-1; //去重 for(int i=1;i<=n;i++) a[ i]=lower_bound(b+1,b+1+bn,a[ i])-b; //离散值 dfs(1,0); //预处理 for(int i=1; i<=m; ++i){ scanf("%d%d%d",&u,&v,&k); u^=last; int L=LCA(u,v); last=b[ query(rt[ u],rt[ v],rt[ L],rt[ f[ L][ 0]],1,bn,k)]; printf("%d\n",last); } }</pre>