做题记录(2023-2-12 ~ 2023-2-25)

转化 $ a _ i ^ 2 + a _ j = k ^ 2 $ 这个条件，变为 $ (a _ i - k)(a _ i + k) = a _ j $ ，是两个数相乘的形式。将 $ a $ 放到值域上考虑，记 $ b _ i $ 表示是否有一个 $ a _ k = i $ 。 之后枚举 $ a _ i - k $ 和 $ a _ j $ ，是一个枚举因数与其倍数的过程，根据调和级数求和可知复杂度为 $ O(n \log n) $ 。

将最小值记作 $ m $ ，如果所有数在二进制中都包含 $ m $ ，那么可行，放一个原序列数再放一个 $ m $ 。
如果有的数不包含 $ m $ ，那么如果包含它，整个序列按位与之后一定小于 $ m $ ，此时无解。
我的思路是考虑到有 $ 0 $ 就有解，之后尝试推广。

$ k \ge 3 $ 时暴力枚举答案， $ k \le 2 $ 时可以拆贡献到每一位，暴力计算即可。

所求即乘积的欧拉函数。对每个质数的指数分别求和，树状数组维护。由于欧拉函数积性，容易计算答案，复杂度为 $ O(cn \log n) $ ，其中 $ c = 60 $ 。

很有趣的一个交互题。考虑先问出来总边数，之后每次随机一个点集，询问它内部边数和总点集除去它内部的边数，于是可以得到两端分别在它和外面的边数。如果这个数为奇数，那它一定不可能为欧拉图。测试 $ 29 $ 次即可保证正确性（我还不会证，可以参考官方题解证法）。
思路是先考虑一个可以一次测试范围比较广的问法，然后发现上述方式符合要求。我也不知道为啥写一发就过了（）

以下大部分运算在 $ \bmod \ p $ 意义下进行。发现和在操作中不变，因此若 $ (a, b) $ 与 $ (c, d) $ 之和不同一定无解。设 $ s = a + b $ 。由于 $ s $ 不变，可以只考虑 $ a $ 的变化，一次操作可以将 $ a $ 变化为 $ 2a $ 或 $ 2a - s $ ，操作 $ k $ 次后 $ a $ 的可能取值为 $ 2 ^ k a - xs $ （其中 $ 0 \le x < 2 ^ k $ 且为整数），所以就要让 $ c = 2 ^ k a - xs $ ，枚举 $ k $ ，转化一下就是 $ \dfrac{2 ^ k a - c}{s} \bmod \ p < 2 ^ k $ 。显然 $ k $ 最大为 $ O(\log p) $ 级别，暴力枚举即可。

个人解法：先判掉 $ k \le 2 $ 。考虑一个长度为 $ n $ 的环，满足条件的点对恰好有 $ n $ 组，但这样只能解决 $ k \le 20 $ 的问题。发现 $ k $ 的可能取值很少，可以打表，于是写一个算点对个数的 dp，之后随机一些图打表即可。我选取的随机图是一个长度为 $ 17 $ 的环上随机加 $ 1 \sim 7 $ 条边，几分钟就跑完了。
其它构造解法可以参照官方题解和其它人的代码。

先思考一个 $ n ^ 3 $ 的区间 dp： $ f _ {l, r} $ 表示删掉区间 $ [l, r] $ 后，最小可能的最大代价，转移可以枚举中间的分界，或是去掉两端。由于是取 $ \max $ ，可以考虑枚举答案，一个个加入，再判断是否能删光全部。加入的过程是一个搜索，将原本不可行的区间变为可行的。搜索过程中，从小到大更新左 / 右端点相同的区间时，需要用 bitset 优化找可更新的区间。由于区间总共有 $ O(n ^ 2) $ 个，所以复杂度为 $ O(\dfrac{n ^ 3}{w}) $ ，其中 $ w = 64 $ ，为 bitset 所优化的常数。
以为自己写的这个是暴力，结果一看题解就是这样的……感觉 IQ test 也许就是要出人意料一些。

将数字一个个贪心加进去，取最后面的。如果不可行，就尝试更改之前加入的一些数字的位置。（不太会描述这个贪心……但模拟一下这个过程就能感觉出来它的正确性。

