很久没更新了呢。
这题我写的是可持久化线段树版本的。
代码参考了hzwer的，orzzzzzzzzzzzz
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | #include<cstdio>#include<algorithm>using namespace std;long long n,m,h[100005],root[100005],en,lca[100005][20],a[100005],b[100005],deep[100005],es,dfn[100005],pos[100005],dfscnt,cnt,ans=0;struct Edge{long long b,next;}e[200005];struct SegTree{long long nl,nr,v;}tree[3000005];void Add(long long sa,long long sb){e[++en].b=sb;e[en].next=h[sa];h[sa]=en;}long long LCA(long long u,long long v){if(deep[u]<deep[v])swap(u,v);long long sou=deep[u]-deep[v];for(long long i=0;i<=18;i++)if((1<<i)&sou)u=lca[u][i];for(long long i=18;i>=0;i--)if(lca[u][i]!=lca[v][i]){u=lca[u][i];v=lca[v][i];}if(u==v)return u;return lca[u][0];}void DFS(long long u){dfn[++dfscnt]=u;pos[u]=dfscnt;for(long long i=1;i<=18;i++){ if((1<<i)<=deep[u])lca[u][i]=lca[lca[u][i-1]][i-1]; else break;}for(long long i=h[u];i;i=e[i].next){ long long v=e[i].b; if(lca[u][0]!=v){ deep[v]=deep[u]+1; lca[v][0]=u; DFS(v); }}}long long Query(long long a,long long bs,long long c){long long Lca=LCA(a,bs);//printf("ABCD:%lld %lld %lld %lld\n",pos[a],pos[bs],pos[Lca],pos[lca[Lca][0]]);long long sa=root[pos[a]],sb=root[pos[bs]],sc=root[pos[Lca]],sd=root[pos[lca[Lca][0]]];long long l=1,r=es;while(l<r){ long long mid=l+r>>1,Sum=tree[tree[sa].nl].v+tree[tree[sb].nl].v-tree[tree[sc].nl].v-tree[tree[sd].nl].v; //printf("SUM:%lld\n",Sum); if(Sum>=c){r=mid;sa=tree[sa].nl;sb=tree[sb].nl;sc=tree[sc].nl;sd=tree[sd].nl;} else {c-=Sum;l=mid+1;sa=tree[sa].nr;sb=tree[sb].nr;sc=tree[sc].nr;sd=tree[sd].nr;}}return b[l];}void Update(long long l,long long r,long long &root,long long lastroot,long long pos){root=++cnt;tree[root].v=tree[lastroot].v+1;if(l==r)return;tree[root].nl=tree[lastroot].nl;tree[root].nr=tree[lastroot].nr;long long mid=l+r>>1;if(pos<=mid)Update(l,mid,tree[root].nl,tree[lastroot].nl,pos);else Update(mid+1,r,tree[root].nr,tree[lastroot].nr,pos);}int main(){freopen("2588.in","r",stdin);freopen("2588.out","w",stdout);scanf("%lld %lld",&n,&m);for(long long i=1;i<=n;i++){ scanf("%lld",&a[i]); b[i]=a[i];}sort(b+1,b+n+1);es=unique(b+1,b+1+n)-b-1;for(long long i=1;i<=n;i++)a[i]=lower_bound(b+1,b+es+1,a[i])-b;for(long long i=1;i<n;i++){ long long sa,sb; scanf("%lld %lld",&sa,&sb); Add(sa,sb); Add(sb,sa);}DFS(1);for(long long i=1;i<=n;i++){ //printf("ROT:%lld\n",root[pos[lca[dfn[i]][0]]]); Update(1,es,root[i],root[pos[lca[dfn[i]][0]]],a[dfn[i]]);}for(long long i=1;i<=m;i++){ long long a,b,c; scanf("%lld %lld %lld",&a,&b,&c); a^=ans; ans=Query(a,b,c); if(i!=m)printf("%lld\n",ans); else printf("%lld",ans);}return 0;} |
评论 (0)
