题目一般是给你边或者点的出现时间区间[Li,Ri],问你在某些时间里1能访问到的点或者点的数量。
先考虑暴力的思路,就是对于一个具体的时间节点,我们去暴力地得知当前边/点是否出现,并且跑图查看是否联通。
由于一个具体的时间节点前后联通情况大致相似,我们考虑是否可以在继承前一个时间节点的情况下,只是局部改变一些点和边的情况?
因为我们是去查看图的联通,免不了使用并查集。当一条边加入进来好处理,但如果删除呢?
线段树分治+可撤销并查集就是用来解决此类问题。
将每条边的时间线段用线段树来分开,每条线段只会分成log个,并且可以保证分完后的所有线段不相交。我们以时间为轴,记录线段树上每个时间区间覆盖的边,然后对线段树进行 DFS,进入一个区间就在并查集里加入这个区间的所有边,离开时再撤销这些边。
可撤销并查集,实际上就是一个用一个栈,在撤销时把最近加入栈中的边回滚掉。回滚的操作就是将原来的一棵树砍下一个树枝,变成两棵树。(那么此时我们就不可以用原来的路径压缩去维护并查集,因为这样会破坏原来的并查集结构。but我们可以用启发式并查集任然可以做到Ologn的复杂度。) 当删除一条边时,我们将父亲的标记下放给儿子(这里可能说的不准确,应该是父联通块的标记下传给即将分裂出去的儿子连通块),而加入一条边,为了避免重复加,我们需要减去之前父亲连通块的标记(不必担心会多减,因为最终所有的点都会分裂出去),在所有边都分裂完之后,就能保证原来的整个连通块都打上标记。
线段树分治的重点在于叶子结点,当 DFS 到叶子结点时,就是到了某个具体的时间点,我们可以对在这个时间点下的答案进行计算或者维护。
板子题
#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;
}