牛客补题

练习赛 91

D 写了棵替罪羊树，E WA 了 \(4\) 次，导致没时间想 F、没时间写 G 了。。。

E. 游戏人生

比较基础的反悔贪心，考场上一直考虑不全，这种题还是要拍

F. 卡牌大师

记 \(len\) 为 \(m\) 的位数，把数分成两组：后 \(m\) 位加起来 \(=m\) 和后 \(m\) 位加起来 \(=10^{len}+m\)（进一位），不难发现两组内的数是独立的。

只考虑后 \(len\) 位。以第一组为例，如果 \(a+b=m\)，那么 \(a,b\) 一定一一对应且 \(a\in[1,\frac{m}{2}],b\in[\frac{m}{2},m]\)，算出这两块分别有多少数取 \(\max\) 即可，实现上细节比较多（比如特判 \(m\) 是偶数、\(0\) 不合法但 \(10^k\) 合法、需要 __int128）。

G. 区间加

如果只有加 \(lowbit\)，每个数被加 \(\log\) 次后会变成 \(2^{k}\) 的形式，之后每次加相当于是 \(\times2\)。
考虑 \(highbit\)，每次加会使二进制下最高的 \(1\) 左移一位，那么把每个数最高的 \(1\) 位和剩余位单独剥离，分别维护即可。

实现上可以用线段树维护最高位的值、其余位的值、最高位和最低位差了多少位，\(+highbit\) 时给最高位 \(\times2\)，差值 \(+1\)；\(+lowbit\) 时对其余位为 \(2^k\) 形式的区间 \(\times2\)，其他位置暴力修改，差值 \(-1\)。时间复杂度 \(O(n\log n\log a)\)

代码鸽了