神奇化合物

题目来源：SHOI 2014 DAY 2 T 1

题意：

给定一个无向图，有删边、添边两种操作，还有询问当前图中连通块个数。点数 $n\leq 5000$, 边数 $m\leq 200000$, 询问和操作总数 $q\leq 10000$。

解法一：

一种并不普适的做法。

如果只有添边操作，那么连通块个数是单调下降的，所以我们用并查集维护即可。如果只有删边操作，那么连通块个数单调上升，所以我们还是可以将时间逆转，化删边为添边，继续用并查集维护。

但是同时遇到两种操作，并查集就不起效果了。

所以，我们面向数据编程。

数据说，询问和操作总数很少，所以真正被删掉或者新添加的边很少。这样，就会存在很多没有被任何操作影响到的联通快，苟全性命于乱世。所以，我们把这些连通块缩点，再用暴力染色求联通快个数，于是事就这样成了。

时间复杂度 $O(q(n+q))$

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <map>
#define MX 800008
#define MQ 10001
using namespace std;

struct graph
{   
    int n;
    int fst[MX],nxt[MX],u[MX],v[MX],lnum;
    int wei[MX];
    map<pair<int,int>,int>mp;
    void init(int a){memset(fst,0xff,sizeof(fst));lnum=-1;mp.clear();n=a;}
    void addeg(int nu,int nv)
    {
        nxt[++lnum]=fst[nu];
        fst[nu]=lnum;
        u[lnum]=nu;
        v[lnum]=nv;
        wei[lnum]=1;
        mp[make_pair(nu,nv)]=lnum+100;
    }
    int vis[MX],vnum;
    void dfs(int x,int c)
    {
        if(vis[x]==c)return;
        vis[x]=c;
        for(int i=fst[x];i!=-1;i=nxt[i])
            if(vis[v[i]]!=c&&wei[i])
                dfs(v[i],c);
    }
    int color()
    {
        memset(vis,0,sizeof(vis));
        vnum=0;
        for(int i=1;i<=n;i++)
            if(!vis[i])
                dfs(i,++vnum);
        return vnum;
    }
    void cut(int a,int b)
    {
        int e=mp[make_pair(a,b)]-100,f=e^1;
        if(e<0||wei[e]==0);
        else wei[e]--,wei[f]--;
    }
    void join(int a,int b)
    {
        int e=mp[make_pair(a,b)]-100,f=e^1;
        if(e<0)addeg(a,b),addeg(b,a);
        else wei[e]++,wei[f]++;
    }
}g1,g2;
struct qeury
{
    char o;
    int a,b;
}qur[MQ];
int n,m,q;

void input()
{
    int a,b;char ch;
    scanf("%d%d",&n,&m);
    g1.init(n);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        g1.join(a,b);
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        ch=getchar();
        while(ch!='A'&&ch!='D'&ch!='Q')ch=getchar();
        qur[i].o=ch;
        if(ch=='A'||ch=='D')scanf("%d%d",&qur[i].a,&qur[i].b);
    }
}

void prework()
{
    for(int i=1;i<=q;i++)if(qur[i].o=='D')g1.cut(qur[i].a,qur[i].b);
    g2.init(g1.color());
    for(int i=0;i<=g1.lnum;i+=2)
        if(g1.vis[g1.u[i]]!=g1.vis[g1.v[i]])
            g2.join(g1.vis[g1.u[i]],g1.vis[g1.v[i]]);
    for(int i=1;i<=q;i++)qur[i].a=g1.vis[qur[i].a],qur[i].b=g1.vis[qur[i].b];
}

void work()
{
    for(int i=1;i<=q;i++)
    {
        if(qur[i].o=='A')g2.join(qur[i].a,qur[i].b);
        else if(qur[i].o=='D')g2.cut(qur[i].a,qur[i].b);
        else printf("%d\n",g2.color());
    }
}

int main()
{
    input();
    prework();
    work();
    return 0;
}

解法二：

如果我们还是固执地想用并查集，其实还是有解决办法的。

并查集有这样一种性质：按秩合并的并查集可以花 $O(n)$的复杂度回退到先前版本。所以，对于相邻两个询问，我们是可以找到哪个时刻的并查集可以发展出这两个询问时刻的版本。于是，我们把第一个时刻的并查集退回到这个时刻，然后再发展成第二个时刻的版本，事就这样成了。

这样的方法并不是非常方便，因为我们不知道两个时刻的询问之间的重复部分具体有多少，因此，我们需要借助一个工具：时间线段树。

首先，我们求出每一条边在整个过程中出现的连续时间段。将这些边加入线段树中。每一条边至多在线段树的 $logn$个区间中出现。可以想象，这棵线段树对应的是一条时间轴，时间轴上的每一个点都代表一个时刻的图的形态。如果要查找一个时间点的图的联通快个数，我们将线段树中的 $logn$覆盖了这个点的个区间中的边全部加入图中，利用并查集维护联通块个数，就可以得到答案。但是这还不是最优的时间复杂度。

我们直接对线段树 dfs，利用可以回退的并查集，我们是可以做到 $O(nlog^2n)$的。

一个小 trick: 线段树上没有询问用到的区间我们不去管他。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <map>
#define MX 200005
#define MT 10001
#define mid ((l+r)>>1)
#define ls (a<<1)
#define rs (a<<1|1)

using namespace std;

struct edge
{
    int u,v;
    bool operator < (const edge a)const
    {
        if(min(u,v)!=min(a.u,a.v))return min(u,v)<min(a.u,a.v);
        else return max(u,v)<max(a.u,a.v);
    }
};
struct node
{
    int l,r,v;
    vector<edge>e;
}tre[MT*4];
map<edge,int>mp;
edge e[MX];
int lnum;
int beg[MX],fin[MX];
int qtm[MT],fa[MX],siz[MX],ccnum;
int n,m,q;

