给定一个 个点 条边的无向图,第 个点的点权初始值为 ,所有 互不相同。
接下来进行 次操作,分为两类:
- 查询与 连通的点中, 最大的点 并输出 ,然后让 。
- 将第 条边删掉。
,,。
这是一道比较有趣的“启发式分裂”题。
首先容易发现,每次删边之后大小较小的那部分的大小至少减半,那么参照启发式合并的思路,考虑每次断边之后在大小较小的部分上跑一次 dfs,求出上次断边到这次断边之间的询问的答案。
具体的:
-
首先对图上的每个连通块都跑一遍 dfs,求出它们内部节点按照权值从大到小排序之后的序列。并且把所有删边操作倒过来,变成加边操作,用并查集找到所有改变图的连通性的删边操作;
-
对于每一次询问操作,直接取对应连通块内权值最大的节点 (权值序列中第一个节点),把它的权值变为 之后放到权值序列的末尾即可;
-
对于每一次删边操作,若这次操作不改变图的连通性,直接删掉它即可;否则删掉它之后在大小较小的那一部分上跑一次 dfs,求出它内部节点排序后的序列,根据这个序列和连通块分裂之前的序列就可以求出另一部分的序列。
用 set 维护连通块权值序列的时间复杂度是 的,其中 是值域,又因为“启发式分裂”的时间复杂度是 的,所以时间复杂度 ,卡一卡可以过。
代码如下:(卡常用的火车头省略了)
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int rd()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
return x*f;
}
void print(int x)
{
if(x>9) print(x/10);
*O++=x%10|48;
}
const int MS=200005,S=300005,QS=500005;
struct edge
{
int x,y;
bool del; // 是否被删除
}ed[S];
struct opt
{
int tpe,id; // 操作类型,删边的编号/节点编号
bool imp;
int mnx; // 删边之后属于大小较小的连通块的点
}que[QS];
int n,m,q,qdel;
int a[MS];
vector<int> g[MS];
int fa[MS],siz[MS];
set<pair<int,int> > st[MS];
int cnt,uid[MS];
inline int fnd(int x)
{
return fa[x]==x?x:fa[x]=fnd(fa[x]);
}
void dfs(int u,int stid)
{
st[stid].erase(make_pair(-a[u],u));
st[uid[u]].insert(make_pair(-a[u],u));
for(int i:g[u])
{
if(ed[i].del) continue;
int v=ed[i].x==u?ed[i].y:ed[i].x;
if(uid[v]==uid[u]) continue;
uid[v]=uid[u];
dfs(v,stid);
}
}
int main()
{
n=rd();
m=rd();
q=rd();
for(register int i=1;i<=n;++i) a[i]=rd();
for(register int i=1;i<=m;++i)
{
ed[i].x=rd();
ed[i].y=rd();
g[ed[i].x].push_back(i),g[ed[i].y].push_back(i);
}
for(register int i=1;i<=q;++i)
{
que[i].tpe=rd();
que[i].id=rd();
if(que[i].tpe==2) ed[que[i].id].del=true;
}
for(register int i=1;i<=n;++i) siz[i]=(fa[i]=i)==i;
for(register int i=1;i<=m;++i)
{
if(!ed[i].del)
{
int rx=fnd(ed[i].x),ry=fnd(ed[i].y);
if(rx!=ry) fa[rx]=ry,siz[ry]+=siz[rx];
}
}
for(register int i=q;i>=1;--i)
{
if(que[i].tpe==2)
{
int rx=fnd(ed[que[i].id].x),ry=fnd(ed[que[i].id].y);
if(rx!=ry)
{
que[i].imp=true;
if(siz[rx]<siz[ry]) que[i].mnx=ed[que[i].id].x;
else que[i].mnx=ed[que[i].id].y;
fa[rx]=ry,siz[ry]+=siz[rx];
ed[que[i].id].del=false;
}
}
}
for(register int i=1;i<=n;++i) if(fa[i]==i) uid[i]=++cnt;
for(register int i=1;i<=n;++i) st[uid[i]=uid[fnd(i)]].insert(make_pair(-a[i],i));
for(register int i=1;i<=q;++i)
{
if(que[i].tpe==1)
{
int id=uid[que[i].id];
pair<int,int> fir=*st[id].begin();
print(-fir.first);
*O++='\n';
st[id].erase(fir);
a[fir.second]=0;
st[id].insert(make_pair(0,fir.second));
}
else
{
ed[que[i].id].del=true;
if(que[i].imp)
{
uid[que[i].mnx]=++cnt;
int oth=uid[ed[que[i].id].x==que[i].mnx?ed[que[i].id].y:ed[que[i].id].x];
dfs(que[i].mnx,oth);
}
}
if(O-obuf>(1<<22)) fwrite(obuf,O-obuf,1,stdout),O=obuf;
}
fwrite(obuf,O-obuf,1,stdout);
return 0;
}