杂题集一
通过与或生成的集合的必要依赖位¶
对象化地思考一个 and or 表达式：最开始随便取一个初始对象。
想象一下用其它元素让它产生变化。
怎么变大？用一个含有（它没含有 1 位）的元素 or 一下。
怎么变小？用一个含有（它没含有 0 位）的元素 and 一下。
现在要 keep 某一个指定位置 \(p\) 的 \(1\)，同时希望其它位能 \(0\) 的就 \(0\)。如果其它元素中如果有能让它某位变 \(0\)，直接让它 and 上来就好，其它位置我不 care，该是 \(1\) 的把我弄 \(0\) 了更好，该是 \(0\) 的 and 后还是 \(0\)。最后会有一些其它位没法从 \(1\) 变成 \(0\)。
到这里我们得到了，如果想让 \(p\) 位是 \(1\)，有若干位因为没法有中生无，必然是 \(1\)，而除了这些必然，我们可以找到一个非必然位都是 \(0\) 的构造。（可以再抽象一步，\(p\) 生成一个串集，如果这个串集是 \(q\) 生成串集的子集，那么 \(p\) 为 \(1\) 时，\(q\) 必然为 \(1\)。所以，如果把完全相等的串集缩成一个点，然后根据真包含关系连接这些点，由于集合真包含的单调性，会得到一个 DAG。可以想象，把一个点设置成必要后，所有从它开始能到达的点都会被染成必要）
接着仿照经典数位不等式套路，从高位往低位考虑。会有两个分支，但是其中一个分支要么完全禁止，要么后面操作获得完全自由，会立马结束。所以每次都只有一个分支是一直继承下来的，并且信息是贴着已知串走的。
假设前面全贴着已知串
-
目前 \(p\) 位上已知串是 \(1\)，那么这位如果为 \(0\) 的话就被完全禁止了。所以继承下来的情况是这位选 \(1\)。你可能会说，我先前操作时可能这位作为必要位，已经是 \(1\) 了。(CRITICAL POINT) 这个时候我们想象一下那个 DAG，某个地方往后面走，走到了 \(p\)，\(p\) 会接着往后走完自己开始能到达的点。现在重复走一下 \(p\) 开始能到达的点，并不会有 side effects。
-
目前 \(p\) 位上已知串是 \(0\)，那么这位如果为 \(1\) 的话就被完全自由了。所以继承下来的情况是这位选 \(0\)。你可能会说，如果这里是前面某位的必要后继，这里也可以直接结束。好吧，确实是可以的。
Bertrand's postulate¶
Bertrand's postulate（实际上被证明为真）：\(n\) 与 \(2n\) 之间必有素数。证明方法是考虑 \(\binom{2n}{n}\)，如果 \(n,2n\) 之间没有素数，我们用素数分解来估计这个东西的大小就会失去很大一部分贡献，从而导出矛盾。细节可参考 Bertrand假设 - 知乎。
反悔自动机¶
M-低谷(hard)中国地质大学（武汉）2024年新生赛（同步赛） P1484 种树 - 洛谷 | 计算机科学教育新生态 P1792 [国家集训队] 种树 - 洛谷 | 计算机科学教育新生态
比较难构造。
模拟费用流
Naive inequality of XOR¶
This making the rest cases to be \(O(1)\).
扩展汉诺塔¶
对图的 度数和 根号分治¶
问题的转换容易想到。大概就是每次指定一个点，吸取其相邻的点的点权。然而问题是有些点可能有很多相邻点，比如说一个点联想其余所有点的图。然而这题的图保证了边数和点数同阶，一条边产生的度数是 \(2\)，总的可以给每个点消耗的度数很有限。也就是说度数 \(>\sqrt{n}\) 的点也就 \(O(\sqrt{n})\) 个。
对于大度数的点来说，如果我们多次让他吸取邻居点，希望卡时间，但要注意到重复的事情做了很多，因为每次吸过来的东西要是不变的话，结果也没啥变化。还要注意，每一步吸取实质上只是一个单点修改，只是修改成什么值需要计算。吸取可以转换一下思维：推出。对于不多的大度数点，当邻居点变化的时候给它更新就好了，并且只需要推出自身变化的一个差量给它就够了。
每次操作至少减一¶
如果有一个变量它每次操作都至少 -1，又构造出了一个恰好每次都 -1 的方案，那这个变量的初值就是最多的操作数。
B - Improve Inversions (atcoder.jp)
题意中给的是 pos 上的 val。technically 转向考虑 val 的 pos。 pos 上的 val 交换，等价于 val 的 pos 交换。 一组 pos 只能交换一次。
这个递至少减一数 count，定义为 val1 > val2 且 pos1 \(\stackrel{k}{\le}\) pos2 的数目。
证明
... > val1 > ... >val2 > ... pos1 \(\stackrel{k}{\le}\) pos2
原先满足这个关系的 pos1,pos2 交换掉，count 减一。 会更改的关系只会和变化了的元素相关。technically 以 pos1 为例子。
最开始：
valL > ... val1 ... > valR posL \(\stackrel{k}{\le}\) pos1 \(\stackrel{k}{\le}\) posR。
pos1 和 pos2 换掉后：
从 posL 的视角看，可以认为是 pos1 后移了，原本的关系不会有任何改变。 从 posR 的视角看 - 如果 posR 的 val 在 val2 后面，和 pos1 的关系自然就保持住了。 - 如果 posR 的 val 在 val1,val2 之间，和 pos1 的关系就寄了，因为 val 的关系不对了。（*）
val 就近原则
（*）处是唯一造成 count 多 -1 的位置。所以我们希望不产生这种情况。另外希望碰上好运，一组 pos 只交换一次。
重申一遍（*）处的判定条件：
val1 > val\' > val2 pos1 \(\stackrel{k}{\le}\) pos',pos2
上面只是 technically 的结果，另一个方向同理，
val1 > val\' > val2 pos1,pos' \(\stackrel{k}{\le}\) pos2
总的来说最佳操作就是 val 距离最近的先换，否则 count 会多减。
一组 pos 最多只交换一次
假设会重复选中相同的 (pos1,pos2)，实际上就是找到了一个 pos0 作跳板，
(1) pos0 pos1 pos2 (2) pos0 pos2 pos1 (3) pos1 pos2 pos0 (4) pos2 pos1 pos0
假如这样的话，则意味着这样的类序（我没找到这种二元关系的名称，所以自己临时造了这个词）关系 pos1 \(\stackrel{k}{\le}\) pos2 （由 (1) 到 (2) 可得） pos0 \(\stackrel{k}{\le}\) pos1 （由 (2) 到 (3) 可得）
这个符号显然可以传递，从而 pos0 \(\stackrel{k}{\le}\) pos2
也就是说 (2) 到 (3) 中，pos0 和 pos2 本来是可以换的，却 违背 了 val 就近原则，跨越了 pos2 进行了交换。矛盾！
然而在实现上也得仔细考虑。比如说从小到大枚举长度是有问题的，因为交换有可能会生成新的长度。 比较好的实现是从 \([n,n]\) 内一格一格扩展到 \([n,1]\)，其中区间内任意一组 pos 都不能有 \(\stackrel{k}{\le}\)。新加进来的一格，只需从近到远冒泡即可。 交换不会在内部产生新关系的证明与上面同理。
辗转相减缩小问题规模¶
B - Annoying String Problem (atcoder.jp)
目前的想法：
（0）yes or no 的问题一般可以先假设 yes，后面出问题了直接驳倒这个假设。
（1）若 \(X,Y\) 首尾有相同的 \(0,1\)，则可去掉后继续考虑。
（2）若 \(cnt_{1}(X)-cnt_{1}(Y)\not =0\)，则可根据
计算出 \(\text{len}(T)\)，那直接匹配就好了。 补：好像还是不行，因为如果 \(\text{len}(T)>\text{len}(S)\) 那多出来的几位就没法确定了。 结论：当且仅当 \(S,T\) 均为长度为 \(\gcd(|S|,|T|)\) 的某串的重复。 证明：如（1）操作后，取首一段进行初步比较（这里要求 \(|S|\not=|T|\)，当然，\(|S|=|T|\) 的情况是平凡的），将较长者全部替换成较短者加上一个余项，转换成一个同模型问题。如此迭代处理，能保证问题规模单调减小。
（3）现在凹出来一个新条件：\(cnt_{1}(X)=cnt_{1}(Y)\)，对应地必有 \(cnt_{0}(X)=cnt_{0}(Y)\)。（仔细一想，如果后者成立同样则必有前者，两者其实是等价的。）这时没有长度的限制，可以直接令 \(T=S\) 就能构造出一个解。
奇偶位翻转¶
逆天脑洞，彰显人类智慧的一集。
A - ABA and BAB (atcoder.jp) Editorial
树的某条路径是否被覆盖¶
标号为 dfs 序
转化为 01 序列处理逆序对¶
枚举 \(\min_{i=1}^{m}b_{i}>M\ge\max_{i=1}^{m}a_i\) 的值（这么说可能会有点奇怪，主要是考虑到全局 \(0\) 数量决定了这些 \(0\) 当中最大的元素是多少），将 \(\le M\) 的元素染色成 \(0\)，将 \(\ge M+1\) 的元素染色成 \(1\)。原约束“等价于” \(a\) 确定的集合里均为 \(0\)，\(b\) 确定的集合均为 \(1\)。
更准确地说，应该是所有原约束筛出的 permutation 与在这种新约束下也会被筛出，反过来也是。这么做的好处在于，将逆序对拆成了三份。0 内部的逆序对是相对自由的，1 内部也是，但是 01 之间的逆序对是定死的。新约束针对的是 01 的关系，0 内部和 1 内部分别自由，这就简化了问题。
而单独去考虑一个区间，就等价于左边是连续的 0，右边是连续的 1。分界线也是唯一的。另外要注意划分区间时要给个保底，不能是空的。 对于 Hard version 来说，会遇到一些相交的区间。其实就是考虑到保底机制，（只看一边），较短的一段有保底机制，导致较长的一段多出来的那段是被确定好了的。输出 -1 的情况无非就是这些确定产生了矛盾。
我选择了比较容易的实现，大概是平方级别的算法。 Submission #278518788 - Codeforces 预处理相当难写。 题解说存在线性级别的算法。
最小化各段最大值之和¶
D - Division into 3 (atcoder.jp)
首先能对整体考虑一个最大值。它落在 X 段，则 X 段的最大值就是 X。 其次，对于边界，它所在段的最大值不会小于它。
设分成 X,Y,Z 三段。
若整体最大值落在 Y：\(a_{l}+a_{m}+a_{r}\)，唯一的条件就是 m 和 l,r 不同。
若整体最大值不落在 Y，technically，落在 Z。 那么 Z 是灵活的，看 X,Y 的需求任意调整长度。 这样就能控制 Y 只有一个元素，因为多了没用，给 Z 吸收掉又不会影响 Z 的取值。所以我们可以枚举 Y 这个元素的位置，把左侧最大值加给它。
考虑离线做法就是一个套路 DS 题了。把询问按照 \(l\) 从大到小排序，从空开始往 DS 里塞元素更新。 需要实现的是： 塞进来的这个元素 \(a_{l}\) 在哪段极大区间 \([l,j]\) 担任最大值（导致这段区间产生了更新）； 将 \([l+1,j+1]\) 的点的 \(mxl\) 属性全部覆盖更新成 \(a_{l}\)； 查询区间中 \(mxl_{t}+a_{t}\) 的最大值。
基本敲定用线段树实现。如此为了考虑到 lazytag 是覆盖的，实际得维护的量还更复杂一点。算个大 DS 题了。
mex 相关¶
每组操作其实就是如下两种情况
- 如果 \(x=\text{mex}(a)\)，则 \(x\) 变为 \(\text{mex}(a\bigcup \{x\})\)。（称为第一类操作）
- 反之，\(x\) 变为 \(\text{mex}(a)\)。（称为第二类操作）
可以看出，第二类操作是一种相当宽松的操作。并且，这种操作没有必要在第一类操作后进行，同时没有必要进行超过一次。所以可以去枚举进行第二类操作的那个操作，让它第一个进行，继而进行决策。（当然，还有一种情况是根本不去进行第二类操作，只不过处理起来比较平凡罢了。）
此后，我们将剩下的 \(n-1\) 项操作各自想象成一条边。这里不要想复杂去套高级数据结构，有非常简单的实现方法。
可以复习一下 C++ 的引用传递语法。Submission #278279563 - Codeforces
这题虽说思路显然，但是如果细节没处理到位或者码力不足还是很难在短时赛中写对的。