题解 P7334 [JRKSJ R1] 吊打

Ryo_Yamada · 2021-06-05 15:51:51 · 题解

区间操作首先想到线段树。

• 区间开方下取整

和 GSS4 一样，可以用相同的方法，记录区间最大值，如果这个最大值 >1 才进入区间修改。10^9 做五次开方操作就会变成 1，所以复杂度是有保证的。

• 区间平方

显然，区间平方的和 与 区间和的平方不是一个东西，无法直接修改，要考虑别的做法。平方和开方是相反的操作，平方再开方后原数是不变的，考虑对每个点记录一个 \text{cnt}_i 表示当前这个数 \text{val}_i 被平方了多少次。对于每次开方操作，将 \text{cnt}_i 区间 +1。开方时，若 \text{cnt}_i 不为 0 则 \text{cnt}_i = \text{cnt}_i-1，否则将原数开方。因为 1 平方和开方后都是 1，所以这种做法区间最大值在 >1 上的正确性是有保证的。

但是这样还不足以通过。通过一次平方一次开方的操作可以将这种做法卡到 O(nm)。再维护区间 \text{cnt}_i 的最小值，修改时，若这个最小值 \geq 1，则直接区间将 \text{cnt}_i = \text{cnt}_i - 1。否则进入左右区间修改。