ShinriiTin/notes/8102OctSep
数据结构
cf1017G
\(n\le10^5\)个点的树，以\(1\)为根，一开始每个点都是白色，\(q\le10^5\)次操作，操作有3种：
- 从点\(v\)开始，如果\(v\)为白色，将\(v\)变为黑色，否则对于\(v\)的所有儿子递归地执行这一操作
- 将点\(v\)所在子树全部变为白色
- 询问点\(v\)当前的颜色
将询问分块，每块的关键点建出虚树，边上记录白点个数，则对于关键点暴力做操作即可。
维护\(lazy[u]\)为从\(u\)往下要染黑的距离，当一条边的白点都被染黑后递归到下面的关键点，清空操作清空\(lazy[u]\)并将白点个数改为原树中缩掉的节点个数。
每块询问做完后，再将非关键点的颜色修改正确，对于被清空过的点要先修改改为白色再判断是否可以被染黑。
复杂度\(O(n\sqrt{n})\).
gym100551A
发现自己15年交了一道gym没加文件输入输出tle的代码，加上就过了。
无向图，加边，删边，询问连通块数量。
按边的删除时间维护最大生成树，lct，复杂度\(O(n\log{n})\).
51nod 1981
\(n\le65536\)个set，\(q\le65536\)次操作，要么给区间\([L,R]\)的set都insert一个\(0\le c\le30000\)，要么询问区间[L,R]的set合并成一个set后第k小，非法输出-1.
用线段树套bitset，标记永久化一下，询问时二分一下，注意\(k=0\)也是非法。
时间复杂度\(O(n\log{n}\cdot \frac{q}{32})\)，空间复杂度\(O(n\cdot\frac{q}{32})\).
#include <bits/stdc++.h>
inline void read(int &x) {
char c;
while (!isdigit(c = getchar()));
x = c - '0';
while (isdigit(c = getchar())) {
(x *= 10) += c - '0';
}
}
#define ls(x) ((x) << 1)
#define rs(x) (ls(x) | 1)
#define mid ((l + r) >> 1)
#define lch ls(x), l, mid
#define rch rs(x), mid + 1, r
const int max_N = 65536 + 21;
const int max_M = 10001;
using data = std::bitset<max_M>;
int n, q, ql, qr, qt, opt;
data seg[max_N << 1], lazy[max_N << 1], qa;
void modify(int x, int l, int r) {
seg[x].set(qt);
if (ql <= l && r <= qr) {
lazy[x].set(qt);
} else {
if (ql <= mid) modify(lch);
if (qr > mid) modify(rch);
}
}
void query(int x, int l, int r) {
qa |= lazy[x];
if (ql <= l && r <= qr) {
qa |= seg[x];
} else {
if (ql <= mid) query(lch);
if (qr > mid) query(rch);
}
}
int main() {
read(n), read(q);
while (q--) {
read(opt), read(ql), read(qr), read(qt);
if (opt == 1) {
modify(1, 1, n);
} else {
qa.reset();
query(1, 1, n);
int sum = qa.count();
if (!qt || qt > sum) {
puts("-1");
} else {
int lo = 0, hi = 10000;
while (lo < hi) {
int mi = (lo + hi) >> 1;
int cur = sum - (qa >> (mi + 1)).count();
if (cur >= qt) {
hi = mi;
} else {
lo = mi + 1;
}
}
printf("%d\n", lo);
}
}
}
return 0;
}图论
cf1039C
给出一个\(n\le500000\)个点，\(m\le500000\)条边的无向图，每个点有个点权\(a_i\)，满足\(0\le a_i<2^k\)，其中\(0\le k\le60\)，并且有边相连的两个点的权值不同.
求二元组\((A,x)\)的数量，满足：
- \(A\)是图中的点集，\(x\)是\([0,2^k)\)的整数
- 将\(A\)中的所有点点权异或上\(x\)，依然满足有边相连的两个点的权值不同.
对于边\((u,v)\)，当\(x=a_u\oplus a_v\)时，\(u\)和\(v\)要么都属于\(A\)要么都不属于\(A\).
将边按\(w = a_u\oplus a_v\)排序，只考虑\(w\)相同的边，那么合法的方案数等于\(2^{cnt}\)，\(cnt\)为连通块数量。
用按秩合并的并查集实现，做完一组撤销即可，时间复杂度\(O(n\log{n})\).
cf1027F
有\(n\le10^6\)门课程，第\(i\)门课程可以在第\(a_i\)天完成或者第\(b_i\)天完成，\(1\le a_i<b_i\le10^9\)。
同一天最多只能完成一门课程，问最早能在第几天完成所有课程，或者压根无法完成。
将天数做为点，课程作为\(a_i\)到\(b_i\)的无向边建出一张图，则每条边需要消耗一个邻点，对于每个连通块，有解当且仅当点数不少于边数。
点数小于边数时显然无解，否则点数可能等于边数或者是边数加一，即是树或者基环套树，显然有解。
如果是树，则答案为树上次晚出现的点可以满足，如果是基环套树，则是树上最晚出现的点出现了才可以满足。
hash之后，用并查集维护最大次大即可。
unordered_map与pbds均无法通过，需要手写hash表。
时间复杂度\(O(n)\).
cf487E
给出一个\(n\le10^5\)个点，\(m\le10^5\)条边的简单无向连通图，每个点有个点权。
\(q\le10^5\)次操作，每次或者修改一个点的点权，或者询问从\(u\)到\(v\)的所有简单路径中最小的点权是多少。
将点双连通分量缩点，之后就是询问树上路径最小值。
关键在于割点可能在多个点双中，修改时不能简单地将所有相关的分量进行修改。
修改一下建图，对于一个点双，新建一个点，向除分量中深度最小的点之外的所有点连边，再从深度最小的点向这个新建点连一条边。
这样对于原图中的每个点，修改时修改自己与父亲节点，询问时若lca为新建点，则将lca的父亲的信息也用来更新即可。
时间复杂度\(O(n\log{n}+m+q\log^2{n})\).
cf962F
给出一个\(n\le10^5\)个点，\(m\le21\times10^5\)条边的简单无向图，求恰好出现在一个简单环中的边有哪些。
求出点双连通分量，然后判断其是否为简单环（点数等于边数），是则所有边都满足要求。
