诡异操作，诡异 trick 与诡异势能陷阱

· · 个人记录

题意：\log_2 V=w=128, \log_2 n=18 支持区间位 and，区间除，区间查和。

  1. 只有区间 and 或区间除

显然暴力操作次数都为 nw。

  1. 缝合

我会打标记！区间 and 可以变成标记，线段树多维护信息：区间内第 i 位为 1 的数的个数。区间除暴力找到 >1 的数进行修改。

复杂度炸了！暴力除的次数高达 nw，更不用说线段树的两个 \log。

  1. 优化

从暴力除下手，我们发现至少线段树叶子的信息需要完全修改，并且应当做到 O(1)。诡异 trick：把原本 w \times \log len 的 01 矩阵转置一下（len 表示线段树区间长度），并在合并时模拟加法进位，可以从 w 做到 \log len。也就是说底层变成 O(1) 了！

由于平常做题的思维套路，容易只分析叶子的势能（操作 w 次）。实际上线段树上每个点被区间除的次数都是最多 w 次。

对于区间除的操作，应当暴力 dfs 并上传标记，由于总操作复杂度为 \sum \log len \times w 在主定理下不带 \log，所以依托线段树节点的势能分析为线性的 O(nw)。

十分诡异的陷阱！如果一直想每个数的最多操作次数，容易忽略线段树本身的性质。