In my life题解

简述:\(c_i\) 在初始时和重置时决定 \(b_i\),对 \(c\) 有区间乘操作,对 \(b\) 有区间加和乘操作,维护 \(b\) 区间和。
打表可证明初始和对应 \(c\) 重置时,\(b_i=\lfloor c_i*c_i/4 \rfloor\)
证明目前有3种,先咕一下。

对 \(b\) 的操作直接线段树2模板即可,但注意要维护一个没有 \(b\) 操作时的数据。

对 \(c\) 操作时,首先把线段树恢复到记录的 \(b\) 操作无效时的状态。之后将区间和 \(\times k^2\) ,这时我们注意到 \(c_i^2/4\) 的可能有余数(只可能为 \(1\))。

如果 \(k^2 \equiv 1 \mod 4\) ,那么将余数为 \(1\) 的数的个数乘 \(k^2/4\),得到的结果累计入区间和,并将余数为 \(1\) 的数的个数重置为 \(0\) 即可。
若不为 \(k^2 \equiv 0 \mod 4\),那么将余数为 \(1\) 的数的个数乘 \(k^2/4\),得到的结果累计入区间和即可。

以上操作都用高精度即可、

上一篇:Oracle提示错误消息ORA-28001: the password has expired


下一篇:题解 CF551C 【GukiZ hates Boxes】