题解 CF1416D 【Graph and Queries】
ez_lcw
2021-01-25 19:54:46
带删除维护最大值显然不好做，所以考虑先把最后的图建出来，再从后往前加边。
但是询问中还带修改（让 $p_u=0$），这样会影响后面的询问，所以也不能加边时就得到答案。
这里给出一种十分简单易懂的做法：
在从后往前枚举操作的时候：
1. 如果是加边 $(u,v)$ 且 $u$ 和 $v$ 不连通（设它们所在连通块的根分别为 $a$、$b$），我们就新建一个虚点连向 $a$、$b$，并且把这个虚点作为 $a$、$b$ 的父亲。
2. 如果是询问 $x$，也就是询问当前 $x$ 所在连通块内的最大值，我们就记录一下当前 $x$ 所在连通块的根。
建好新图后，我们再从前往后扫每一个询问。对于一个询问，我们直接查询我们对这个询问记录的根的子树内的最大值，然后把它置零。这些操作具体可以用 dfn 序线段树维护。
其实这个做法的巧妙之处就在于设置了一个虚点，这个虚点起到了一个类似可持久化记录和区分版本的作用。
代码如下：
```cpp
#include<bits/stdc++.h>
#include<iostream>
#define N 200010
#define M 300010
#define K 500010
using namespace std;
struct Edge
{
int u,v;
}e[M];
struct Query
{
int opt,x;
}q[K];
struct data
{
int v,id;
data(){v=-1*1*1*1;}
data(int a,int b){v=a,id=b;}
}maxn[(N+K)<<2];
bool operator < (data a,data b)
{
return a.v<b.v;
}
int n,m,Q,v[N+K],fa[N+K];
int cnt,head[N+K],to[N+K],nxt[N+K];
int node,idx,dfn[N+K],rk[N+K],size[N+K];
bool del[M],vis[N+K];
int find(int x)
{
return x==fa[x]?x:(fa[x]=find(fa[x]));
}
void adde(int u,int v)
{
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
void dfs(int u)
{
dfn[u]=++idx;
rk[idx]=u;
size[u]=1;
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
dfs(v);
size[u]+=size[v];
}
}
void up(int k)
{
maxn[k]=max(maxn[k<<1],maxn[k<<1|1]);
}
void build(int k,int l,int r)
{
if(l==r)
{
maxn[k]=data(v[rk[l]],l);
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
up(k);
}
data query(int k,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr) return maxn[k];
int mid=(l+r)>>1;
data ans;
if(ql<=mid) ans=max(ans,query(k<<1,l,mid,ql,qr));
if(qr>mid) ans=max(ans,query(k<<1|1,mid+1,r,ql,qr));
return ans;
}
void update(int k,int l,int r,int x)
{
if(l==r)
{
maxn[k].v=0;
return;
}
int mid=(l+r)>>1;
if(x<=mid) update(k<<1,l,mid,x);
else update(k<<1|1,mid+1,r,x);
up(k);
}
int main()
{
scanf("%d%d%d",&n,&m,&Q);
node=n;
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);
for(int i=1;i<=m;i++)
scanf("%d%d",&e[i].u,&e[i].v);
for(int i=1;i<=Q;i++)
{
scanf("%d%d",&q[i].opt,&q[i].x);
if(q[i].opt==2) del[q[i].x]=1;
}
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
if(!del[i])
{
int a=find(e[i].u),b=find(e[i].v);
if(a!=b)
{
fa[b]=a;
adde(a,b);
}
}
}
for(int i=Q;i>=1;i--)
{
if(q[i].opt==1) q[i].x=find(q[i].x);
else
{
int a=find(e[q[i].x].u),b=find(e[q[i].x].v);
if(a!=b)
{
++node;//新建虚点
fa[a]=fa[b]=fa[node]=node;
adde(node,a),adde(node,b);
}
}
}
for(int i=1;i<=node;i++)
{
int a=find(i);
if(!vis[a])
{
vis[a]=true;
dfs(a);
}
}
build(1,1,node);
for(int i=1;i<=Q;i++)
{
if(q[i].opt==1)
{
data ans=query(1,1,node,dfn[q[i].x],dfn[q[i].x]+size[q[i].x]-1);
printf("%d\n",ans.v);
update(1,1,node,ans.id);
}
}
return 0;
}
```