随记 – 一月十三日

看来还是每天写些随记才好。做题时发现、学会的一些令人啧啧称奇的绝妙性质，以后可能有用。

关于异或

异或和具有区间可减性。可以通过前缀异或和快速求出某个区间所有元素的异或。

区间内，多种元素数量奇偶性的统计问题，可以转化为状压后的异或和。

性质一是由于$a \oplus b = c \Rightarrow a\oplus c = b$。由于异或可以理解为不进位二进制加法，所以若知道结果$c$和运算数$b$，运算数$a$的每一位是唯一确定的，$(0, 0)  \Rightarrow 0, (0, 1) \Rightarrow 1, (1, 1) \Rightarrow 0, (1, 0) \Rightarrow 1$。

由性质一的证明，性质二的运用参见洛谷题库 P3604 美好的每一天。将询问离线后莫队，瓶颈在于如何快速统计符合要求的后缀区间数量。对于每一个包含字符$c$的位置，我们把它记作$2^{c – \textrm{‘a’}}$。用一个$26$位二进制数来保存前缀异或和。一个区间能够在重排之后变成回文串，当且仅当它长度为偶，且区间中出现的各个元素计数均为偶；或者长度为奇，区间中有且仅有一个元素计数为奇。这也就等价于异或和是$0$（长度$2 \mid l$）或$2^k$（长度$l \equiv 1 (\mod 2)$）。指针移动过程中记录前缀异或和的出现次数（unsigned short险过），这样我们可以枚举新增加/减少位置的前缀异或的每一位，找到满足要求的前缀异或和的数量即可。

关于区间开平方根、置换为因数个数等

暴力去做这种数据结构题目是$\mathrm{O}(nm)$的。但数论知识告诉我们，一个$10^9$范围的数，至多在经过$5$次开平方后向下取整操作之后就会变成$1$，所以我们考虑跳过那些里面全部是$1$的区间。可以用线段树或者块状数组（分块）实现。总体来看的时间复杂度应当是$\mathrm{O}(n \log n + m \log n)$。参见CF920F REPLACE and SUM。

• 以后打乒乓要控制时长，不能上瘾。
• 诸如“函数无返回值导致CE”之类的语法错误应尽量避免。