题解 P5268 【[SNOI2017]一个简单的询问】

2019-03-29 15:29:51


先来推式子:

$\begin{aligned} \sum_{i=0}^{\infty} get(l_1, r_1, x) \times get(l_2, r_2, x) = &\sum_{i=0}^{\infty} get(0, r_1, x) \times get(0, r_2, x)\\ - &\sum_{i=0}^{\infty} get(0, l_1-1, x) \times get(0, r_2, x)\\ - &\sum_{i=0}^{\infty} get(0, r_1, x) \times get(0, l_2-1, x) \\ + &\sum_{i=0}^{\infty} get(0, l_1-1, x) \times get(0, l_2-1, x) \end{aligned}$

这样子就可以把每个询问拆成四个,然后莫队即可。

具体实现和细节见代码