int findfa(int x){return (fa[x]==x?x:findfa(fa[x]));}

void cut(int y){if(y)ccnum++,siz[fa[y]]-=siz[y],fa[y]=y;}

int join(int x,int y)
{
    int f1=findfa(x),f2=findfa(y);
    if(siz[f1]>siz[f2])swap(f1,f2);
    if(f1==f2)return 0;
    else
    {
        ccnum--;
        siz[f1]+=siz[f2];
        fa[f2]=f1;
        return f2;
    }
}

void input()
{
    int a,b;char ch;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        e[++lnum]=(edge){a,b};
        mp[e[lnum]]=lnum;
        beg[lnum]=1;
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        ch=getchar();
        while(ch!='A'&&ch!='D'&&ch!='Q')ch=getchar();
        if(ch=='A')
        {
            scanf("%d%d",&a,&b);
            e[++lnum]=(edge){a,b};
            mp[e[lnum]]=lnum;
            beg[lnum]=i;
        }
        else if(ch=='D')
        {
            scanf("%d%d",&a,&b);
            fin[mp[(edge){a,b}]]=i;
            mp[(edge){a,b}]=0;
        }
        else qtm[i]=1;
    }
    for(int i=1;i<=lnum;i++)if(!fin[i])fin[i]=q;
}

void build(int a,int l,int r)
{
    tre[a].l=l,tre[a].r=r;
    tre[a].e.clear();
    if(l==r)tre[a].v=qtm[l];
    else build(ls,l,mid),build(rs,mid+1,r),tre[a].v=tre[ls].v|tre[rs].v;
}

void insrt(int a,int ql,int qr,edge eg)
{
    int l=tre[a].l,r=tre[a].r;
    if(ql<=l&&r<=qr){if(tre[a].v)tre[a].e.push_back(eg);}
    else if(ql>r||qr<l)return;
    else insrt(ls,ql,qr,eg),insrt(rs,ql,qr,eg);
}

void dfs(int a)
{
    vector<int>tmp;
    int l=tre[a].l,r=tre[a].r;
    for(int i=0;i<tre[a].e.size();i++)tmp.push_back(join(tre[a].e[i].u,tre[a].e[i].v));
    if(l==r)printf("%d\n",ccnum);
    else {if(tre[ls].v)dfs(ls);if(tre[rs].v)dfs(rs);}
    for(int i=0;i<tre[a].e.size();i++)cut(tmp[i]);
}

int main()
{
    input();
    for(int i=1;i<=n;i++)siz[i]=1,fa[i]=i;
    build(1,1,q);
    for(int i=1;i<=lnum;i++)insrt(1,beg[i],fin[i],e[i]);
    ccnum=n;
    dfs(1);
    return 0;
}

#include <bits/stdc++.h>

#define NS (5005)
#define QS (10005)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; dig = 0;
    while (c = getchar(), !isdigit(c));
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
}

int n, m, q, o[QS], x[QS], y[QS], cur[NS], cnt;

bool g1[NS][NS], book[NS][NS], vis[NS];

char opt[10];

map<int, int> g[NS];

void Init(int a)
{
    vis[a] = 1, cur[a] = cnt;
    for (int i = 1; i <= n; i += 1)
        if (g1[a][i] && !book[a][i] && !vis[i])
            Init(i);
}

void dfs(int a)
{
    vis[a] = 1;
    for (map<int, int>::iterator i = g[a].begin(); i != g[a].end(); i++)
        if (!vis[i->first]) dfs(i->first);
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m);
    for (int i = 1, a, b; i <= m; i += 1)
        IN(a), IN(b), g1[a][b] = g1[b][a] = 1;
    IN(q);
    for (int i = 1; i <= q; i += 1)
    {
        scanf("%s", opt);
        if (opt[0] == 'Q') o[i] = 0;
        else if (opt[0] == 'A') IN(x[i]), IN(y[i]), o[i] = 1;
        else
        {
            IN(x[i]), IN(y[i]), o[i] = 2;
            book[x[i]][y[i]] = book[y[i]][x[i]] = 1;
        }
    }
    for (int i = 1; i <= n; i += 1)
        if (!vis[i]) cnt += 1, Init(i);
    for (int i = 1; i <= n; i += 1)
        for (int j = 1; j <= n; j += 1)
            if (g1[i][j] && cur[i] != cur[j])
                g[cur[i]][cur[j]]++;
    for (int i = 1, ans; i <= q; i += 1)
        if (!o[i])
        {
            ans = 0, memset(vis, 0, sizeof(vis));
            for (int j = 1; j <= cnt; j += 1)
                if (!vis[j]) dfs(j), ans += 1;
            printf("%d\n", ans);
        }
        else if (o[i] == 1)
        {
            if (cur[x[i]] != cur[y[i]])
                g[cur[x[i]]][cur[y[i]]]++, g[cur[y[i]]][cur[x[i]]]++;
        }
        else
        {
            if (cur[x[i]] != cur[y[i]])
            {
                g[cur[x[i]]][cur[y[i]]]--, g[cur[y[i]]][cur[x[i]]]--;
                if (!g[cur[x[i]]][cur[y[i]]])
                {
                    g[cur[x[i]]].erase(g[cur[x[i]]].find(cur[y[i]]));
                    g[cur[y[i]]].erase(g[cur[y[i]]].find(cur[x[i]]));
                }
            }
        }
    return 0;
}