Luogu P5214 [SHOI2014]神奇化合物
我做完这个题才发现可以用缩点+暴力水过去。。。。建议加强数据吧。
我的第一思路是线段树分治。看到这种动态图，第一反应是线段树分治没什么问题吧。。。。
具体来说，我们把每条边出现的时间统计出来，挂到线段树上，然后遍历一遍即可。要标记一下每次询问的时间点。判断图的块数的话，可以用可撤销并查集，用栈记录一下每次的操作，最后回退回去就好了。
问题是如何记录每条边出现的时间呢？我们可以开一个数组 \(a_{i,j}\) 记录 \((i,j)\) 这条边目前最早一次出现的时间点。
- 如果遇到
A i j，就把 \(a_{i,j}\) 更改成当前时间点。 - 如果是
D i j，就把 \(a_{i,j}\) 记为 \(0\)，把这一段时间挂到线段树上即可。
最后遍历线段树，每个时间点的答案就算出来了，只需要对号入座即可。
//Don't act like a loser.
//This code is written by huayucaiji
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
#define int long long
#define pr pair<int,int>
using namespace std;
int read() {
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
const int MAXN=5000+10,MAXM=4e5+10;
int n,m,q,cnt,num;
stack<pr > stk;
int size[MAXN],father[MAXN],a[MAXN][MAXN],qu[MAXM],ans[MAXM];
vector<pr > edge[MAXM<<2];
int find(int x) {
if(x!=father[x]) {
return find(father[x]);
}
return x;
}
void merge(pr s) {
int x=find(s.first);
int y=find(s.second);
if(x==y) {
stk.push(make_pair(-1,-1));
return ;
}
num--;
if(size[x]>size[y]) {
swap(x,y);
}
father[x]=y;
size[y]+=size[y];
stk.push(make_pair(x,y));
}
void del() {
int x=stk.top().first;
int y=stk.top().second;
stk.pop();
if(x==-1) {
return ;
}
num++;
father[x]=x;
size[y]-=size[x];
}
void modify(int l,int r,int p,int x,int y,pr s) {
if(r<x||y<l) {
return ;
}
if(x<=l&&r<=y) {
edge[p].push_back(s);
return ;
}
int mid=(l+r)>>1;
modify(l,mid,p<<1,x,y,s);
modify(mid+1,r,p<<1|1,x,y,s);
}
void query(int l,int r,int p) {
int sz=edge[p].size();
for(int i=0;i<sz;i++) {
merge(edge[p][i]);
//加边
}
if(l==r) {
ans[l]=num;
}
else {
int mid=(l+r)>>1;
query(l,mid,p<<1);
//遍历线段树
query(mid+1,r,p<<1|1);
}
while(sz--) {
del();
//回退操作
}
}
signed main() {
cin>>n>>m;
num=n;
for(int i=1;i<=n;i++) {
father[i]=i;
size[i]=i;
}
for(int i=1;i<=m;i++) {
int u,v;
u=read();
v=read();
a[u][v]=a[v][u]=1;
}
cin>>q;
for(int i=1;i<=q;i++) {
char c;
cin>>c;
if(c=='Q') {
qu[++cnt]=i;
}
if(c=='A') {
int u,v;
u=read();
v=read();
a[u][v]=a[v][u]=i;
}
if(c=='D') {
int u,v;
u=read();
v=read();
modify(1,q,1,a[u][v],i-1,make_pair(u,v));
a[u][v]=a[v][u]=0;
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<i;j++) {
if(a[i][j]) {
modify(1,q,1,a[i][j],q,make_pair(i,j));
}
}
}
query(1,q,1);
for(int i=1;i<=cnt;i++) {
cout<<ans[qu[i]]<<endl;
}
return 0;
}
/*
7 10
1 2
2 3
3 4
4 1
1 3
2 4
5 6
6 7
7 5
2 5
3
Q
D 2 5
Q
*/