300iq contest 2 vp 记录
$A$
看完题目头皮发麻，这啥啊！
咕了。
$B$
结论：$c < b < a$, $a \otimes b \geq x$, $b \otimes c \geq x$，那么 $a \otimes c \geq x$。
设 $b$ 与 $c$ 不同在第 $i$ 位，$b_i = 1$, $c_i = 0$
- $a_i = 1$：$a \otimes c > a \otimes b$ 显然；
- $a_i = 0$：则前面位必有位置 $j$ 满足 $a_j > b_j = c_j$，而 $b \otimes c \geq x$ !!! $b$ 和 $c$ 从当前位异或为 $1$ 开始就 $\geq x$ 了你 $a$ 和 $c$ 在之前位异或为 $1$ 了当然 $\geq x$。
有传递性就好做了。trie 上卡位。
$C$
将一条边也看作环，仙人掌就是许多环拼在一起。
凭借 xza 模拟赛教育过你的 exp 知识，应该可以轻松 AC 此题（划掉）。
从小到大枚举每个点，把包含它的环拼起来
$D$
这个题目条件就告诉你，所有边双大小不超过 $k$。然后要求邻接矩阵行列式？
图的行列式 $= \sum\limits_{图的所有分解方式，分解为若干环} (-1)^{偶环个数}$
由于要考虑二元环，就比较恶心了……
在边双缩点得到的树上做 dp。
每个块有两种类型：$0$、$1$，表示该块的顶点 $top$ 是否和父亲块连。$dp[x, 0/1]$ 表示边双树上第 $x$ 个块及其子树的答案。
和父亲连的话只要在计算块行列式前把 $top$ 抠出来就可以了。
把儿子子树的系数和放到矩阵里做行列式，得到当前子树的系数和。
复杂度大概是 $O(\frac{n}{k} k^3) = O(nk^2)$
$E$
动态加边，每次寻找最大权的异或和为 $0$ 的非欧拉回路图，可以不连通
catalan 数 😂 这个 300iq 怎么造奇怪样例
首先把边看作向量，一条 $(x, y, a)$ 的边可以看作 $x$ 维和 $y$ 维都是 $1$，第 $n + 1$ ~ $n + 65$ 维为 $a$ 的二进制表示的向量
那么就是求最大权的线性无关向量组。
不用对每个前缀求的话怎么做：按 $w$ 降序排列后能加则加。正确性大概是因为它有拟阵结构！！！遗传性和交换性都满足。
对每个前缀求：当新加的向量异或成 $0$ 时，找到异或它的基内最小权向量并替换。。
$F$
粗略的想法：从前往后扫，非法的存起来，合法的合并并查询有无满足之前要求的，搞个并查集 + 线段树合并询问。丢进线段树的询问形如 $(need_val, qid)$。感觉这个细节有问题而且巨大难写。
——你需要一些奇怪的复杂度！
官方：
性质：$a + b \geq s$ 时必然满足 $a \geq s/2$ 或 $b \geq s/2$
设 $a$ 和 $b$ 所在连通块当前和分别为 $x$ 和 $y$，在两个连通块的 $(s - x - y)/2$ 处放上两个事件，标注一下是哪对 $a$ $b$
当一对连通块满足条件就合并，否则在新的 $(s - x - y)/2$ 处放上事件
每个 $s$ 会被分 $log$ 次，对连通块及其事件采取启发式合并，复杂度 $O(nlog(nlogC)logC)$
注意答案可能不为 $n - 1$ 因为最后可能并不成一棵树。
$G$
SAM？不用。
如果每个字符都不同，方案数为 $2^n - 1$
否则对于每个极长连续段减去重复计算的方案，就，枚举一下左边刚取到 $l$ 时右边到 $[l, r]$ 中哪个位置了，以及右边刚取到 $r$ 时左边到 $[l, r]$ 中哪个位置了，减去多算的操作序列数即可。
$H$
差点读错题。是要求选 $k$ 个不相交子区间价值和的最大值。
模拟费用流似乎没法搞。但是费用流告诉我们这是凸的。wqs 二分，单次 $O((r - l + 1) * log)$，线段树预处理每个区间凸包，就三只 log 了。
注意到总区间长（重复算一次）不过 $nlogn$，整体二分，将询问排序，有单调性了，指针就够了，$nlognlogV$。
——第三个点大概 $10000$ 到 $30000$ 之间吧，为什么疯狂 TLE 啊？
——find 那里传了一整个 vector 进去……
传指针形式的 vector，和传编号，都可以 AC。
$I$
用不超过 $4 log_2 n$ 次操作找出关键点 $A$，每次询问 $?$ $k$ $x$ $y_1 \cdots y_k$，返回 $dis(A, x) \geq \min( dis(A, y_i) )$
$log^2$ 就是重链上二分。
wssb！$log$ 就是每次割一半，那么每次找重心即可。
数据好像比较水？/yiw
$J$
设 $f(k)$ 表示 $k$ 个匹配的最大价值和。
费用流模型容易建出。
费用流增广路径的价值递减，那么 f 就是上凸的了！
有凸性的考虑 dp，$dp[i, j, 0/1]$ 表示 $i$ 子树内匹配了 $j$ 对，$i$ 有无选。
dp 数组的合并其实就是凸包合并，闵可夫斯基和。
合并 $u$、$v$ 的复杂度是 $O(sz[u] + sz[v])$，那么启发式合并即可。
具体来说是类似链分治的玩意。重链要分治卷！！！跟花朵一样的方式，$[0/1][0/1]$ 表示该重链片段左右是否已匹配。鲨了我吧。
大概是一只 $log$？
$K$
1 | 不可做题。 |
官解真是有够暴力 /px
预处理可能存在非法串的位置和可能成为非法串的长度
由于不能控制所有位置的字符，考虑容斥，钦定一些位置是这些非法串，剩下位置随便摆。方案数可以通过并查集把应当相同的位置并起来得到。
先搜长串再搜短串。