插头 dp 板子题。考虑直接按行转移， $ m = 6 $ 时状态数只有 $ 51 $ 。预处理出从上到下和从下到上每一行的 dp 值，然后暴力合并即可。代码比较难写，我只写了 2h（）

这东西不像能直接算的，于是尝试计算其它的来加加减减出答案。（可能 IQ 比较高的人可以一下子找到用什么来加加减减（？））。我枚举了很多很多个式子，最后整理出 $ 4 $ 个有用的式子（和官方题解好像不太一样）。
定义 $ y(u, v) $ 表示边 $ (u, v) $ 为黄， $ b(u, v) $ 表示边 $ (u, v) $ 为蓝， $ y _ u $ 表示点 $ u $ 所连向的黄点的集合， $ b _ u $ 表示点 $ u $ 所连向的蓝点的集合， $ S \& T $ 表示集合 $ S $ 和集合 $ T $ 的交集的大小。
首先考虑将四个点的子图分成 $ 11 $ 类，在此只摘取有用的五类（以下公式中直接用大写字母表示该类子图个数）：

• A：三条蓝，三条黄，四个点无论是黄边还是蓝边均形成一条链。
• B：只有一条黄边。
• C：只有一条蓝边。
• G：只有两条黄边，且黄边端点均不同。
• I：只有两条蓝边，且蓝边端点均不同。

答案就是 $ A - B - C $ 。
之后，考虑令 $ s _ {11} = \sum \limits _ {y(u, v)} \binom{b _ u \& b _ v}{2} $ （即枚举每条黄边对其计数）、 $ s _ {12} = \sum \limits _ {b(u, v)} \binom{y _ u \& y _ v}{2} $ 、 $ s _ {22} = \sum \limits _ {y(u, v)} (y _ u \& b _ v)(y _ u \& b _ v) $ 、 $ s _ {23} = \sum \limits _ {b(u, v)} (y _ u \& b _ v)(y _ u \& b _ v) $ 。
通过组合意义可以得到 $ s _ {11} = B + 2G, s _ {12} = C + 2I, s _ {22} = A + 4I, s _ {23} = A + 4G $ 。
随后，容易想到 $ s _ {22} + s _ {23} - 2s _ {11} - 2s _ {12} = 2A - 2B - 2C $ 可以将 $ G $ 和 $ I $ 消去，引入 $ B $ 和 $ C $ 。答案就是 $ \dfrac{s _ {22} + s _ {23} - 2s _ {11} - 2s _ {12}}{2} $ 。
求 $ s $ 可以用 bitset 优化求集合交集大小，复杂度 $ O(\dfrac{n ^ 3}{w}) $ 。
其实也许比较无趣，就是暴力计算就行，画了两页草稿纸（
如果有快速找到如何计算的方法的话，那它似乎还不错，不过我并不会。

设 $f(j)$ 为 $j$ 对应的合法的 $i$ 的数量，容易得到

$$ f(j) = \begin{cases} n & j < k \\ k \left \lfloor \cfrac{n}{j} \right \rfloor + \min(n \bmod j, k - 1) & j \ge k \end{cases} $$

考虑整除分块，将 $n \bmod j$ 变化为 $n - j \left \lfloor \cfrac{n}{j} \right \rfloor$ ，在一个块内 $\left \lfloor \cfrac{n}{j} \right \rfloor$ 是相同的。因此，这个 $\min$ 是一个一次函数和一个常数的，容易 $O(1)$ 计算和。复杂度 $O(\sqrt n)$ 。

拆曼哈顿距离的绝对值，枚举在 $\binom{m}{2}$ 对曼哈顿距离的计算中，每个点在每对计算中，每个坐标的正负值。可以预处理出 $m - 1$ 对距离的计算中，若正负状态确定，坐标和的最大值，最后暴力枚举即可。
不过由于只最优化，所以有用的状态是较少的，能做到更优秀的复杂度。

对第二棵树后缀排序，对第一棵树每个点维护一个区间表示在第二棵树后缀排序后，和它前一些字符匹配的串的区间。之后模拟，树状数组维护，加第一棵树的点时，区间在其一级祖先的区间上二分出新的区间即可。

