[DS记录]P5064 [Ynoi2014] 等这场战争结束之后
command_block
2021-06-30 10:02:42
**题意** ： 维护一张 $n$ 个点的无向图，点有点权，初始时没有边。
支持下列操作 ：
- 添加一条 $x$ 与 $y$ 之间的无向边。
- 回到第 $x$ 次操作后的状态（注意这里的 $x$ 可以是 $0$，即回到初始状态）。
- 查询 $x$ 所在联通块能到的点中点权第 $y$ 小的值，如果不存在，那么输出 $-1$。
允许离线， $n,m\leq 10^5$ ，时限$\texttt{0.5s}$ ，空限$\texttt{20M}$。
------------
一切不强制在线的可持久化都是纸老虎！只需要建立操作树，就能把回档转化为撤回。
考虑值域分块，记块大小为 $B$。对于每个询问，我们只需先判定答案在那个值域块内，再枚举块内的数进行检验。
对于每个值域块，将在块内的数的点权设为 $1$ ，不在块内的数的点权设为 $0$。
对操作树进行 dfs ，用可撤回并查集进行维护，容易查询联通块内的点权和。
这部分复杂度为 $O\big((n^2/B)\log n\big)$。
在得知答案所在值域块后，枚举块内的每个值大力判连通性即可。
这部分复杂度为 $O(nB\log n)$。
取 $B=O(\sqrt{n})$ 可得最优复杂度为 $O(n\sqrt{n}\log n)$。
我们每次只处理一个值域块太浪费，考虑每次处理 $O(\log n)$ 个值域块，则复杂度改进为 $O(n^2/B+nB\log n)$ ，取 $B=\sqrt{n/\log n}$ 即可做到 $O(n\sqrt{n\log n})$。（但空间需要 $O(n\log n)$）
还可以进一步改进。
将操作树分块，在树上撒 $O(\sqrt{n})$ 个关键点点使得每个点向上跳 $O(\sqrt{n})$ 次都会经过某个关键点。
对于每个关键点，不难 $O(n)$ 搜索得到此时的联通信息。
对于每个询问，只需从最近的祖先关键点向下加入 $O(\sqrt{n})$ 个修改然后搜索。
复杂度改进为 $O(n\sqrt{n})$。
代码是 $O(n\sqrt{n\log n})$ 的。
由于数据比较奇怪，块大小要开大一些。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#define MaxN 100500
using namespace std;
const int BS=600,BS2=10;
struct Node{int u,v;}b[MaxN],stk[MaxN];
int top,f[MaxN],c[MaxN];
short s[MaxN][BS2];
void Init(int n){
for (int i=1;i<=n;i++){c[i]=1;f[i]=i;}
memset(s,0,sizeof(short)*(n+3)*BS2);
}
int find(int u)
{return f[u]==u ? u : find(f[u]);}
bool flag;
void merge(int u,int v)
{
u=find(u);v=find(v);
if (u==v)return ;
if (c[u]>c[v])swap(u,v);
stk[++top]=(Node){u,v};
c[f[u]=v]+=c[u];
if (flag)for (int i=0;i<BS2;i++)
s[v][i]+=s[u][i];
}
void undo()
{
int u=stk[top].u,v=stk[top].v;top--;
c[v]-=c[f[u]=u];
if (flag)for (int i=0;i<BS2;i++)
s[v][i]-=s[u][i];
}
struct Data{int u,k,ans;bool fl;}q[MaxN];
struct Line{int t,nxt;}l[MaxN];
int fir[MaxN<<1],tl;
void adl(int u,int v)
{l[++tl]=(Line){v,fir[u]};fir[u]=tl;}
int m;
void dfs1(int u)
{
int sav=top;
merge(b[u].u,b[u].v);
for (int i=fir[u+m];i;i=l[i].nxt){
Data &now=q[l[i].t];
if (now.fl)continue;
int fa=find(now.u);
for (int j=0;j<BS2;j++)
if (now.k>s[fa][j]){
now.k-=s[fa][j];
now.ans+=BS;
}else {now.fl=1;break;}
}
for (int i=fir[u];i;i=l[i].nxt)dfs1(l[i].t);
while(top>sav)undo();
}
void dfs2(int u)
{
int sav=top;
merge(b[u].u,b[u].v);
for (int i=fir[u+m];i;i=l[i].nxt){
Data &now=q[l[i].t];
if (!now.fl){now.ans=-1;continue;}
int fa=find(now.u),&j=now.ans;
while(now.k)if (find(++j)==fa)now.k--;
}
for (int i=fir[u];i;i=l[i].nxt)dfs2(l[i].t);
while(top>sav)undo();
}
int n,tn,tq,x[MaxN],tp[MaxN],*tim=f,*p=f;
bool cmp(int A,int B){return x[A]<x[B];}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)scanf("%d",&x[p[i]=i]);
sort(p+1,p+n+1,cmp);sort(x+1,x+n+1);
for (int i=1;i<=n;i++)tp[p[i]]=i;
for (int i=1,now=0,op,u,k;i<=m;i++){
scanf("%d",&op);
if (op==1){
adl(now,++tn);now=tn;
scanf("%d%d",&b[tn].u,&b[tn].v);
b[tn].u=tp[b[tn].u];b[tn].v=tp[b[tn].v];
}
if (op==2){scanf("%d",&now);now=tim[now];}
if (op==3){
++tq;
scanf("%d%d",&q[tq].u,&q[tq].k);
q[tq].u=tp[q[tq].u];
if (!now)q[tq].ans=-1;
else adl(now+m,tq);
}tim[i]=now;
}
flag=1;
for (int k2=0;k2*BS*BS2<n;k2++){
Init(n);
for (int k=k2*BS2;k<k2*BS2+BS2;k++){
int bl=k*BS+1,br=min(k*BS+BS,n),t=k%BS2;
for (int i=bl;i<=br;i++)s[i][t]=1;
}for (int i=fir[0];i;i=l[i].nxt)dfs1(l[i].t);
}
flag=0;Init(n);
for (int i=fir[0];i;i=l[i].nxt)dfs2(l[i].t);
for (int i=1;i<=tq;i++)
printf("%d\n",q[i].ans==-1 ? -1 : x[q[i].ans]);
return 0;
}
```