泥萌感觉我还能说什么……

这题就是DFS序套主席树，顺便带上倍增LCA，但有两大坑点：

1. 存放数据不一定要用long long，但输入必须要。
2. 输出数据蛋疼，最后一行行末没回车。

代码：

/**************************************************************
    Problem: 2588
    User: danihao123
    Language: C++
    Result: Accepted
    Time:5776 ms
    Memory:52952 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cctype>
#include <vector>
#include <algorithm>
using namespace std;
  
#define FOR1(i,tes) for(i=1;tes;i++)
#define REP(i,n) for(i=0;i<n;i++)
#define REPB(i,n) for(i=1;i<=n;i++)
#define DREP(i,n) for(i=n;i>=0;i--)
#define TwoGn(x) (1<<x)
#define MAKE_MIDDLE int M=L+(R-L)/2
  
const int maxn=100001,maxlogn=18;
const int maxnode=maxn*31;
  
// Graph
vector<int> G[maxn];
inline void Add_Edge(int x,int y){
    G[x].push_back(y);
}
  
// Chair Tree
int sumv[maxnode];
int lc[maxnode],rc[maxnode];
int ct_cnt=0;
int build_tree(int L,int R){
    int ans=++ct_cnt;
    if(R>L){
        MAKE_MIDDLE;
        lc[ans]=build_tree(L,M);
        rc[ans]=build_tree(M+1,R);
    }
    return ans;
}
int p;
int update(int o,int L,int R){
    int ans=++ct_cnt;
    sumv[ans]=sumv[o];
    if(R>L){
        lc[ans]=lc[o];
        rc[ans]=rc[o];
        MAKE_MIDDLE;
        if(p<=M)
            lc[ans]=update(lc[ans],L,M);
        else
            rc[ans]=update(rc[ans],M+1,R);
    }
    sumv[ans]++;
    return ans;
}
int query(int l,int r,int lca,int lca_f,int L,int R,int k){
    if(L==R){
        return L;
    }else{
        int lc_siz=sumv[lc[l]]+sumv[lc[r]]-sumv[lc[lca]]-sumv[lc[lca_f]];
        MAKE_MIDDLE;
        if(k<=lc_siz)
            return query(lc[l],lc[r],lc[lca],lc[lca_f],L,M,k);
        else
            return query(rc[l],rc[r],rc[lca],rc[lca_f],M+1,R,k-lc_siz);
    }
}
int n,siz;
int A[maxn],A2[maxn];
int trees[maxn];
void initChairTree(){
    register int i;
    sort(A2+1,A2+1+n);
    siz=unique(A2+1,A2+1+n)-A2-1;
    trees[0]=build_tree(1,siz);
    for(i=1;i<=n;i++){
        A[i]=lower_bound(A2+1,A2+1+siz,A[i])-A2;
    }
}
  
// DFS
int dep[maxn],par[maxn][maxlogn];
void dfs(int x,int depth,int fa){
    int i,temp;
    par[x][0]=fa;
    dep[x]=depth;
    p=A[x];
    trees[x]=update(trees[fa],1,siz);
    REP(i,G[x].size()){
        temp=G[x][i];
        if(temp!=fa){
            dfs(temp,depth+1,x);
        }
    }
}
void init_LCA(){
    register int i,j;
    FOR1(j,TwoGn(j)<=n)
        REPB(i,n)
            if(par[i][j-1]!=-1)
                par[i][j]=par[par[i][j-1]][j-1];
}
int LCA(int x,int y){
    register int i,j,log;
    if(dep[x]<dep[y])
        swap(x,y);
    for(log=0;TwoGn(log)<=dep[x];log++);
    log--;
    DREP(j,log)
        if((dep[x]-TwoGn(j))>=dep[y])
            x=par[x][j];
    if(x==y)
        return x;
    DREP(j,log)
        if(par[x][j]!=-1 && par[x][j]!=par[y][j]){
            x=par[x][j];
            y=par[y][j];
        }
    return par[x][0];
}
inline long long readint(){
    long long x=0,flag=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')
            flag=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*flag;
}
int main(){
    int m,lca;
    int a,b,c;
    register int i,lastans=0;
    /*
    #ifndef ONLINE_JUDGE
    freopen("data0.in","r",stdin);
    freopen("ot","w+",stdin);
    #endif
    */
    n=readint();
    m=readint();
    REPB(i,n){
        A[i]=readint();
        A2[i]=A[i];
    }
    REP(i,n-1){
        a=readint();
        b=readint();
        Add_Edge(a,b);
        Add_Edge(b,a);
    }
    initChairTree();
    memset(par,-1,sizeof(par));
    dfs(1,1,0);
    init_LCA();
    for(i=1;i<=m;i++){
        a=readint();
        b=readint();
        c=readint();
        a^=lastans;
        lca=LCA(a,b);
        lastans=A2[query(trees[a],trees[b],trees[lca],trees[par[lca][0]],1,siz,c)];
        printf("%d",lastans);
        if(i!=m)
            putchar('\n');
    }
    return 0;
}

• 相关文章
• 全局相关文章