线段树分治+可撤销并查集 学习笔记
题目一般是给你边或者点的出现时间区间[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;
}