BZOJ 5016 [Snoi2017] 一个简单的询问

发布于 2017-09-02  123 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=5016

https://loj.ac/problem/2254

题意:见原题面。


为了书写方便,get 内均省略 x 不写。

首先显然地,区间询问转换为前缀询问:\(get(l,r)=get(1,r)-get(1,l-1)\)

那么整理原式:\(get(l_1,r_1)\cdot get(l_2,r_2)=[(get(1,r_1)-get(1,l_1-1)]\cdot [(get(1,r_2)-get(1,l_2-1)]\)

进一步展开:(为了书写更方便,省略 get 不写)\(get(l_1,r_1)\cdot get(l_2,r_2)=(1,r_1)\cdot (1,r_2)-(1,r_1)\cdot(1,l_2-1)-(1,r_2)\cdot (1,l_1-1)+(1,l_1-1)\cdot (1,l_2-1)\)

记\([l,r]=(1,l)\cdot (1,r)\)

那么\(get(l_1,r_1)\cdot get(l_2,r_2)=[r_1,r_2]-[r_1,l_2-1]-[r_2,l_1-1]+[l_1-1,l_2-1]\)

直接上莫队就好了,分别记录 l,r 两个指针的答案,一个询问拆成四个询问。

详见代码:

 


一个非常弱的准退役OIER