时间线段树(线段树分治)学习笔记
思想
考虑如下问题:
进行若干次操作,每次操作都在一个时间段内有效,也就是先被添加然后可能被撤销。同时还进行询问,对于每个时刻,输出所有操作的贡献。
当这类题目在线比较难做时,就可能需要离线,并按照时间进行分治。分治的方法有两种,一种是采用时间线段树(又称线段树分治),另一种是采用 以前我总结过的一类分治 ,可以根据不同的题目看看哪种更适合。
时间线段树顾名思义,是在时间轴上建了一棵线段树,这样我们就把每个操作变为了线段树上的区间修改。算法流程是遍历整棵线段树,到达一个节点时执行这个节点的所有操作,然后继续向下递归,回溯时将操作撤销即可。
例题:P5787 二分图 /【模板】线段树分治
一个图是二分图的充要条件是图中不存在奇环,这个可以使用扩展域并查集维护。
然后照着算法流程做就好了。注意到回溯的时候需要撤销操作,因此需要使用可撤销并查集。为了撤销操作,并查集的形态需要被维持,因此采用按秩合并优化,注意不能采用路径压缩优化。在合并时,若 \(u\) 变成了 \(v\) 的父亲,就在操作栈中记录节点 \(v\) 以及这次合并导致 \(u\) 的秩的增加量。撤销时依次弹栈得到 \(v\),在并查集中找到 \(v\) 的父亲 \(u\)(这就是不能动并查集形态的原因),利用秩的增加量信息恢复 \(u\) 的秩,然后将 \(v\) 的父亲设为自己即可。
时间复杂度 \(\Theta(m\log n\log k)\)。
// Problem: P5787 二分图 /【模板】线段树分治
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5787
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 2e5+5;
int n, m, k, U[N], V[N], fa[N], rk[N];
stack<tuple<int, int>> undo;
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
int find(int x) {return x == fa[x] ? x : find(fa[x]);}
void merge(int x, int y) {
x = find(x); y = find(y);
if(rk[x] < rk[y]) swap(x, y);
undo.emplace(y, rk[x] == rk[y]);
chkmax(rk[x], rk[y] + 1);
fa[y] = x;
}
struct SegTree {
vector<int> t[N<<2];
#define lc(u) (u<<1)
#define rc(u) (u<<1|1)
void insert(int u, int l, int r, int ql, int qr, int id) {
if(ql > qr) return;
if(ql <= l && r <= qr) {
t[u].push_back(id);
return;
}
int mid = (l + r) >> 1;
if(ql <= mid) insert(lc(u), l, mid, ql, qr, id);
if(qr > mid) insert(rc(u), mid+1, r, ql, qr, id);
}
void solve(int p, int l, int r) {
bool ok = 1;
int sz = undo.size();
for(int i : t[p]) {
int u = find(U[i]), v = find(V[i]);
if(u == v) {
rep(i, l, r) puts("No");
ok = 0;
break;
}
merge(U[i]+n, V[i]);
merge(U[i], V[i]+n);
}
if(ok) {
if(l == r) puts("Yes");
else {
int mid = (l + r) >> 1;
solve(lc(p), l, mid);
solve(rc(p), mid+1, r);
}
}
while((int)undo.size() > sz) {
int u = get<0>(undo.top()), d = get<1>(undo.top()); undo.pop();
rk[fa[u]] -= d;
fa[u] = u;
}
}
#undef lc
#undef rc
}sgt;
int main() {
scanf("%d%d%d", &n, &m, &k);
rep(i, 1, 2*n) fa[i] = i, rk[i] = 0;
rep(i, 1, m) {
int l, r;
scanf("%d%d%d%d", &U[i], &V[i], &l, &r);
sgt.insert(1, 1, k, l+1, r, i);
}
sgt.solve(1, 1, k);
return 0;
}
标签:int,线段,分治,undo,fa,笔记,rk
From: https://www.cnblogs.com/ruierqwq/p/segment-tree-offline.html