当前位置：首页 > news >正文

洛谷P3674 小清新人渣的本愿

news 来源：原创 2024/5/5 22:59:56

题意：多次询问，区间内是否存在两个数，使得它们的和为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暴力即可。

  1 #include <cstdio>
  2 #include <bitset>
  3 #include <cmath>
  4 #include <algorithm>
  5 
  6 const int N = 100010;
  7 
  8 int fr[N], a[N], bin[N];
  9 std::bitset<N> bs, bs2, tp;
 10 
 11 struct ASK {
 12     int f, l, r, x, t, ans;
 13     inline bool operator <(const ASK &w) const {
 14         if(fr[l] != fr[w.l]) {
 15             return l < w.l;
 16         }
 17         return r < w.r;
 18     }
 19 }ask[N];
 20 
 21 inline bool cmp(const ASK &A, const ASK &B) {
 22     return A.t < B.t;
 23 }
 24 
 25 inline void add(int x) {
 26     if(!bin[a[x]]) {
 27         bs.set(a[x]);
 28         bs2.set(N - a[x]);
 29     }
 30     bin[a[x]]++;
 31     return;
 32 }
 33 
 34 inline void del(int x) {
 35     bin[a[x]]--;
 36     if(!bin[a[x]]) {
 37         bs.reset(a[x]);
 38         bs2.reset(N - a[x]);
 39     }
 40     return;
 41 }
 42 
 43 int main() {
 44     int n, m;
 45     scanf("%d%d", &n, &m);
 46     int T = sqrt(n);
 47     for(int i = 1; i <= n; i++) {
 48         scanf("%d", &a[i]);
 49         fr[i] = (i - 1) / T + 1;
 50     }
 51     for(int i = 1; i <= m; i++) {
 52         scanf("%d%d%d%d", &ask[i].f, &ask[i].l, &ask[i].r, &ask[i].x);
 53         ask[i].t = i;
 54     }
 55     std::sort(ask + 1, ask + m + 1);
 56 
 57     int l = 1, r = 1;
 58     bin[a[1]]++;
 59     bs.set(a[1]);
 60     bs2.set(N - a[1]);
 61     for(int i = 1; i <= m; i++) {
 62         while(l > ask[i].l) {
 63             add(--l);
 64         }
 65         while(r < ask[i].r) {
 66             add(++r);
 67         }
 68         while(l < ask[i].l) {
 69             del(l++);
 70         }
 71         while(r > ask[i].r) {
 72             del(r--);
 73         }
 74         // ------------
 75         if(ask[i].f == 1) {
 76             tp = bs & (bs >> ask[i].x);
 77             ask[i].ans = tp.any();
 78         }
 79         else if(ask[i].f == 2) {
 80             tp = bs & (bs2 >> (N - ask[i].x));
 81             ask[i].ans = tp.any();
 82         }
 83         else {
 84             bool fd = 0;
 85             for(int j = 1; j * j <= ask[i].x; j++) {
 86                 if(ask[i].x % j) {
 87                     continue;
 88                 }
 89                 if(bs[j] && bs[ask[i].x / j]) {
 90                     ask[i].ans = 1;
 91                     break;
 92                 }
 93             }
 94         }
 95     }
 96 
 97     std::sort(ask + 1, ask + m + 1, cmp);
 98     for(int i = 1; i <= m; i++) {
 99         if(ask[i].ans) {
100             puts("hana");
101         }
102         else {
103             puts("bi");
104         }
105     }
106     return 0;
107 }