题解：CF2069F Graph Inclusion

对于一组询问，答案为 $A$ 中连通块的数量 - $A \cup B$ 中的连通块数量。

设在 $A$ 中添加了若干条边后变为 $A’$。当两个顶点 $u,v$ 在 $A$ 或 $B$ 中属于同一个连通分量，那么在 $A’$ 中必同属于一个连通分量。因此，我们不难得出上述结论。

由于存在动态的加边删边，不难想到时间戳的线段树分治。对于在某一张图的边，记录下出现时间和消失时间 $l,r$，则由题目可知，该边在 $[l,r - 1]$ 范围内产生贡献。注意，若一条边在加入之后一直存在，则该边在 $[l,q]$ 范围内产生贡献。

至于如何计算连通块的个数，初始值显然为 $n$。与此同时，可以在并查集的合并时增加一个返回值，若形成一次有效的合并时，连通块的个数便会减少 $1$。

由于需要分别维护 $A$ 和 $A \cup B$ 的连通块数量，我们可以先求解出 $A$，然后在此基础上加入 $B$ 的边即可得到 $A \cup B$ 的答案。

由于并查集不能路径压缩，最后时间复杂度为 $O(q \log q \log n)$，代码如下：

#include <bits/stdc++.h>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define pii pair <int,int> 
using namespace std;
const int MAX = 4e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
pii st[MAX],e[MAX]; 
vector <pii> ve[MAX << 2];
map <pii,int> mp;
int n,q,top,ans[3][MAX],fa[MAX],sz[MAX];char ty[MAX][1];
int getfa (int u);
bool merge (int u,int v);
void modify (int cur,int l,int r,int x,int y,pii v);
void solve (int res[],int cur,int l,int r,int tot);
int main ()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    n = read ();q = read ();
    for (int i = 1;i <= n;++i) fa[i] = i,sz[i] = 1;
    for (int i = 1;i <= q;++i)
    {
        scanf ("%s",ty[i]);int u = read (),v = read ();
        if (u > v) swap (u,v);
        e[i] = {u,v};
    }
    for (int i = 1;i <= q;++i)
    {
        if (ty[i][0] == 'B') continue;
        if (!mp[e[i]]) mp[e[i]] = i;
        else 
        {
            modify (1,1,q,mp[e[i]],i - 1,e[i]);
            mp[e[i]] = 0;
        }
    }
    for (auto item : mp)
        if (item.second) modify (1,1,q,item.second,q,item.first);
    solve (ans[1],1,1,q,n);
    mp.clear ();
    for (int i = 1;i <= q;++i)
    {
        if (ty[i][0] == 'A') continue;
        if (!mp[e[i]]) mp[e[i]] = i;
        else
        {
            modify (1,1,q,mp[e[i]],i - 1,e[i]);
            mp[e[i]] = 0;
        }
    }
    for (auto item : mp)
        if (item.second) modify (1,1,q,item.second,q,item.first);
    solve (ans[2],1,1,q,n);
    for (int i = 1;i <= q;++i) printf ("\t%d\n",ans[1][i] - ans[2][i]);//A - A U B
    return 0;
}
inline int read ()
{
    int s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
    {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}
int getfa (int u) {return fa[u] == u ? u : getfa (fa[u]);} 
bool merge (int u,int v)
{
    u = getfa (u),v = getfa (v);
    if (u == v) return 0;
    if (sz[u] > sz[v]) swap (u,v);
    st[++top] = {u,v};// u -> v
    fa[u] = v;sz[v] += sz[u];
    return 1;
}
void modify (int cur,int l,int r,int x,int y,pii v)
{
    if (x <= l && y >= r) {ve[cur].push_back (v);return ;}
    int mid = (l + r) >> 1;
    if (x <= mid) modify (cur << 1,l,mid,x,y,v);
    if (y > mid) modify (cur << 1 | 1,mid + 1,r,x,y,v); 
}
void solve (int res[],int cur,int l,int r,int tot)
{
    int la = top;
    for (auto p : ve[cur]) tot -= merge (p.first,p.second);
    if (l == r) res[l] = tot;
    else
    {
        int mid = (l + r) >> 1;
        solve (res,cur << 1,l,mid,tot);solve (res,cur << 1 | 1,mid + 1,r,tot);
    }
    while (top > la)
    {
        sz[st[top].second] -= sz[st[top].first];
        fa[st[top].first] = st[top].first;
        --top;
    }
}