线段树分治总结

概念
例题
- 二分图 /【模板】线段树分治
- [HAOI2017] 八纵八横
- [FJOI2015] 火星商店问题
- Envy
- Extending Set of Points
- Forced Online Queries Problem
- 「雅礼集训 2018 Day10」贪玩蓝月
- BZOJ4184-shallot
- [bzoj4644]经典**题

概念

$\qquad$ 线段树分治一般用来解决带有如下两个特征的问题：1、一些操作只在某一特定时间段生效；2、查询某一时间点上所有操作的结果。我们可以对时间建立一棵线段树，把操作挂在线段树对应节点上，询问挂在叶子节点上，然后从根节点开始从左到右遍历线段树。每次进入一个新节点就完成当前节点处挂的操作，从某一结点回溯时把它上面挂的操作撤销，到叶子节点查询即可。所以线段树合并总是与支持添加、撤销的数据结构结合。

例题

二分图 /【模板】线段树分治

$\qquad$ 题面

$\qquad$ 线段树分治模板题。

$\qquad$ 判断一张图是否是二分图，一般用的都是染色法，看有没有相邻两个点颜色相同。但是在本题中图是动态的，显然我们每次不能重新跑一遍图。此时，我们就要用另一种方法：拓展域并查集。因为要撤销，所以我们不能写路径压缩，而应该写按秩合并。

$\qquad$ 核心 $C o d e :$

void solve(int p) {
	int cnt = 0;
	bool flag = 1;
	for(int i : qs(p)) {//把挂在当前节点的边添加到并查集中
		if(B.Find(a[i].x) == B.Find(a[i].y)) {//若当前已经不是二分图，再加边就更不是二分图了
			for(int j = l(p); j <= r(p); j ++) bol[j] = 1;
			flag = 0;
			break;
		}
		B.merge(a[i].x + n, a[i].y, cnt), B.merge(a[i].x, a[i].y + n, cnt);
	}
	if(flag && l(p) != r(p)) solve(p << 1), solve(p << 1 | 1);
	while(cnt --) {//撤销
		Node Top = s.top(); s.pop();
		B.bin[Top.x] = Top.x, B.dep[Top.fa] -= Top.dep;
	}
}

[HAOI2017] 八纵八横

$\qquad$ 题面

$\qquad$ 线段树分治套线性基。

$\qquad$ 只要提到异或，他那很好的性质总是能给我们带来很大的便利： $x\oplus x=0$ 。在本题中，我们的任务实际上是找到几个环使得他们权值的异或和最大。因为最终的路径是以首都为开头、结尾的环，环上的边是可以由其他环拼出来的（选两次相当于没选）。那么我们如何找到图上所有的环呢？一个结论是我们在一开始任意找一个图的生成树，那么我们仅需记录新加的边与生成树形成的环便可组成所有的环。根据这个结论，套上一个线段树分治即可。

$\qquad$ 核心 $C o d e :$

//并查集操作
int Find(int x) {
	while(x != bin[x]) x = bin[x];
	return x;
}
bt Find_dis(int x) {//路径权值异或和
	bt res;
	res.reset();
	while(x != bin[x]) res ^= dis[x], x = bin[x];
	res ^= dis[x];
	return res;
}
void merge(node Now) {
	int x = Now.x, y = Now.y; bt z = Now.w;
	int fx = Find(x), fy = Find(y);
	if(fx == fy) return G.Insert(Find_dis(x) ^ Find_dis(y) ^ z), void();
	if(sze[fx] > sze[fy]) swap(fx, fy), swap(x, y);
	stk.push({fx, fy, sze[fy]});
	dis[fx] = Find_dis(x) ^ Find_dis(y) ^ z;
	bin[fx] = fy, sze[fy] += sze[fx];
}

[FJOI2015] 火星商店问题

$\qquad$ 题面

$\qquad$ 线段树分治套可持久化 $01 t r i e$ 。

$\qquad$ 其实主要就题面将恶心点，写起来还是很顺的。

$\qquad$ 核心 $C o d e :$

//可持久化01trie
struct Trie {
	int tr[maxn * 20][2], num[maxn * 20], tot = 0;
	
	inline int build() {
		return ++ tot;
	}
	
	void Insert(int p, int q, int val) {
		num[p] = num[q] + 1;
		for(int i = 19; ~i; i --) {
			int x = ((val >> i) & 1);
			tr[p][x ^ 1] = tr[q][x ^ 1], tr[p][x] = build();
			p = tr[p][x], q = tr[q][x];
			num[p] = num[q] + 1;
		}
	}
	int query(int p, int q, int val) {
		int res = 0;
		for(int i = 19; ~i; i --) {
			int x = ((val >> i) & 1);
			if(num[tr[q][x ^ 1]] > num[tr[p][x ^ 1]]) res += (1 << i), x ^= 1;
			p = tr[p][x], q = tr[q][x];
		}
		return res;
	}
}T;

Envy

$\qquad$ 题面

$\qquad$ ~~奇怪的东西混入……~~

$\qquad$ 最小生成树性质题。

$\qquad$ 本题主要用到最小生成树的两个性质：1、所有最小生成树中，权值相同的边的条数一定是相同的。2、所有最小生成树中，小于等于某一权值的边加完后图的连通性一定是相同的。有了这两点，我们每次将不同权值的边分开考虑，判断是否成环即可。

$\qquad$ Code

Extending Set of Points

$\qquad$ 题面

$\qquad$ 我们若将整个网格的行看作二分图的左部点，列看作二分图的右部点，那么网格上的一个点就对应了二分图上的一条连接左右部点的边。一个显然的结论：二分图上的一个连通块给答案带来的贡献为 $sx\times sy$ ， $s x, sy$ 分别表示当前连通块中左右部点的数量。直接套线段树分治即可。

$\qquad$ Code

Forced Online Queries Problem

$\qquad$ 题面

$\qquad$ 最恶心的一道题……

$\qquad$ 虽然题目中给定了所谓的“强制在线”，但这是诈骗题！注意到，线段树分治就是对时间建立线段树，求解的时候也是按照时间的先后依次求解，所以我们带考虑到第 $i$ 个操作时，它的 $l a s t an s$ 一定已经求过了。而且注意到本题的 $l a s t an s$ 只有可能是 $0/1$ ，所以我们在插入线段树的时候把 $l a s t an s = 0/1$ 的情况全部插入，在往并查集中加入的时候判断一下该加哪条边即可。有点细节。

$\qquad$ Code

「雅礼集训 2018 Day10」贪玩蓝月

$\qquad$ 题面

$\qquad$ 线段树分治套背包水题。

$\qquad$ 核心 $C o d e :$

void calc(int p) {
	for(PII x : qs[p]) {
		cnt ++;
		for(int j = 0; j < mod; j ++) dp[cnt][j] = dp[cnt - 1][j];
		for(int j = 0; j < mod; j ++) dp[cnt][(x.first + j) % mod] = max(dp[cnt][(x.first + j) % mod], dp[cnt - 1][j] + x.second);
	}
}