题解 P3674 【小清新人渣的本愿】

noip

2017-03-19 22:06:39

Solution

![](https://cdn.luogu.com.cn/upload/pic/4666.png) 考虑对于减操作,用bitset来维护每个数是否出现过 这样就可以O( c / 64 )的查询区间是否有两个数差为x了,即得到区间的bitset a,( a & ( a << x ) ).count() 加操作同理,维护一个反的bitset即可 乘操作直接暴力枚举小的因数,是O( sqrt( n ) )的 用膜队维护区间的bitset,总复杂度为O( m( sqrt( n ) + c / 64 ) ) 其实除也可以做的。。。只是似乎有点麻烦