线段树分治

定义

线段树的本质就是 分治的实体化。

我理解的狭义上的线段树指的是支持区间查询修改的一种数据结构，而广义上的线段树则是一种思想——分治实体化的思想。

线段树分治就是由这种思想催生出的产物（同样的还有线段树优化建边）。

线段树分治有一个别名叫 时间分治，它的主要思想就是对于一些在线算法比较难写的动态问题中，维护整个动态问题的时间轴，从而离线地高效解决整个问题。

想法

具体而言，如果有这么一个问题：
你要维护一张无向简单图。你被要求加入删除一条边及查询两个点是否连通。

• 0：加入一条边。保证它不存在。
• 1：删除一条边。保证它存在。
• 2：查询两个点是否连通。

如果想要在线地解决这个问题比较麻烦（那个L什么什么CT同学，我就不点名了），发现每条边都只存在于某一段区间，我们可以把整个问题的修改操作放到时间轴上。

例如样例2：

最后得到的结果为 N Y Y N

我们在时间轴上建立线段树

因此对于每一个查询我们只需要考虑这个时间点（叶子）到根的路径上的所有边即可，可以用并查集维护两点连通性。

优化

但是难道我们需要对每个查询都建一个并查集吗？可以观察到，两个查询所构成的图之间是有重复的边的，从这一点入手，我们只需要使用 UNDO 并查集+按轶合并优化 就可以把时间复杂度优化到 \(O(n\log m\log n)\)，\(m\) 是时间轴的长度。

实现

// Problem: #121. 「离线可过」动态图连通性
// Contest: LibreOJ
// URL: https://loj.ac/p/121
// Memory Limit: 512 MB
// Time Limit: 800 ms
// Author: Moyou
// Copyright (c) 2022 Moyou All rights reserved.
// Date: 2023-01-21 15:28:46

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#define x first
#define y second
#define speedup (ios::sync_with_stdio(0), cin.tie(0), cout.tie(0))
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e6 + 10, M = 2e6 + 10;

int tim = 1;

map<PII, PII> e;
struct qwq
{
    int u, v;
};
vector<qwq> query[N];
int es[N];

int fa[N], sz[N], top;
int stk[N];
void init(int n)
{
    for (int i = 1; i <= n; i++)
        fa[i] = i, sz[i] = 1;
}

inline int find(int x)
{
    while (x != fa[x])
        x = fa[x];
    return x;
}
inline bool merge(int a, int b)
{
    int x = find(a), y = find(b);
    if (x == y)
        return 1;
    if (sz[x] > sz[y])
        swap(x, y);
    fa[x] = y, sz[y] += sz[x];
    stk[++top] = {x};
    return 0;
}

inline void undo()
{
    int t = stk[top--];
    sz[fa[t]] -= sz[t];
    fa[t] = t;
}

inline bool same(int a, int b)
{
    return find(a) == find(b);
}

vector<PII> dat[M];
void update(int k, int l, int r, int ll, int rr, PII x)
{
    if (ll > r || rr < l)
        return;
    if (ll <= l && rr >= r)
    {
        dat[k].push_back(x);
        return;
    }
    int mid = l + r >> 1;
    if(ll <= mid) update(k << 1, l, mid, ll, rr, x);
    if(rr > mid) update(k << 1 | 1, mid + 1, r, ll, rr, x);
}

void solve(int k, int l, int r)
{
    int backup = top;
    for (auto [u, v] : dat[k])
        merge(u, v);
    if (l == r)
    {
        for (auto [u, v] : query[l])
            puts(same(u, v) ? "Y" : "N");
    }
    else
    {
        int mid = l + r >> 1;
        solve(k << 1, l, mid);
        solve(k << 1 | 1, mid + 1, r);
    }
    while (top > backup)
        undo();
}

signed main()
{
    int n, m;
    cin >> n >> m;
    init(n);
    for (int i = 1; i <= m; i++)
    {
        int op, u, v;
        cin >> op >> u >> v;
        if(u > v) swap(u, v);
        if (!op) // 加边
            e[{u, v}] = {++tim, 0};
        else if (op == 1)
            e[{u, v}].y = tim ++;
        else
            query[tim].push_back({u, v});
    }

    for (auto [key, val] : e)
    {
        if(!val.y) val.y = m;
        update(1, 1, tim, val.x, val.y, key);
    }
    solve(1, 1, tim);
    cout << ' ';
    return 0;
    puts("我永远喜欢伊蕾娜~！！");
}