求树上路径第k大。
主席树。从根往孩子建。查询(x,y)路径时,在第x棵主席树+第y棵主席树-两倍的第lca(x,y)棵主席树上查询即可。还要特判一下lca(x,y)这个节点。
我写的速度慢出翔。QAQ
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 | #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=200010,maxm=500010,maxt=4000100; int p[maxm],n1[maxm],h[maxn],T[maxn],lc[maxt],rc[maxt],s[maxt],a[maxn],bin[maxn]; int val[maxn],anc[maxn][20],dep[maxn],LcaVal,tot=0,ee=0,n,m,q[maxn],vis[maxn]={0}; char buf[8000000],*pt=buf,*o=buf; inline int getint(){ int s=0; while (*pt< '0' ||*pt> '9' )pt++; while (*pt>= '0' &&*pt<= '9' )s=s*10+*pt++-48; return s; } inline void print( int x){ char str[12],*p=str; if (!x)*o++=48; else { while (x) *p++=x%10+48,x/=10; while (p--!=str)*o++=*p;}; } inline void ae( int a, int b){ p[ee]=b; n1[ee]=h[a]; h[a]=ee++; p[ee]=a; n1[ee]=h[b]; h[b]=ee++; } void build( int l, int r, int &x){ s[x=++tot]=0; if (l==r) return ; int mid=l+r>>1; build(l,mid,lc[x]); build(mid+1,r,rc[x]); } void modify( int p, int v, int l, int r, int &x){ s[x=++tot]=s[p]+1; lc[x]=lc[p]; rc[x]=rc[p]; if (l==r) return ; int mid=l+r>>1; if (v<=mid) modify(lc[p],v,l,mid,lc[x]); else modify(rc[p],v,mid+1,r,rc[x]); } int ask( int a, int b, int c, int l, int r, int k){ if (l==r) return l; int cnt=s[lc[a]]+s[lc[b]]-(s[lc[c]]<<1),mid=l+r>>1; if (LcaVal>=l && LcaVal<=(l+r>>1)) cnt++; if (k<=cnt) return ask(lc[a],lc[b],lc[c],l,mid,k); else return ask(rc[a],rc[b],rc[c],mid+1,r,k-cnt); } int lca( int u, int v){ if (dep[u]<dep[v]) swap(u,v); int k=dep[u]-dep[v],j=0; while (k){ if (k&1) u=anc[u][j]; k>>=1,j++; } if (u==v) return u; for ( int i=16;~i;i--) if (anc[u][i]!=anc[v][i]) u=anc[u][i],v=anc[v][i]; return anc[u][0]; } int main(){ fread (buf,1,8000000,stdin); n=getint(); m=getint(); for ( int i=1;i<=n;i++) bin[i]=a[i]=getint(); memset (h,-1, sizeof (h)); int x,y; for ( int i=1;i<n;i++) ae(getint(),getint()); sort(bin+1,bin+n+1); for ( int i=1;i<=n;i++) a[i]=lower_bound(bin+1,bin+n+1,a[i])-bin; build(1,n,T[0]); int head=0,tail=1; q[0]=vis[1]=dep[1]=1; modify(T[0],a[1],1,n,T[1]); while (head<tail){ int u=q[head++]; for ( int i=h[u];~i;i=n1[i]){ if (!vis[p[i]]){ modify(T[u],a[p[i]],1,n,T[p[i]]); vis[p[i]]=1; dep[p[i]]=dep[u]+1; anc[p[i]][0]=u; q[tail++]=p[i]; } } } for ( int j=1;j<=16;j++) for ( int i=1;i<=n;i++) anc[i][j]=anc[anc[i][j-1]][j-1]; int la=0,z,k; while (m--){ x=getint(); y=getint(); k=getint(); z=lca(x,y); LcaVal=a[z]; if (x==y) print(bin[a[x]]); else print(bin[ask(T[x],T[y],T[z],1,n,k)]); if (m) *o++= '\n' ; } return fwrite (buf,1,o-buf,stdout),0; } |
树上的Nim取石子游戏。
说白了就是,维护一棵树,支持:修改点权,询问一条路径上点权的xor值是否为零。
可以用树链剖分做。但是介于n和q都50w这么大感觉常数很DT。。
既然它只修改点的话,影响到的只是它这棵子树。那么很容易就想到了dfs序。这个子树就是连续一段。
先维护每个点dfs开始时和结束时的时间戳。修改的时候先在它自己的开始、结束位置上xor它自己变成零,然后再修改。
(x,y)路径上的xor值=query(x的开始) xor query(y的开始) xor lca(x,y)的点权。很好想通。LCA就倍增算一下好了。
没了。
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 | #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define YES *o++='Y',*o++='e',*o++='s',*o++='\n' #define NO *o++='N',*o++='o',*o++='\n' const int maxn=500100,maxm=1000100; int p[maxm],n1[maxm],h[maxn],begin[maxn],end[maxn],bit[maxm],st[maxn],a[maxn],n,ee=0,tot=0; int anc[maxn][20],dep[maxn]; char buf[25000000],*o=buf,*pt=buf; inline int getint(){ int s=0; while (*pt< '0' ||*pt> '9' )pt++; while (*pt>= '0' &&*pt<= '9' )s=s*10+*pt++-48; return s; } inline char getop(){ while (*pt!= 'Q' &&*pt!= 'C' ) pt++; return *pt++; } inline void ae( int a, int b){ p[ee]=b; n1[ee]=h[a]; h[a]=ee++; p[ee]=a; n1[ee]=h[b]; h[b]=ee++; } inline void dfs( int s){ int top=0; begin[st[++top]=s]=dep[s]=++tot; while (top){ int u=st[top],f=0; for ( int i=h[u];~i;i=n1[i]){ if (!~begin[p[i]]){ begin[p[i]]=++tot; anc[p[i]][0]=u; dep[p[i]]=dep[u]+1; st[++top]=p[i]; h[u]=n1[i]; f=1; break ; } } if (!f){ end[u]=++tot; top--; } } } inline int lca( int u, int v){ if (dep[u]<dep[v]) swap(u,v); int k=dep[u]-dep[v],j=0; while (k){ if (k&1) u=anc[u][j]; j++,k>>=1; } if (u==v) return u; for ( int j=19;~j;j--) if (anc[u][j]!=anc[v][j]) u=anc[u][j],v=anc[v][j]; return anc[u][0]; } inline void modify( int i){ for ( int x=begin[i];x<maxm;x+=x&-x) bit[x]^=a[i]; for ( int x=end[i];x<maxm;x+=x&-x) bit[x]^=a[i]; } inline int ask( int x){ int r=0; for (;x;x-=x&-x) r^=bit[x]; return r; } int main(){ fread (buf,1,25000000,stdin); n=getint(); for ( int i=1;i<=n;i++) a[i]=getint(); memset (h,-1, sizeof (h)); memset (begin,-1, sizeof (begin)); for ( int i=1;i<n;i++) ae(getint(),getint()); dfs(1); for ( int i=1;i<=n;i++) modify(i); for ( int j=1;j<=19;j++) for ( int i=1;i<=n;i++) anc[i][j]=anc[anc[i][j-1]][j-1]; int q=getint(),x,y,z; while (q--){ if (getop()== 'Q' ){ x=getint();y=getint(); if (ask(begin[x])^ask(begin[y])^a[lca(x,y)]) YES; else NO; } else { x=getint();y=getint(); modify(x); a[x]=y; modify(x); } } return fwrite (buf,1,o-buf,stdout),0; } |
给你一颗无根树。每条边的路径长是1。
每次询问给你三个点。要求你找到一个点。使其它三个点到这个点的路径和最小。
看到这种题就很快联想到LCA了。然后看看样例然后随便手造几组数据,发现求的点一定在其中两个点的LCA。
那么就好了。每次求出3个LCA。然后枚举。算出距离和。
介于倍增比rmq好写的多。就没写rmq。不过倍增的话每次求lca是logn的。每次询问差不多要做6次LCA。那么6logn。
如果是rmq的话每次询问时O(1)。预处理都是nlogn。那么常数一下就跪了。刷rank1也没戏了、不过还有个rank2= =还是玩不过seter、、跪烂、、
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 | #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; char buf[21000000],*pt=buf,*o=buf; int p[1000005],n1[1000005],h[500005]={0},q[500005],d[500005],v[500005]={0}; int lg[500005],a[500005][20],n,m,tot=1; inline int getint(){ int r=0; while (*pt<48||*pt>57)pt++; while (*pt>47&&*pt<58)r=r*10+*pt++-48; return r; } inline void print( int x){ char str[11],*p=str; if (!x)*o++=48; else { while (x) *p++=x%10+48,x/=10; while (p--!=str)*o++=*p;} } inline void ae( int a, int b){ p[tot]=b; n1[tot]=h[a]; h[a]=tot++; p[tot]=a; n1[tot]=h[b]; h[b]=tot++; } inline void pre(){ int s=0,e=1; q[0]=1; d[1]=1; v[1]=1; while (s<e){ for ( int i=h[q[s++]];i;i=n1[i]) if (!v[p[i]]) v[p[i]]=1,q[e++]=p[i],d[p[i]]=d[q[s-1]]+1,a[p[i]][0]=q[s-1]; } for ( int j=1;j<20;j++) for ( int i=1;i<=n;i++) a[i][j]=a[a[i][j-1]][j-1]; } inline int lca( int u, int v){ if (d[u]>d[v]){ u^=v; v^=u; u^=v;} int k=d[v]-d[u],j=0; while (k){ if (k&1)v=a[v][j]; j++; k>>=1;} if (u==v) return u; for ( int i=lg[d[u]-1];~i;i--) if (a[u][i]!=a[v][i]) u=a[u][i],v=a[v][i]; return a[u][0]; } int main(){ fread (pt,1,21000000,stdin); n=getint();m=getint(); for ( int i=0;(1<<i)<=n;i++) for ( int j=(1<<i);j<(1<<i+1)&&j<=n;j++)lg[j]=i; int u,v,w,a1,a2,a3,a4,a5,An1,An2; for ( int i=1;i<n;i++) u=getint(),v=getint(),ae(u,v); pre(); for ( int i=1;i<=m;i++){ u=getint(),v=getint(),w=getint(); a1=lca(u,v),a2=lca(u,w),a3=lca(v,w),a4=d[u]+d[v]+d[w]; An1=a1,An2=a4-d[a1]-(d[lca(w,a1)]<<1); if ((a5=a4-d[a2]-(d[lca(v,a2)]<<1))<An2) An2=a5,An1=a2; if ((a5=a4-d[a3]-(d[lca(u,a3)]<<1))<An2) An2=a5,An1=a3; print(An1);*o++= ' ' ;print(An2);*o++= '\n' ; } return fwrite (buf,1,o-buf,stdout),0; } |