over 4 years ago

颓了一天……唯一的收获是自己yy了一个主席数然后写出来啦~
充分告诉我们先思考和肉眼查错的重要性,本来可以少花一个小时的。
不要手残==
其实主席树就是把每个点的值插入每个点的线段树就好了wwwwww

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define maxn 100001
#define maxm 4000001
#define l(x) son[x][0]
#define r(x) son[x][1]
using namespace std;
int n,m,lastans=0,widen=0,tot=0,dep=0;
int son[maxm][2]={0},sum[maxm],p[maxn]={0};
int next[maxn*2],point[maxn],v[maxn*2],dy[maxn];
int lca[maxn][20],deep[maxn]={0},fa[maxn],pos[maxn];
struct node{int pos,num;}ls[maxn];
int readln()
{
    char c=getchar();int bj=1,result=0;
    while (c!='-'&&!(c<='9'&&c>='0'))c=getchar();
    if (c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return bj*result;
}
void addedge(int x,int y)
{
    widen++;next[widen]=point[x];point[x]=widen;v[widen]=y;
}
void update(int now){sum[now]=sum[l(now)]+sum[r(now)];}
int insert(int old,int pos,int left,int right)
{
    if (left==right) {tot++;sum[tot]++;return tot;}
    tot++;int re=tot,mid=(left+right)>>1;
    if (pos<=mid) {l(re)=insert(l(old),pos,left,mid);r(re)=r(old);}
    if (mid<pos) {l(re)=l(old);r(re)=insert(r(old),pos,mid+1,right);}
    update(re);
    return re;
}
void dfs(int x,int father,int step)
{
    dy[x]=insert(dy[father],pos[x],1,n);deep[x]=step;dep=max(dep,step);
    for (int k=point[x];k!=0;k=next[k])
      if (v[k]!=father) {lca[v[k]][0]=x;fa[v[k]]=x;dfs(v[k],x,step+1);}
}
int buildvoid(int left,int right)
{
    tot++;
    if (left==right ) return tot;
    int mid=(left+right)>>1,re=tot;
    if (left<=mid) l(tot)=buildvoid(left,mid);
    if (mid<right) r(tot)=buildvoid(mid+1,right);
    return re;
}
bool cmp(const node a,const node b){return a.num<b.num;}
void prepare()
{
    int i,j,border=(int)ceil(log(dep)/log(2));
    for (i=1;i<=border;i++)
     for (j=1;j<=n;j++)
      lca[j][i]=lca[lca[j][i-1]][i-1];
}
int findlca(int x,int y)
{
    if(deep[x]<deep[y]) {int o=x;x=y;y=o;}
    int i,border=(int)ceil(log(dep)/log(2));
    for (i=border;i>=0;i--)
      if (deep[lca[x][i]]>=deep[y]) x=lca[x][i];
    for (i=border;i>=0;i--)
      if (lca[x][i]!=lca[y][i])
        x=lca[x][i],y=lca[y][i];
    if (x!=y)  x=lca[x][0],y=lca[y][0];//这里!手残了写成lca[x][i]...无限RE
 return x;
}
int query(int x,int y,int lca,int falca,int pos,int left,int right)
{
    if (left==right) return ls[left].num;
    int mid=(left+right)>>1;
    int k=sum[l(x)]+sum[l(y)]-sum[l(lca)]-sum[l(falca)];
    if (pos<=k) return query(l(x),l(y),l(lca),l(falca),pos,left,mid);
    if (pos>k) return query(r(x),r(y),r(lca),r(falca),pos-k,mid+1,right);
}
int main()
{
    int i,j,k,x,y,z,depfa;
    n=readln();m=readln();
    for (i=1;i<=n;i++) ls[i].num=p[i]=readln(),ls[i].pos=i;
    sort(ls+1,ls+n+1,cmp);
    for (i=1;i<=n;i++) pos[ls[i].pos]=i;
    for (i=1;i<=n-1;i++)  {x=readln();y=readln();addedge(x,y);addedge(y,x);}
    dy[0]=buildvoid(1,n);
    dfs(1,0,1);
    prepare();
    for (i=1;i<=m;i++)
    {
        x=readln()^lastans;y=readln();z=readln();
        depfa=findlca(x,y);
        lastans=query(dy[x],dy[y],dy[depfa],dy[fa[depfa]],z,1,n);
        printf("%d",lastans);
        if (i!=m) printf("\n");
    }
}
← 【bzoj2395】【Balkan 2011】【最小乘积生成树】Timeismoney 【bzoj2653】【主席树】middle(陈立杰) →
 
comments powered by Disqus