【BZOJ2588】【SPOJ10628】Count on a tree

主席树裸题之二

练板子

// <2588.cpp> - 08/01/16 21:55:49
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=200010;
const int K=20;
const int INF=1e9;
struct number{
    int x,id;
    bool operator <(const number b) const{return x<b.x;}
}p[MAXN];
int n,a[MAXN];
int bt,b[MAXN],next[MAXN],to[MAXN];
inline void add(int x,int y){
    next[++bt]=b[x];b[x]=bt;to[bt]=y;
    next[++bt]=b[y];b[y]=bt;to[bt]=x;
}
int f[K][MAXN],dep[MAXN];
int tot,root[MAXN],s[MAXN*20][2],val[MAXN*20];
int build(int last,int k,int l=1,int r=n){
    int x=++tot;
    s[x][0]=s[last][0];s[x][1]=s[last][1];
    val[x]=val[last]+1;
    if(l!=r){
        int m=(l+r)>>1;
        if(k<=m)s[x][0]=build(s[last][0],k,l,m);
        else s[x][1]=build(s[last][1],k,m+1,r);
    }
    return x;
}
void dfs(int x){
    for(int i=b[x];i;i=next[i]){
        if(to[i]==f[0][x])continue;
        f[0][to[i]]=x;
        dep[to[i]]=dep[x]+1;
        root[to[i]]=build(root[x],a[to[i]]);
        dfs(to[i]);
    }
}
int lca(int x,int y){
    if(dep[x]>dep[y])swap(x,y);
    int l=dep[y]-dep[x];
    for(int i=0,now=1;i<K;i++,now<<=1)
        if(l&now)y=f[i][y];
    if(x==y)return x;
    for(int i=K-1;i>=0;i--)
        if(f[i][x]!=f[i][y])x=f[i][x],y=f[i][y];
    return f[0][x];
}
int ask(int x,int y,int a,int b,int k,int l=1,int r=n){
    if(l==r)return l;
    int m=(l+r)>>1;
    int lp=val[s[x][0]]+val[s[y][0]]-val[s[a][0]]-val[s[b][0]];
    if(k<=lp)return ask(s[x][0],s[y][0],s[a][0],s[b][0],k,l,m);
    return ask(s[x][1],s[y][1],s[a][1],s[b][1],k-lp,m+1,r);
}
int main(){
    n=gi();int m=gi(),ans=0;
    for(int i=1;i<=n;i++)p[i].x=gi(),p[i].id=i;
    sort(p+1,p+n+1);
    for(int i=1;i<=n;i++)a[p[i].id]=i;
    for(int i=1;i<n;i++)add(gi(),gi());
    root[1]=build(0,a[1]);
    dfs(1);
    for(int j=1;j<K;j++)
        for(int i=1;i<=n;i++)f[j][i]=f[j-1][f[j-1][i]];
    while(m--){
        int u=gi()^ans,v=gi(),k=gi();
        int l=lca(u,v);
        ans=p[ask(root[u],root[v],root[l],root[f[0][l]],k)].x;
        printf("%d",ans);
        if(m)putchar('\n');
    }
    return 0;
}

// <2588.cpp> - 08/01/16 21:55:49

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=200010;

const int K=20;

const int INF=1e9;

struct number{

int x,id;

bool operator <(const number b) const{return x<b.x;}

}p[MAXN];

int n,a[MAXN];

int bt,b[MAXN],next[MAXN],to[MAXN];

inline void add(int x,int y){

next[++bt]=b[x];b[x]=bt;to[bt]=y;

next[++bt]=b[y];b[y]=bt;to[bt]=x;

}

int f[K][MAXN],dep[MAXN];

int tot,root[MAXN],s[MAXN*20][2],val[MAXN*20];

int build(int last,int k,int l=1,int r=n){

int x=++tot;

s[x][0]=s[last][0];s[x][1]=s[last][1];

val[x]=val[last]+1;

if(l!=r){

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

if(k<=m)s[x][0]=build(s[last][0],k,l,m);

else s[x][1]=build(s[last][1],k,m+1,r);

}

return x;

}

void dfs(int x){

for(int i=b[x];i;i=next[i]){

if(to[i]==f[0][x])continue;

f[0][to[i]]=x;

dep[to[i]]=dep[x]+1;

root[to[i]]=build(root[x],a[to[i]]);

dfs(to[i]);

}

int lca(int x,int y){

if(dep[x]>dep[y])swap(x,y);

int l=dep[y]-dep[x];

for(int i=0,now=1;i<K;i++,now<<=1)

if(l&now)y=f[i][y];

if(x==y)return x;

for(int i=K-1;i>=0;i--)

if(f[i][x]!=f[i][y])x=f[i][x],y=f[i][y];

return f[0][x];

}

int ask(int x,int y,int a,int b,int k,int l=1,int r=n){

if(l==r)return l;

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

int lp=val[s[x][0]]+val[s[y][0]]-val[s[a][0]]-val[s[b][0]];

if(k<=lp)return ask(s[x][0],s[y][0],s[a][0],s[b][0],k,l,m);

return ask(s[x][1],s[y][1],s[a][1],s[b][1],k-lp,m+1,r);

}

int main(){

n=gi();int m=gi(),ans=0;

for(int i=1;i<=n;i++)p[i].x=gi(),p[i].id=i;

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

for(int i=1;i<=n;i++)a[p[i].id]=i;

for(int i=1;i<n;i++)add(gi(),gi());

root[1]=build(0,a[1]);

dfs(1);

for(int j=1;j<K;j++)

for(int i=1;i<=n;i++)f[j][i]=f[j-1][f[j-1][i]];

while(m--){

int u=gi()^ans,v=gi(),k=gi();

int l=lca(u,v);

ans=p[ask(root[u],root[v],root[l],root[f[0][l]],k)].x;

printf("%d",ans);

if(m)putchar('\n');

}

return 0;

}