bzoj 2588 Spoj 10628 Count on a tree 樹鍊剖分 主席樹

主席樹維護樹鍊剖分裸題。

最後換行會PE。。。

#include <bits/stdc++.h>
using namespace std;
#define N 110000
#define M 7100000
#define ll long long
int n,m,tot,num,cnt,ans;
int a[N],b[N],head[N],nex[N<<],to[N<<];
int fa[N],size[N],son[N],top[N],deep[N],pos[N],val[N];
int root[N],ch[M][],sum[M];
int st1[],st2[],top1,top2;
void add(int x,int y)
{
    tot++;
    nex[tot]=head[x];head[x]=tot;
    to[tot]=y;
}
void dfs(int x,int y)
{
    size[x]=;
    fa[x]=y;deep[x]=deep[y]+;
    for(int i=head[x];i;i=nex[i])
        if(to[i]!=y)
        {
            dfs(to[i],x);
            size[x]+=size[to[i]];
            son[x]=size[to[i]]>size[son[x]] ? to[i]:son[x];
        }
}
void dfs1(int x,int y,int tp)
{
    top[x]=tp;
    pos[x]=++num;val[num]=a[x];
    if(son[x])dfs1(son[x],x,tp);

    for(int i=head[x];i;i=nex[i])
        if(to[i]!=y&&to[i]!=son[x])
            dfs1(to[i],x,to[i]);
}
void build(int l,int r,int pre,int &now,int v)
{
    sum[now=++cnt]=sum[pre]+;
    if(l==r)return;
    int mid=(l+r)>>;
    ch[now][]=ch[pre][];
    ch[now][]=ch[pre][];
    if(mid>=v)build(l,mid,ch[pre][],ch[now][],v);
    else build(mid+,r,ch[pre][],ch[now][],v);
}
void get(int x,int y)
{
    top1=top2=;
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]])swap(x,y);
        st1[++top1]=root[pos[x]];
        st2[++top2]=root[pos[top[x]]-];
        x=fa[top[x]];
    }
    if(deep[x]<deep[y])swap(x,y);
    st1[++top1]=root[pos[x]];
    st2[++top2]=root[pos[y]-];
}
void trs(int x)
{
    for(int i=;i<=top1;i++)
        st1[i]=ch[st1[i]][x];
    for(int i=;i<=top2;i++)
        st2[i]=ch[st2[i]][x];
}
int solve(int l,int r,int k)
{
    if(l==r)return b[l];
    ll t=;
    for(int i=;i<=top1;i++)
        t+=sum[ch[st1[i]][]];
    for(int i=;i<=top2;i++)
        t-=sum[ch[st2[i]][]];
    int mid=(l+r)>>;
    if(t<k)
        {trs();return solve(mid+,r,k-t);}
    else
        {trs();return solve(l,mid,k);}
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=;i<=n;i++)
        scanf("%d",&a[i]),b[i]=a[i];
    sort(b+,b++n);
    for(int i=;i<=n;i++)
        a[i]=lower_bound(b+,b++n,a[i])-b;
    for(int i=,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs(,);
    dfs1(,,);
    for(int i=;i<=n;i++)
        build(,n,root[i-],root[i],val[i]);
    for(int x,y,k;m--;)
    {
        scanf("%d%d%d",&x,&y,&k);x^=ans;
        get(x,y);
        printf("%d",ans=solve(,n,k));
        if(m)puts("");
    }   
    return ;
}