本来想试试直接暴力能不能跑过去……结果不行。
对 $a$ 的修改可以看作对 $b$ 的单点修改和区间平移一格，看起来就很平衡树。考虑如何快速维护 $\sum \limits _ {i = 1} ^ n \left \lfloor \cfrac{b _ i i ^ k}{w} \right \rfloor$ ：下取整不好做，又因为 $w \le 5$ ，于是考虑按 $i \bmod w$ 分别维护。为方便计算，以下都在 $b$ 的最开始加一个零。
有 $i = w \left \lfloor \frac{i }{w} \right \rfloor + i \bmod w$ ，根据二项式定理， $\sum \limits _ {i = 0} ^ n \left \lfloor \cfrac{b _ i i ^ k}{w} \right \rfloor = \sum \limits _ {i = 0} ^ n \left \lfloor \cfrac{b _ i \sum _ {j = 0} ^ k \binom{k}{j} \left \lfloor \frac{i }{w} \right \rfloor ^ j w ^ j (i \bmod w) ^ {k - j}}{w} \right \rfloor$ 。
分别维护 $j = 0$ 和 $j \ne 0$ 的答案。
对于 $j = 0$ ，答案为 $\sum \limits \left \lfloor \cfrac{b _ i (i \bmod w) ^ k}{w} \right \rfloor$ ，对每一种 $i \bmod w$ 都维护出来它即可。
对于 $j \ne 0$ ，答案为 $\sum b _ i \sum _ {j = 1} ^ k \binom{k}{j} \left \lfloor \frac{i }{w} \right \rfloor ^ j w ^ {j - 1} (i \bmod w) ^ {k - j}$ ，对每种 $i \bmod w$ 开一个平衡树，即可将 $\left \lfloor \frac{i }{w} \right \rfloor$ 变为 $i$ ，更容易处理了。记 $i \bmod w = L$ 。
记 $s _ j$ 表示一个节点上，若这个节点子树就是全部的话， $\sum b _ i i ^ j$ 是多少。那么这部分的答案可以表示为 $\sum _ {j = 1} ^ k s _ j w ^ {j - 1} L ^ {k - j} \binom{k}{j}$ 。
维护 $s _ j$ ，就是左侧的加上自己再加上右侧中所有 $i$ 都变为 $i + siz _ l + 1$ 的答案，其中 $siz _ l$ 表示左侧子树大小。将右侧所有 $i$ 变为 $i + c$ 应该是容易用二项式定理展开得到一个关于右侧一些 $s _ j$ 的多项式的，可以快速计算。
考虑区间平移：这会让 $w$ 棵树裂出来中间的一些区间互相交换。比如区间右移一位，就会使树 $p$ 中间的区间跑到 $(p + 1) \bmod w$ 这棵树上。
于是我们使用平衡树解决了这道题！代码也就 4.2k（
不过似乎别人写的都是线段树……？全比我强啊（）

首先转化题意：发现 $p$ 是骗人的，直接把 $q$ 按照 $p$ 映射过去即可。之后如果将 $(i, p _ i)$ 看作一个点并黑白染色，条件就变成了如果一个点是黑色的，那么它左上必须都是黑的；如果它是白的，那么它右下必须是白的（我就做到这里了）。
考虑黑白分界线必然是一个上升的折线，所以不可能经过重复的纵坐标。考虑对每条路径算贡献：直接设 $f _ {i, j, k}$ 表示走到了 $(i, j)$ ，经过了 $k$ 个未确定的点的方案数，最后对于每个状态直接乘上总不确定数减去 $k$ 的阶乘，求和即可。

这题之前模拟赛做过，看过题解，不过当时没补，就当补题了（）
模拟几个数据，感觉 LCS 长度至少为 $n$ ，也感觉必然有一些简单规律。打表发现的确如此，直接照着规律写就行。

是个人做法。
考虑建括号树：必然是一条向左的链再加上链上点的其它孩子。答案是每一层的答案之和。
考虑使用线段树维护之：每一层占一个位置，答案的合并就是直接加。当删掉 1 操作时，相当于单点减一；当删掉二操作时，相当于给一个点写一个标记，表示它将会和下一层合并。