分块维护不带修区间点对信息_杂项

分块维护不带修区间点对信息

通常求的是 $\sum_{i=l}^r\sum_{j=l}^r f(i,j)$。

由于贡献可差分，我们可以利用分块按照一定套路求。

维护如下信息：

• $p_{x}$ 表示 $[l(id(x)),x]$ 的点对贡献。
• $s_x$ 表示 $[x,r(id(x))]$ 的点对贡献。
• $f_{L,R}$ 表示 $[l(L),r(R)]$ 的点对贡献。
• $c_{i,j}$ 表示前 $i$ 块中对 $j$ 有贡献的元素个数（若求的不是点对个数那就是贡献和），如果贡献的两方不对等那么需要维护两个 $c$。

用 $b(a,b,c,d)$ 表示暴力求 $[a,b]$ 与 $[c,d]$ 之间的贡献。

求 $p_x,s_x$ 通常可以暴力，$f_{L,R}=f_{L+1,R}+f_{L,R-1}-f_{L+1,R-1}+b(l(L),l(R),r(L),r(R))$。

求 $c_{i,j}$ 也需要找到好的方法，常用方法（如果 $j$ 这一维具有某种单调性）是先对块间做 $i$ 这一维的前缀和，再每块对 $j$ 这一维做前缀和。

实际询问中若 $l,r$ 在同一块，那么可以使用 $p_r-p_l-b(l(id(l),l-1,l,r)$ 来求。

若 $l,r$ 在不同块，那么中间块内部的贡献用 $f$ 来求，散块内部的贡献用 $p,s$ 来求，散块与中间块的贡献用 $c$ 来求，两散块的贡献用 $b$ 来求。