That’s to say 没写代码。
DP 还是太消耗我本就不富裕的脑神经元了。还是 DS（此处特指线段树题）更友好 /tyt
题目来源：在洛谷文章广场里乱薅题解，看看是道 DS 就做。洛谷这招太狠了。
P12389 COmPoUNdS
https://www.luogu.com.cn/problem/P12389
给定常数模数，维护模意义下的区间加、区间哈希。\(n\le 10^6\)。
发现线段树哈希没办法维护取模操作，太难受了。
但把差分值也取模容易发现是对的。太好了。而且小性质：此处取模后的差分数组模意义下前缀和仍然是原数组。
bb：似乎也有把差分值取 abs 的做法，容易发现也是对的。
P12598 参数要吉祥
https://www.luogu.com.cn/problem/P12598
给定 \(\{a\}\) 和 \(q\) 个询问，每次问 \([l,r]\) 中 \(c(x)\times a_x\) 的最大值。其中 \(c(x)\) 为『出现次数为 \(x\) 的数』的种类。
太好了直接上莫队。每次更新一个数的 \(cnt\) 时，如果没出现过就加入队列。最后查询的时候把队列过一遍，丢掉非最新版本的数据。显然队列长度和移动次数是一样的。唉莫队结合队列感觉还是有点常用的。
最后需要过一遍整个队列。对于长度为 \(len\) 的区间，你会发现 \(\ge \sqrt{len}\) 的 \(cnt\) 出现次数不超过 \(\sqrt {len}\)；\(\le \sqrt{len}\) 的 \(cnt\) 出现次数更不超过 \(len\)。所以过一遍队列就是 \(O(\sqrt {len})\) 的。
P3793 由乃救爷爷
https://www.luogu.com.cn/problem/P3793
尽可能快地维护随机序列区间最值。
我们知道随机序列笛卡尔树期望深度是 \(\log\)。发现数据太过随机以至于可以过。
来自 UnyieldingTrilobite 的文章：同样可以用悬线！悬线 + 分块 就可以做了。
P4635 [SHOI2011] 改进代码
https://www.luogu.com.cn/problem/P4635
给定序列 \(a_{1\sim n}\) 和常数 \(p\)，维护:
- 修改：模 \(p\) 意义下区间加；
- 询问：区间中 \(\sum\limits_{i=l}^{r-1}[a_i>a_{i+1}]\)。
\(n\le 10^5,p\le 10^6\)。
怎么又是模意义区间加？
发现第二个也和差分有关系；需要注意到此时差分数组是非负的（有助于你想正解），假如 \(s\) 为当前差分数组前缀和模 \(p\) 的值（也就是原数），发现前一个数 \(>\) 后一个数当且仅当 \(s\) 加爆了。那么这就很简单了：顺便维护一下原数组；那么 \(p\) 的初值就可以确定。然后维护区间内差分数组之和（显然不用取模），在这个和里有多少个 \(p\) 就会爆多少次。
P12685 [国家集训队] 排队 加强版
https://www.luogu.com.cn/problem/P12685
给定 \(a_{1\sim n}\) 和 \(m\) 次交换操作，每次操作后输出逆序对数。
\(n,m\le 2\times 10^5\)。
哇是动态逆序对（？）。交换看成两次修改就可以无脑 CDQ 了。
薅的题解 里给了一个奇怪卡常小寄巧：发现 CDQ 是 \(O(len\log n)\) 的，暴力是 \(O(len^2)\) 的。所以等到 \(len<\log n\) 的时候就可以上暴力了。