题解：P4246 [SHOI2008] 堵塞的交通

先简单说下线段树分治。

字面意思，就是按照每次操作的时间进行分治（对于可撤销的）。

很明显，对于图的连通性并查集秒了。对于删边操作，就用可撤销并查集维护就好了。那怎么样在一段区间上加边删边呢？很简单，类似于懒标记，要加的边先放在节点上，最后遍历的时候，直接下传就好了。

需要注意的是，因为每次是一段区间，所以最后要清空此时的操作。

对于这道题，用 map 维护每条边第一次加入时的时间（后面用 a 指代），如果要删除这条边，记删除这条边时的时间为 b ，就相当于是把 a \to b - 1 的时间段给加上一条边。

最后记住把没加进去的边（直到最后都没被删）加进线段树就好了。

时间复杂度 O (n \log ^ 2 {n}) ，包能过得。

code：

# include <bits/stdc++.h>
# define endl '\n'
using namespace std;
using size_s = unsigned int;
const int N = 1000000 + 11;
vector <int> q;
int fa[N], siz[N];
int qx[N], qy[N];
int n, m;
int find (int x)
{
    return x == fa[x] ? x : find (fa[x]);
}
bool merge (int x, int y)
{
    x = find (x), y = find (y);
    if (x == y) return 0;
    if (siz[x] < siz[y])
    {
        swap (x, y);
    }
    fa[y] = x;
    siz[x] += siz[y];
    q.push_back (y);
    return 1;
}
void cut ()
{
    int x = q.back ();
    q.pop_back ();
    int y = fa[x];
    fa[x] = x;
    siz[y] -= siz[x];
}
string op[N];
struct SegTree
{
    size_s l, r, mid;
    SegTree *ls, *rs;
    vector <int> stk;
    SegTree (size_s s, size_s t) :
    l {s}, r {t}, mid { (l + r) >> 1 },
    ls {nullptr}, rs {nullptr}
    {
        if (l == r)
        {
            return;
        }
        ls = new SegTree (l, mid + 0);
        rs = new SegTree (mid + 1, r);
    }
    void modify (size_s s, size_s t, int x)
    {
        if (l >= s and r <= t)
        {
            stk.push_back (x);
            return;
        }
        if (mid >= s) ls -> modify (s, t, x);
        if (mid <  t) rs -> modify (s, t, x);
    }
    void solve ()
    {
        int cnt = 0;
        for (auto it : stk)
        {
            int u = qx[it], v = qy[it];
            cnt += merge (u, v);
        }
        if (l == r)
        {
            if (op[l] == "Ask")
            {
                int x = qx[l], y = qy[l];
                if (find (x) == find (y))
                {
                    cout << "Y" << endl;
                }
                else
                {
                    cout << "N" << endl;
                }
            }
        }
        else
        {
            ls -> solve ();
            rs -> solve ();
        }
        while (cnt --)
        {
            cut ();
        }
    }
};
//# define first fi
//# define second se
map <int, map <int, int> > mp;
int main ()
{
    ios :: sync_with_stdio (0);
    cin.tie (0), cout.tie (0);
    cin >> n;
    for (int i = 1; i <= n * 2; i ++)
    {
        fa[i] = i, siz[i] = 1;
    }
    SegTree tr (1, 1e5 + 5);
    while (cin >> op[++ m])
    {
        if (op[m] == "Exit") break;
        int r1, c1, r2 = 0, c2 = 0;
        int x = 0, y = 0;
        cin >> r1 >> c1 >> r2 >> c2;
        x = (r1 - 1) * n + c1;
        y = (r2 - 1) * n + c2;
        if (x > y) swap (x, y);
        qx[m] = x, qy[m] = y;
        if (op[m] == "Open")
        {
            mp[x][y] = m;
        }
        else if (op[m] == "Close")
        {
            tr.modify (mp[x][y], m - 1, m);
            mp[x].erase (mp[x].find (y));
        }
    }
    for (int u = 1; u <= n * 2; u ++)
    {
        for (auto v : mp[u])
        {
            tr.modify (v.second, m, v.second);
        }
    }
    tr.solve ();
}