线段树均摊复杂度

GSS4 - Can you answer these queries IV

• 操作 \(1\)：\(a_i=\sqrt{a_i},i\in[l,r]\)
• 操作 \(2\)：询问 \(\sum_{i=l}^ra_i\)

开根号无法使用 tag 的方式维护，因为开根号后不确定减去多少，无法维护 \(\sum a_i\)。
\(a_i=2^{\log a_i}\)，每次开根号后 \(\log a_i\) 会减半，操作 \(\log\log a_i\) 后 \(\log a_i=1\)，也就是说 \(a_i\) 不会再发生变化了。
\(\Phi=\sum_{i=1}^n\log\log a_i\)，每次区间开根都让 \(\Phi\) 减少 \(r-l+1\)，所以开根操作的总复杂度为 \(\mathcal O(n\log^2w)\)。
复杂度是 \(\mathcal O(n\log^2w+q\log n)\)。

基础数据结构练习题

• 操作 \(1\)：\(a_i=a_i+x,i\in[l,r]\)
• 操作 \(2\)：\(a_i=\sqrt{a_i},i\in[l,r]\)
• 操作 \(3\)：询问 \(\sum_{i=l}^ra_i\)

对于开方操作于上一题的操作不一样，修改会加上值。
把 \(a_i=\sqrt{a_i}\) 的操作变成 \(a_i=a_i-(a_i-\sqrt{a_i})\)，对于所有相同的值就可以一起操作了。
而且，不仅仅是 \(\min_{i=l}^r=\max_{i=l}^r\) 可以进行操作，只要满足 \(\min-\sqrt{\min}=\max-\sqrt{\max}\) 就可以把开根号变成减法。那么把线段 \(s\) 变为完全相同的次数就是 \(\mathcal O(\log\log(\max-\min))\)。
\(\Phi=\sum_s\log\log(\max-\min)\)，每次区间加只会让 \(\log n\) 块势能增加 \(\log\log w\)。
复杂度是 \(\mathcal O(q\log n\log\log w)\)。

I like Query Problem

• 操作 \(1\)：\(a_i=\lfloor\frac{a_i}x\rfloor,i\in[l,r]\)
• 操作 \(2\)：\(a_i=x,i\in[l,r]\)
• 操作 \(3\)：询问 \(\sum_{i=l}^ra_i\)

同理，对每个线段 \(s\) 维护 \(\min,\max\)。如果区间内 \(\min=\max\) 就直接整除，否则就暴力除最多 \(\log w\) 次。推平就打标记。
\(\Phi=\sum_s\log(\max-\min)\)，每次区间推平只会让 \(\log n\) 块势能增加 \(\log w\)。
复杂度是 \(\mathcal O(q\log n\log w)\)。

And RMQ

• 操作 \(1\)：\(a_i=a_i\space\&\space x\)
• 操作 \(2\)：\(a_i=x\)
• 操作 \(3\)：询问 \(\max_{i=l}^r\)

对于操作 \(1\) 暴力操作。记录每个线段的 \(\operatorname{or}_s\)，若 \(\operatorname{or}_s\&\space x=0\) 就直接不对这条线段进行操作。
\(\Phi=\sum_s\operatorname{popcnt}(\operatorname{or}_s)\)。初始时 \(\Phi=n\log w\)。操作 \(1\) 遍历过得每个节点都至少让 \(\Phi\) 减少 \(1\)。操作 \(2\) 会让 \(\Phi\) 增加 \(\log n\log w\)。所以总势能最多为 \(n\log w+q\log w\)。
复杂度是 \(\mathcal O(n\log w+q\log n \log w+n\log n)\)。

Counting Stars

• 操作 \(1\)：\(a_i=a_i+\operatorname{highbit}(a_i),i\in[l,r]\)
• 操作 \(2\)：\(a_i=a_i-\operatorname{lowbit}(a_i),i\in[l,r]\)
• 操作 \(3\)：询问 \(\sum_{i=l}^ra_i\)，对 \(998244353\) 取模

发现无论怎么操作，\(\operatorname{popcnt}(a_i)\) 总是不升的。记录最高位，如果是操作 \(1\) 就相当于 \(a_i=a_i+2^{\operatorname{highbit}(a_i)}\)，只储存 \(2^{\operatorname{highbit}}\) 的话就是区间乘 \(2\)。如果是操作 \(2\) 就可以暴力修改，修改完顺便维护一下最高位有没有被减掉，区间是否全 \(0\)。
\(\Phi=\sum_{i=1}^n\operatorname{popcnt}(a_i)\)。
复杂度是 \(\mathcal O(n\log w+n\log n)\)。

Lowbit

• 操作 \(1\)：\(a_i=a_i+\operatorname{lowbit}(a_i),i\in[l,r]\)
• 操作 \(2\)：询问 \(\sum_{i=l}^ra_i\)，对 \(998244353\) 取模

做法几乎差不多。一个数在执行 \(\log w\) 次后必然仅有最高位为 \(1\)。这个时候操作 \(1\) 就为区间乘 \(2\) 了。
\(\Phi=\sum_{i=1}^n\log(a_i)\)（这里的 \(a_i\) 是原始序列）。
复杂度是 \(\mathcal O(n\log w+n\log n)\)。

Gorgeous Sequence

• 操作 \(1\)：\(a_i=\max(a_i,x),i\in[l,r]\)
• 操作 \(2\)：询问 \(\max_{i=l}^r\)
• 操作 \(3\)：询问 \(\sum_{i=l}^ra_i\)

维护区间最小值 \(mn_1\)，最小值出现次数 \(cnt\)，严格次小值 \(mn_2\)。如果 \(x\le mn_1\) 直接退出。如果 \(mn_2<x\le mn_1\) 就用 \(x\) 更新 \(mn_1\) 和 \(cnt\) 等。否则递归儿子。
由于我太菜了，所以证明在这里。
复杂度是 \(\mathcal O(n\log^2n)\)。

关于 Beats，等我彻底理解了再继续写。