线段树分治+可撤销并查集 2020牛客暑期多校训练营（第八场）All-Star Game
题目大意：
题解：
线段树分治+可撤销并查集。
首先讲讲这两个算法：
线段树分治呢，其实和线段树差不多，不过有一个分治的思想在里面，可以多刷几个这种类型的题目。
关键是把一个修改看成一个区间，每个询问是一个叶子，修改在线段树上打标记
可撤销并查集：
这个就很简单了，并查集不用路径压缩而是按秩合并，这样可以容易删除，每次放进去的同时记录到一个栈里面，之后再删除，不太理解的可以看看代码。
知道以上两个算法之后，接下来说说这个题目的思路：
- 线段树的每一个区间表示这条边的存在时间，每一个叶子节点表示一个询问。
- 一开始就存在的边先用map存下来，之后的q次询问，对于每次询问的边首先判断是否这条边，如果存在则把这条边放入线段树中，并删除，不存在则存下来。
- 最后每一条存下来的边，都放入线段树中。
- 然后查询，每次查询类似于一个递归的过程，如果遍历到的节点，如果存在边，那么并查集并起来，之后遍历回来再删除即可，这个递归的过程就可以求解。
#include <bits/stdc++.h>
#define debug(x) cout<<"debug:"<<#x<<" = "<<x<<endl;
using namespace std;
const int maxn = 5e5+10;
struct node{
int u,v;
node(int u=0,int v=0):u(u),v(v){}
};
int f[maxn],rk[maxn];
int Find(int x) {
while (x != f[x]) x = f[x];
return x;
}
node unite(int x,int y) {
x = Find(x), y = Find(y);
if (x == y) return 0;
if (rk[x] > rk[y]) swap(x, y);
f[x] = y;
if (rk[x] == rk[y]) {
rk[y]++;
return node(x,rk[y]-1);
}
return node(x,rk[y]);
}
void del(int u,int v) {
rk[f[u]] = v;
f[u] = u;
}
vector<node>e[maxn<<2];
void update(int id,int l,int r,int x,int y,int u,int v){
if(x<=l&&y>=r){
e[id].push_back(node(u,v));
return ;
}
int mid=(l+r)>>1;
if(x<=mid) update(id<<1,l,mid,x,y,u,v);
if(y>mid) update(id<<1|1,mid+1,r,x,y,u,v);
}
int ans[maxn];
int n, m, q;
void dfs(int id,int l,int r,int now) {
for (int i = 0; i < e[id].size(); i++) {
int u = e[id][i].u, v = e[id][i].v;
if (Find(u) != Find(v)) --now;
e[id][i] = unite(u, v);
}
if (l == r) ans[l] = now;
else {
int mid = (l + r) >> 1;
dfs(id << 1, l, mid, now);
dfs(id << 1 | 1, mid + 1, r, now);
}
for (int i = (int) e[id].size() - 1; i >= 0; i--) {
int u = e[id][i].u,v = e[id][i].v;
if (u) del(u,v);
}
}
int cnt1[maxn],cnt2[maxn];
int edge1[maxn],edge2[maxn];
unordered_map<int,int>mp[maxn];
int main() {
scanf("%d%d%d",&n,&m,&q);
for (int i = 1; i <= n; i++) {
int c;
scanf("%d",&c);
while (c--) {
int x;
scanf("%d",&x);
mp[i][x] = 0;
edge1[i]++,edge2[x]++;
}
}
for(int i=1;i<=n+m;i++) f[i] = i;
int tmp1 = 0, tmp2 = 0;
for (int i = 1; i <= n; i++) if (edge1[i] == 0) tmp1++;
for (int i = 1; i <= m; i++) if (edge2[i] == 0) tmp2++;
for (int i = 1; i <= q; i++) {
int y,x;
scanf("%d%d",&y,&x);
if (mp[x].count(y)) {
update(1, 0, q, mp[x][y], i - 1, x, y + n);
mp[x].erase(y);
edge1[x]--, edge2[y]--;
if (edge1[x] == 0) tmp1++;
if (edge2[y] == 0) tmp2++;
} else {
mp[x][y] = i;
if (edge1[x] == 0)tmp1--;
if (edge2[y] == 0)tmp2--;
edge1[x]++, edge2[y]++;
}
cnt1[i] = tmp1, cnt2[i] = tmp2;
}
for (int i = 1; i <= n; i++) {
unordered_map<int, int>::iterator p;
for (p = mp[i].begin(); p != mp[i].end(); p++) {
update(1, 0, q, p->second, q, i, p->first + n);
}
}
dfs(1, 0, q, n + m);
for(int i=1;i<=q;i++){
// printf("cnt1[%d]=%d cnt2[%d]=%d ans[%d]=%d
",i,cnt1[i],i,cnt2[i],i,ans[i]);
if(cnt2[i]) printf("-1
");
else printf("%d
",ans[i]-cnt1[i]);
}
return 0;
}