[洛谷P3674]小清新人渣的本愿

题目链接

题解

其实这题要不是当时在学莫队,真的没想过会用莫队解决(粗略估计一下复杂度会炸)

用bitset维护的这个想法很赞,不看题解想不出来

大概就是下面这样的一个思路

首先对于操作1,第一个bitset维护的是当前位出现与否,比如$bitset[3]==1$说明当前区间内,3出现过

如果说让bitset里面所有的数-x或者+x后,还有和原bitset有相同的元素的话,那么就说明有这样的数

然后对于操作2,有一个前提就是这里询问的x也是在维护的bitset的范围内

于是呢我们可以维护另一个bitset,这个bitset存的反的bitset,什么意思呢,就是如果$bitset[x]==1$那么说明区间内存在$N-x$这个数,N就是bitset维护的最大的数。

如果说让第二个bitset里的数全部+x-N后,还有和第一个bitset有相同的元素的话,那么就说明有这样的数

其实第二个bitset很巧妙,它真正要存的东西其实是相反数(请仔细理解下这是为什么),$a+b=x$那么$a=x-b$其中a由第一个bitset维护,x-b由第二个bitset维护(请仔细理解这里,这是这道题的难点

至于操作3,枚举x的约数,$O(\sqrt{N})$

代码

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注