题解 P5064 【[Ynoi2014]等这场战争结束之后】

虽然我也不知道为什么$O(n\sqrt{Nlogn})$的做法会这么块…… 虽然我也不知道为什么$O(nlogn)$的空间复杂度可以过20mb的内存限制 ~~听说标算是启发式合并bitset的时候整个人都惊了~~ ~~当然这东西现在过不去了~~ ___________ ## 本题题解 好了让我们来看看这题让我们干什么…… 求联通块kth支持加边? 这不是线段树合并裸题~~(HNOI2012永无乡)~~吗？ 好的看起来我们忽略了操作2……，我们还要资瓷回档~~(Load)~~操作，此时我们的线段树合并的复杂度就gg了(因为我可以一直在你线段树合并复杂度非常大的一步回档然后复杂度就被卡成$O(n^2)$了) 那么我们怎么办呢？ 当然是万能的根号算法咯 那么众所周知的，求kth有两个算法，一个是二分法，而另一个就是大家喜闻乐见的值域分块算法了 如果您还不知道什么是值域分块求kth的话，这里简单的科普一下 我们把权值分成$O(\sqrt{N})$块，如果我们可以快速回答值为i的数字恰好有多少个这个问题以及第i个值域块内有多少个数字这个问题的话，我们就可以采用这样的方式来求出kth **先枚举kth在哪一个值域块，然后在枚举kth到底是哪一个数字** 这样做的好处就是我们无需像二分一样回答比mid大的数字有几个这个不是很好做的问题，我们现在只需要回答有几个数字落在第i个块里以及有几个数字的值恰好为i这两个比较好回答的问题就可以了 接下来我们考虑如何快速的回答这两个问题 为了方便起见我们把点按照权值排序，这样就将求第k小值转成了求第k小点的问题了 ### case1:求有几个点的值恰好为i 那么其实我们把每个点离散化之后这个问题的答案就只有0和1了，也就是说值为i的点是否和x相连 这个问题是普及组并查集问题，此处不再赘述 ### case2:求有几个点的值恰好落在第i个值域块内 一个简单粗暴的思路是并查集上每个点维护一个长度为$O(\sqrt{N})$的数组，然后合并两个点的时候暴力把两个数组相加，这样我们就可以求kth了 等等啊，$20mb$的空间您跟我提$O(n\sqrt{n})$的空间复杂度？ 这种行为就是在自找mle，所以我们来考虑有没有什么trick可以帮我们卡空间 如果我们使用按size合并的并查集的话，我们会发现这个并查集的树高是$O(logn)$级别的，那么这又意味着什么呢？ 意味着如果我们把数组换成一个有序的链表的话此时我们的空间复杂度将会骤降至$O(nlogn)$ 具体点来讲我们并查集上每个节点维护一个链表，链表中的节点存上两个值$(id,cnt)$表示这个集合中有$cnt$个属于编号为$id$的值域块的点,查kth的时候for一遍这个有序的链表就可以了 如此这般分析的话我们会发现一个节点的链表size为$\min(size(p),\sqrt{N})$简单分析一下空间复杂度就是$O(nlogn)$的，因为每一个点最坏情况下会在每个祖先处被存储一次，由于这个log相当的虚所以我们的数组长度只需要开10~20n就可以了 但是合并两个有序链表就非常的令人头疼了，我写了一个归并来合并两个有序的链表，需要注意的一点是我们在将两个链表合并的时候必须保证是把小的链表一个一个的插入到大链表里，为了避免被卡空间我合并的是两个单向链表(这东西十分恶心，细节相当多) 这样的话我们就解决了合并两个集合的问题了，也解决了kth的问题了 当然，这样的话我们仅仅是用$O(n\sqrt{nlogn})$的复杂度解决了永无乡这题，我们还需要支持操作2，也就是回档操作 ### case3:回档 我被这个操作题意杀了好几回 请注意操作2就是字面上的意思，也就是让这张图**完美**的回到第x次操作之后的状态，**不是删除所有添加时间大于x的边** 这两个操作的区别就是我们甚至会**删除操作时间大于x的回档操作** 所以说我们该怎么描述回档关系呢？ 我们把所有的操作看成一颗树，我们现在只需要存储一下第x次操作之后的版本号就行了，然后我们每次操作相当于在某一个特定的版本上进行修改操作，同时生成一个新的版本(其实这东西就是可持久化数据结构) 那么我们不妨设当前的版本号为$father$,一开始的版本是1，也就是什么操作都不做 那么第i个操作1会让版本号变成i+1，因为图被改变了，**此时我们在father和i+1之间连一条边**，然后令$father=i+1$ 询问操作不会改变当前图的版本号，所以第i次询问时的版本号等于第i-1次操作之后的版本号 **回档操作之后的版本号为第x次操作结束之后的版本号**(这东西可能有点拗口，多读几遍你就会知道这是什么意思了)，此时我们将father更改为第x时刻之后的版本号 这样的话我们会建出一棵以1为根的有根树来，第i个版本所拥有的边就是i到1路径上的所有边 那么我们可以在这颗操作树上dfs,压栈的时候直接在按秩合并的并查集上进行连边即可，而弹栈的时候我们需要动一些脑筋了 众所周知，按秩合并的并查集是资瓷撤销操作的，一般状态下我们开一个栈记录一下什么东西被修改了就行了，但是在这里我们不能直接弹栈来实现快速回档，为什么呢? 因为我们为了卡空间，在合并两个并查集节点u和v的时候直接将v的链表接到了u的链表上，而不是复制了一份新的链表(注意如果复制了一个新的链表空间复杂度将会不对) 所以说我们需要把两个有序链表**相减**,换句话说就是在大链表当中删掉小链表中的所有元素，这个同样可以通过归并来实现，当然，由于我们是单向链表，细节同样会非常的恶心，细节部分可以自行看我的代码 这样的话我们就顺利处理了回档操作，接下来把询问离线一下挂到树的对应节点上就可以了…… 所以总结一下这题就是维护一个按秩合并的并查集，将询问离线之后把版本树造出来然后在树上dfs通过压栈和弹栈的方式维护这张图就可以了…… 为了卡空间代码里有很多trick，请自行参考代码吧…… 上代码~ ```C #include<cstdio> #include<algorithm> using namespace std;const int N=1e5+10;const int B=350; template <class T> void read(T &x){ char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } int qu[N];int qv[N];int rk[N];int val[N];int n;int m; int cntb[N/B+3];int pl[N/B+3];int pr[N/B+3]; int ve[N];int nx[N];int al[N];int ans[N];int ctt; inline void add(int u,int V){ve[++ctt]=V;nx[ctt]=al[u];al[u]=ctt;} namespace lsh//离散化 { inline bool cmp(const int& x,const int& y){return val[x]<val[y];} inline void pre() { for(int i=1;i<=n;i++)ans[i]=i;sort(ans+1,ans+n+1,cmp); for(int i=1;i<=n;i++)rk[ans[i]]=i;for(int i=1;i<=n;i++)ans[rk[i]]=val[i]; for(int i=1;i<=n;i++)val[i]=ans[i];val[n+1]=-1; for(int i=1;i<=n;i++)pr[(i-1)/B+1]=i;for(int i=n;i>=1;i--)pl[(i-1)/B+1]=i; } } struct bcj//并查集 { int fa[N];int tot[N];int x[20*N];int v[20*N];int ct;int al[N]; inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;} inline void mglist(int p,int q)//归并两个有序链表，注意不要新开多余的节点 { int t;int i=al[p];int j=al[q];int k1=v[i]&32767;int k2=v[j]&32767; if(k1==k2)v[i]=(((v[i]>>15)+(v[j]>>15))<<15)|k1,t=i,i=x[i],j=x[j]; else if(k1<k2)t=i,i=x[i];else v[++ct]=v[j],al[p]=ct,t=ct,j=x[j]; while(i&&j) { int k1=v[i]&32767;int k2=v[j]&32767; if(k1==k2)v[i]=(((v[i]>>15)+(v[j]>>15))<<15)|k1,x[t]=i,t=i,i=x[i],j=x[j]; else if(k1<k2)x[t]=i,t=i,i=x[i];else v[++ct]=v[j],x[t]=ct,t=ct,j=x[j]; }while(i)x[t]=i,t=i,i=x[i];while(j)v[++ct]=v[j],x[t]=ct,t=ct,j=x[j];x[t]=0; } inline void splist(int p,int q,int ti)//分裂两个有序链表 { for(int i=al[q];i;i=x[i])cntb[v[i]&32767]+=(v[i]>>15); while(al[p]>ti)al[p]=x[al[p]];int t=al[p]; v[t]=(((v[t]>>15)-(cntb[v[t]&32767]))<<15)|(v[t]&32767); for(int i=x[al[p]];i;i=x[i]) if(i<=ti){int k=v[i]&32767;v[i]=(((v[i]>>15)-cntb[k])<<15)|k,x[t]=i,t=i;} ct=ti;for(int i=al[q];i;i=x[i])cntb[v[i]&32767]=0;x[t]=0; }inline void f(int& x){for(;x!=fa[x];x=fa[x]);} inline int ck(int x){for(;x!=fa[x];x=fa[x]);return x;} inline void ih() { for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=n;i++)tot[i]=1; for(int i=1;i<=n;i++)add(i,(1<<15)|((i-1)/B+1)); } inline void lk(int& u,int& V)//连边 {f(u);f(V);if(u==V)return;if(tot[u]<tot[V])swap(u,V);tot[u]+=tot[V];fa[V]=u;mglist(u,V);} inline void del(int u,int V,int ti){fa[V]=V;tot[u]-=tot[V];splist(u,V,ti);}//删除边 inline int brukth(int id,int l,int r,int k)//暴力查询kth {for(int i=l;i<=r;i++){k-=(id==ck(i));if(!k)return i;}} inline int kth(int u,int k) { f(u);if(k>tot[u])return n+1; for(int i=al[u];i;i=x[i]) if(k>(v[i]>>15))k-=(v[i]>>15); else return brukth(u,pl[v[i]&32767],pr[v[i]&32767],k); } }bcj; inline void dfs(int u)//在操作树上dfs { if(u<0){ans[-u]=bcj.kth(qu[-u],qv[-u]);return;}int curt; if(u!=1)curt=bcj.ct,bcj.lk(qu[u],qv[u]); for(int i=al[u];i;i=nx[i])dfs(ve[i]); if(u!=1&&qu[u]!=qv[u])bcj.del(qu[u],qv[u],curt); } int main() { read(n);read(m);for(int i=1;i<=n;i++)read(val[i]); lsh::pre();bcj.ih();ans[1]=1; for(int i=2,typ,x,fa=1;i<=m+1;i++) { read(typ); switch(typ) { case 1: { read(qu[i]);read(qv[i]);qu[i]=rk[qu[i]];qv[i]=rk[qv[i]]; ans[i]=i;add(fa,i);fa=i;break; } case 2:{read(x);x++;fa=ans[x];ans[i]=fa;break;} case 3:{read(qu[i]);read(qv[i]);qu[i]=rk[qu[i]];add(fa,-i);ans[i]=ans[i-1];break;} } }for(int i=2;i<=m+1;i++)ans[i]=-2;dfs(1); for(int i=2;i<=m+1;i++)if(ans[i]!=-2)printf("%d\n",val[ans[i]]);return 0;//拜拜程序~ } ```