洛谷P3674 小清新人渣的本愿

题意：多次询问，区间内是否存在两个数，使得它们的和为x，差为x，积为x。

n，m，V <= 100000

解：

毒瘤bitset……

假如我们有询问区间的一个桶，那么我们就可以做到O(n)枚举查找了。

然后我们用bitset优化一下……外面套上莫队来维护桶。

具体来说，差为x可以写成 a – b = x

然后我们把bitset左移/右移x位，与原来的and一下，看是否有元素为1即可。

和为x可以写成 a + b = x   N – a – b = N – x   (N – a) – b = N – x

这启示我们维护一个N – x的反桶，然后把反桶右移N – x位与原桶and。

关于积，直接n^0.5暴力即可。

 #include <cstdio>
 #include <bitset>
 #include <cmath>
 #include <algorithm> const int N = ; int fr[N], a[N], bin[N];
 std::bitset<N> bs, bs2, tp; struct ASK {
     int f, l, r, x, t, ans;
     inline bool operator <(const ASK &w) const {
         if(fr[l] != fr[w.l]) {
             return l < w.l;
         }
         return r < w.r;
     }
 }ask[N]; inline bool cmp(const ASK &A, const ASK &B) {
     return A.t < B.t;
 } inline void add(int x) {
     if(!bin[a[x]]) {
         bs.set(a[x]);
         bs2.set(N - a[x]);
     }
     bin[a[x]]++;
     return;
 } inline void del(int x) {
     bin[a[x]]--;
     if(!bin[a[x]]) {
         bs.reset(a[x]);
         bs2.reset(N - a[x]);
     }
     return;
 } int main() {
     int n, m;
     scanf("%d%d", &n, &m);
     int T = sqrt(n);
     for(int i = ; i <= n; i++) {
         scanf("%d", &a[i]);
         fr[i] = (i - ) / T + ;
     }
     for(int i = ; i <= m; i++) {
         scanf("%d%d%d%d", &ask[i].f, &ask[i].l, &ask[i].r, &ask[i].x);
         ask[i].t = i;
     }
     std::sort(ask + , ask + m + );     int l = , r = ;
     bin[a[]]++;
     bs.set(a[]);
     bs2.set(N - a[]);
     for(int i = ; i <= m; i++) {
         while(l > ask[i].l) {
             add(--l);
         }
         while(r < ask[i].r) {
             add(++r);
         }
         while(l < ask[i].l) {
             del(l++);
         }
         while(r > ask[i].r) {
             del(r--);
         }
         // ------------
         if(ask[i].f == ) {
             tp = bs & (bs >> ask[i].x);
             ask[i].ans = tp.any();
         }
         else if(ask[i].f == ) {
             tp = bs & (bs2 >> (N - ask[i].x));
             ask[i].ans = tp.any();
         }
         else {
             bool fd = ;
             for(int j = ; j * j <= ask[i].x; j++) {
                 if(ask[i].x % j) {
                     continue;
                 }
                 if(bs[j] && bs[ask[i].x / j]) {
                     ask[i].ans = ;
                     break;
                 }
             }
         }
     }     std::sort(ask + , ask + m + , cmp);
     for(int i = ; i <= m; i++) {
         if(ask[i].ans) {
             puts("hana");
         }
         else {
             puts("bi");
         }
     }
     return ;
 }

AC代码