线段树分治+可撤销并查集 学习笔记

题目一般是给你边或者点的出现时间区间[Li,Ri]，问你在某些时间里1能访问到的点或者点的数量。

先考虑暴力的思路，就是对于一个具体的时间节点，我们去暴力地得知当前边/点是否出现，并且跑图查看是否联通。

由于一个具体的时间节点前后联通情况大致相似，我们考虑是否可以在继承前一个时间节点的情况下，只是局部改变一些点和边的情况？

因为我们是去查看图的联通，免不了使用并查集。当一条边加入进来好处理，但如果删除呢？

线段树分治+可撤销并查集就是用来解决此类问题。

将每条边的时间线段用线段树来分开，每条线段只会分成log个，并且可以保证分完后的所有线段不相交。我们以时间为轴，记录线段树上每个时间区间覆盖的边，然后对线段树进行 DFS，进入一个区间就在并查集里加入这个区间的所有边，离开时再撤销这些边。

可撤销并查集，实际上就是一个用一个栈，在撤销时把最近加入栈中的边回滚掉。回滚的操作就是将原来的一棵树砍下一个树枝，变成两棵树。（那么此时我们就不可以用原来的路径压缩去维护并查集，因为这样会破坏原来的并查集结构。but我们可以用启发式并查集任然可以做到Ologn的复杂度。） 当删除一条边时，我们将父亲的标记下放给儿子（这里可能说的不准确，应该是父联通块的标记下传给即将分裂出去的儿子连通块），而加入一条边，为了避免重复加，我们需要减去之前父亲连通块的标记（不必担心会多减，因为最终所有的点都会分裂出去），在所有边都分裂完之后，就能保证原来的整个连通块都打上标记。

线段树分治的重点在于叶子结点，当 DFS 到叶子结点时，就是到了某个具体的时间点，我们可以对在这个时间点下的答案进行计算或者维护。

Problem - F - Codeforces

板子题

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define FOR() int le=e[u].size();for(int i=0;i<le;i++)
#define QWQ cout<<"QwQ\n";
#define ll long long

#include <vector>
#include <queue>
#include <map>

#define ls now<<1
#define rs (now<<1|1)

using namespace std;
const int N = 1001010;
const int M = 2e5;
const int qwq = 303030;
const int inf = 0x3f3f3f3f;

inline int read() {
    int sum = 0, ff = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') ff = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        sum = sum * 10 + c - '0';
        c = getchar();
    }
    return sum * ff;
}

int n, m, L[N], R[N], fa[N], tag[N];
vector<pair<int, int> > e[N << 3];

void insert(int p, int l, int r, int x, int y, int u, int v) {

    if (x <= l && r <= y) {
        e[p].emplace_back(u, v);
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) insert(p << 1, l, mid, x, y, u, v);
    if (y > mid) insert(p << 1 | 1, mid + 1, r, x, y, u, v);

}

int tot, deep[N];
struct node {
    int x, y, depy;
} st[N << 3];

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

void merge(int u, int v) {
    int fu = find(u), fv = find(v);
    if (fu == fv) return;
    if (deep[fu] > deep[fv])swap(fu, fv);
    st[++tot] = {fu, fv, deep[fv]};
    fa[fu] = fv;
    deep[fv] += (deep[fu] == deep[fv]);
    tag[fu] -= tag[fv];
}

void roll_back(int sz) {

    while (tot && sz < tot) {
        const auto &[x, y, depy] = st[tot];
        fa[x] = x;
        deep[y] = depy;
        tag[x] += tag[y];
        tot--;

    }
}

void dfs(int p, int l, int r) {
    int sz = tot;
    for (auto [u, v]: e[p]) {
        merge(u, v);
    }
    if (l == r) {
        tag[find(1)]++;
    } else {
        int mid = (l + r) >> 1;
        dfs(p << 1, l, mid);
        dfs(p << 1 | 1, mid + 1, r);
    }
    roll_back(sz);

}

int main() {
    int x, y;
    n = read();
    m = read();

    for (int i = 1; i <= n; i++) {
        L[i] = read(), R[i] = read();
    }
    for (int i = 1; i <= m; i++) {
        x = read();
        y = read();
        int le = max(L[x], L[y]);
        int re = min(R[x], R[y]);
        if (le <= re) insert(1, 1, M, le, re, x, y);
    }
    for (int i = 1; i <= n; i++) fa[i] = i;
    dfs(1, 1, M);
    for (int i = 1; i <= n; i++) if (tag[i]) printf("%d ", i);
    return 0;
}

传送

有一个 n 个节点 m 条边的无向图，对于一条边有四个参数 (a,b,l,r) ，表示这条边在 [l,r] 这些时间连接 (a,b) 。

有一个传送技能：如果在某时刻 u 和 v 在一个连通块里，可以从 u 传送到 v 。

小 A 初始在节点 1 ，所以 小 A 想知道他能在 [1,n] 中的哪些时间点能直接从 1 传送到节点 i ，请你帮帮他。

由于输出量可能过大，考虑简化输出，假设所有能从 1 到达 i 的时间点为 ti,1…ti,k ，定义 ansi=∑kj=1ti,j ，你只需要输出一个 ⊕ni=1ansi 即可，其中 ⊕ 表示异或和。

杭电oj咋回事，一样的代码交了好几遍，有时候T有时候能过，有没有人给看看

#include <algorithm>
#include <iostream>
#include <vector>
#define ls now<<1
#define rs (now<<1|1)
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;

int n, m;
vector<pair<int, int> > t[N << 2];
struct CZ {
    int x, y, depy;
} st[N];
int fa[N], dep[N];
ll tag[N];
int cnt;

inline int read() {
    int sum = 0, ff = 1; char c = getchar();
    while(c<'0' || c>'9') { if(c=='-') ff = -1; c = getchar(); }
    while(c>='0'&&c<='9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return sum * ff;
}

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

void insert(int now, int l, int r, int x, int y, int u,int v) {
    if (x <= l && r <= y) {
        t[now].emplace_back(u,v);
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid) insert(ls, l, mid, x, y, u,v);
    if (y > mid) insert(rs, mid + 1, r, x, y, u,v);
}

void merge(int x, int y) {
    int xx = find(x), yy = find(y);
    if (xx == yy) return;
    if (dep[xx] > dep[yy]) swap(xx, yy);
    st[++cnt] = {xx, yy, dep[yy]};
    fa[xx] = yy;
    if (dep[xx] == dep[yy]) dep[yy]++;
    tag[xx] -= tag[yy];
}

void DFS(int now, int l, int r) {
    int sz = cnt;
    for(auto &[u,v] : t[now]){
        merge(u,v);
    }
    if (l == r) {
        tag[find(1)] += l;
    } else {
        int mid = l + r >> 1;
        DFS(ls, l, mid);
        DFS(rs, mid + 1, r);
    }
    while (cnt > sz && cnt >=0 ) {
        const auto &[x,y,deep] = st[cnt];
        fa[x] = x;
        tag[x] += tag[y];
        dep[y] = deep;
        cnt -- ;
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    n = read(),m=read();
    for (int i = 1,x,y,le,re; i <= m; i++) {
        x=read();
        y=read();
        le=read();
        re=read();
         insert(1, 1, n, le, re, x, y);
    }

    for (int i = 1; i <= n; i++) fa[i] = i;
    DFS(1, 1, n);
    ll ans = 0;

    for (int i = 1; i <= n; i++) {
        ans ^= tag[i];
    }
    printf("%lld" ,ans);
    return 0;
}