二次离线莫队

更新答案不是 \(O(1)\)？答案可差分？

二离来啦。

P4887 【模板】莫队二次离线

先考虑贡献：\(f(x,[l,r])\) 表示 \(x\) 对区间 \([l,r]\)。

考虑莫队每次的移动：\(r\to r'\)。答案增加为：

发现前面那一坨可以直接预处理，莫队的时候 \(O(1)\) 更新即可。考虑后面。

设 \(g([r+1,r'],[1,l-1])\) 表示 \(\sum\limits_{i\in [r+1,r']} f(i,[1,l-1])=\sum\limits_{i<l} f(i,[r+1,r'])\)。

又，由莫队的复杂度证明知，所有 \([r+1,r']\) 的长度总和在线性根号级别。所以我们可以对 \(i\) 递增扫描线，每次更新前缀值，然后在 \([r+1,r']\) 暴力查询即可。

对于单点，查询怎么做？套路地开一个桶记录即可。单次复杂度为 \(O(\binom{14}{k})\)，最大为 3000 多一点。

注意上面只列举了 \(r\to r'\) 的情况，其它情况是平凡的。