2025
Jul.
3
蛇给的题
给定序列 \(a_{1\cdots n}\in\N\)，求所有子段和的异或和。
\(n\le10^5,S=\sum a_i\le 10^6\)
套路性考虑，求一堆 \(S=\sum a_i\le 10^6\) 的异或和，按位考虑。对于第 \(b\) 位，要求所有区间的异或和，考虑扫右端点，记录每个左端点的信息。子段和中有效信息只有 \(2^b\)，是一个较小的值域且位置无关乎答案，所以套路性对值域建立数据结构。发现 fhq_treap 秒了。即：两棵树，分别代表第 \(b\) 位为 \(1\) 的和为 \(0\) 的，右端点每次往右扫，加入一个权值为 \(0\) 的节点进去，然后全局加上当前 \(a_i\)，并且把每棵树中进位到第 \(b\) 位的节点拆出来拼进另一个棵树，这显然是连续区间，只要把两棵树裂成四棵树然后再拼成两棵树。复杂度 \(O(n\log s\log n)\)。另一种做法先扫右端点，然后考虑直接维护所有左端点对应区间。\(O(n)\) 次全局加 \(x\) 操作可以改为 \(O(S)\) 次全局加 \(1\)，这用 01trie 是很好维护的（经典 trick：从低位到高位插入 trie）。复杂度 \(O(S\log S)\)。
AGC066A Adjacent Difference
一个 \(n\times n\) 的方阵 \(A_{1\cdots n,1\cdots n}\)，每次操作为给 \(a_{i,j}\) 加上 \(x\)，代价是 \(|x|\)。要求控制代价在 \(\frac 12dn^2\) 以内达到：任意两个相邻（共边）的元素差不小于 \(d\)。
\(n\le500,d\le1000,|A_{i,j}|\le1000\)
猜呗。一个显然的想法是国际象棋棋盘黑格为 \(k\)，白格为 \(k+d\)。容易发现对于极端大或小的情况不方便。容易想到 \(\pmod{2d}\)。
AGC066B Decreasing Digit Sums
考虑 \(f(x)\) 表示 \(x\) 十进制下各位之和。求一个 \(x\le10^{10000}\) 满足 \(\forall i\le50,f(2^ix)<f(2^{i-1}x)\)。
考虑一个比较优的构造 \(5^{50}\)，但是他在一定位置上会有个别递减。那么考虑用多个 \(5^{50}x\) 累加即可。实际构造时每次随机 \(2\not\mid x\) 添加到答案前面，然后加 \(50\) 个 0 来避免互相影响，检测是否满足要求，不满足则继续随机。