深圳有哪些网站建设公司,电商运营团队,如何做链接淘宝客的网站,更改网站伪静态线段树分治总结 概念例题二分图 /【模板】线段树分治[HAOI2017] 八纵八横[FJOI2015] 火星商店问题EnvyExtending Set of PointsForced Online Queries Problem「雅礼集训 2018 Day10」贪玩蓝月BZOJ4184-shallot[bzoj4644]经典**题 概念 \qquad 线段树分治一般用来解决带有如下两… 线段树分治总结 概念例题二分图 /【模板】线段树分治[HAOI2017] 八纵八横[FJOI2015] 火星商店问题EnvyExtending Set of PointsForced Online Queries Problem「雅礼集训 2018 Day10」贪玩蓝月BZOJ4184-shallot[bzoj4644]经典**题 概念 \qquad 线段树分治一般用来解决带有如下两个特征的问题1、一些操作只在某一特定时间段生效2、查询某一时间点上所有操作的结果。我们可以对时间建立一棵线段树把操作挂在线段树对应节点上询问挂在叶子节点上然后从根节点开始从左到右遍历线段树。每次进入一个新节点就完成当前节点处挂的操作从某一结点回溯时把它上面挂的操作撤销到叶子节点查询即可。所以线段树合并总是与支持添加、撤销的数据结构结合。
例题
二分图 /【模板】线段树分治 \qquad 题面 \qquad 线段树分治模板题。 \qquad 判断一张图是否是二分图一般用的都是染色法看有没有相邻两个点颜色相同。但是在本题中图是动态的显然我们每次不能重新跑一遍图。此时我们就要用另一种方法拓展域并查集。因为要撤销所以我们不能写路径压缩而应该写按秩合并。 \qquad 核心 C o d e : Code: Code:
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 ⊕ x 0 x\oplus x0 x⊕x0。在本题中我们的任务实际上是找到几个环使得他们权值的异或和最大。因为最终的路径是以首都为开头、结尾的环环上的边是可以由其他环拼出来的选两次相当于没选。那么我们如何找到图上所有的环呢一个结论是我们在一开始任意找一个图的生成树那么我们仅需记录新加的边与生成树形成的环便可组成所有的环。根据这个结论套上一个线段树分治即可。 \qquad 核心 C o d e : Code: Code:
//并查集操作
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 01trie 01trie。 \qquad 其实主要就题面将恶心点写起来还是很顺的。 \qquad 核心 C o d e : Code: Code:
//可持久化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 我们若将整个网格的行看作二分图的左部点列看作二分图的右部点那么网格上的一个点就对应了二分图上的一条连接左右部点的边。一个显然的结论二分图上的一个连通块给答案带来的贡献为 s x × s y sx\times sy sx×sy s x , s y sx,sy sx,sy 分别表示当前连通块中左右部点的数量。直接套线段树分治即可。 \qquad Code
Forced Online Queries Problem \qquad 题面 \qquad 最恶心的一道题…… \qquad 虽然题目中给定了所谓的“强制在线”但这是诈骗题注意到线段树分治就是对时间建立线段树求解的时候也是按照时间的先后依次求解所以我们带考虑到第 i i i 个操作时它的 l a s t a n s lastans lastans 一定已经求过了。而且注意到本题的 l a s t a n s lastans lastans 只有可能是 0 / 1 0/1 0/1所以我们在插入线段树的时候把 l a s t a n s 0 / 1 lastans0/1 lastans0/1 的情况全部插入在往并查集中加入的时候判断一下该加哪条边即可。有点细节。 \qquad Code
「雅礼集训 2018 Day10」贪玩蓝月 \qquad 题面 \qquad 线段树分治套背包水题。 \qquad 核心 C o d e : Code: Code:
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);}
}BZOJ4184-shallot \qquad 八纵八横的简化版线段树分治套线性基。
[bzoj4644]经典**题 \qquad 我们把一个点的权值定义为与其相连的边的权值的异或和。可以发现如果一条边同时选两个端点相当于没选所以本题相当于选出若干点使得异或和最大。线段树分治时线段树节点处插入点在该时刻时的权值。
