[洛谷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})

代码

发表评论

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