做法还是比较simple的 主席树+启发式合并
然后怎么感觉卡常卡空间啊。。
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 104 105 106 107 108 109 110 111 112 113 114 |
// <3123.cpp> - Wed Mar 8 09:18:15 2017 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; #define next NEXT template<typename T> inline void gg(T &res){ res=0;T fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); res*=fh; } inline int gi(){int x;gg(x);return x;} inline lol gl(){lol x;gg(x);return x;} const int MAXN=80010; const int MAXM=160010; const int MAXK=MAXN<<8; const int K=18; const int INF=1e9; int u[MAXN],a[MAXN],id[MAXN]; bool cmp(int x,int y){return a[x]<a[y];} char ch[3]; int n,tot,rt[MAXN],val[MAXK],s[MAXK][2]; int build(int p,int k,int l=1,int r=n){ int x=++tot; val[x]=val[p]+1; s[x][0]=s[p][0];s[x][1]=s[p][1]; if(l==r)return x; int m=l+r>>1; if(k<=m)s[x][0]=build(s[x][0],k,l,m); else s[x][1]=build(s[x][1],k,m+1,r); return x; } int ask(int a,int b,int c,int d,int k,int l=1,int r=n){ if(l==r)return l; int m=l+r>>1; int suml=val[s[a][0]]+val[s[b][0]]-val[s[c][0]]-val[s[d][0]]; if(suml>=k)return ask(s[a][0],s[b][0],s[c][0],s[d][0],k,l,m); return ask(s[a][1],s[b][1],s[c][1],s[d][1],k-suml,m+1,r); } int bt,b[MAXN],next[MAXM],to[MAXM]; inline void add(int x,int y){ next[++bt]=b[x];b[x]=bt;to[bt]=y; next[++bt]=b[y];b[y]=bt;to[bt]=x; } int dep[MAXN],f[K][MAXN],size[MAXN],F[MAXN]; void kill(int x,int y){ F[x]=y; for(int i=b[x];i;i=next[i]) if(F[to[i]]!=y)kill(to[i],y); f[0][x]=0; } void dfs(int x){ size[x]=1; for(int j=1;j<K;j++)f[j][x]=f[j-1][f[j-1][x]]; rt[x]=build(rt[f[0][x]],a[x]); for(int i=b[x];i;i=next[i]){ if(to[i]==f[0][x])continue; f[0][to[i]]=x; dep[to[i]]=dep[x]+1; dfs(to[i]); size[x]+=size[to[i]]; } } void link(int x,int y){ if(size[F[x]]>size[F[y]])swap(x,y); size[F[y]]+=size[F[x]]; kill(F[x],F[y]); add(x,y); f[0][x]=y; dep[x]=dep[y]+1; dfs(x); } int lca(int x,int y){ if(dep[x]<dep[y])swap(x,y); int d=dep[x]-dep[y]; for(int i=0,p=1;i<K;i++,p<<=1) if(d&p)x=f[i][x]; if(x==y)return x; for(int i=K-1;i>=0;i--){ if(f[i][x]==f[i][y])continue; x=f[i][x];y=f[i][y]; } return f[0][x]; } int main(){ gi();n=gi();int m=gi(),q=gi(); for(int i=1;i<=n;i++)u[i]=a[i]=gi(),id[i]=i; sort(u+1,u+n+1); sort(id+1,id+n+1,cmp); for(int i=1;i<=n;i++)a[id[i]]=i; for(int i=1;i<=n;i++)rt[i]=build(0,a[i]); for(int i=1;i<=m;i++)add(gi(),gi()); for(int i=1;i<=n;i++)if(!F[i]){kill(i,i);dfs(i);} int ans=0; while(q--){ scanf("%s",ch); if(ch[0]=='Q'){ int x=gi()^ans,y=gi()^ans,z=lca(x,y),k=gi()^ans; printf("%d\n",ans=u[ask(rt[x],rt[y],rt[z],rt[f[0][z]],k)]); }else link(gi()^ans,gi()^ans); } return 0; } |
Orz & 沙发
LCF是个神犇 Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz … 阅读更多 »
楼上是个神犇 Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz O… 阅读更多 »
这道题写个垃圾回收站空间就是O(nlogn)了
所以空间还是没那么卡的
Orz LCF
能过就没写空间回收了
Orz