感觉在哪做过的一道题.

Description

给一列数, 每次询问一个区间, 问能不能用这个区间内的两个数(可以是同一个), 相加/相减/相乘出询问的数.

Solution

总觉得是某道题是一样的套路, 小清新系列的一道题.

乘法直接暴力枚举约数.

用bitset维护正负两个的出现情况, 负数的用常量$maxv$减一下, 然后查询的时候加减法就推推式子, 移位以后再与一下, 检查有没有值就行了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e+5 + 5;

int n, m, a[maxn], r[maxn], bel[maxn], mx, ans[maxn];
struct question {
  int l, r, t, x, id;
  inline bool operator<(const question &rhs) const {
    return (bel[l] == bel[rhs.l]) ? r < rhs.r : bel[l] < bel[rhs.l];
  }
}q[maxn];
bitset<maxn> cur, ruc, upd;
int cnt[maxn];

inline int rd() {
  register int x = 0, c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return x;
}
inline void add(int x) {
  if (!cnt[x]) cur[x] = 1, ruc[mx - x] = 1;
  cnt[x]++;
}
inline void del(int x) {
  if (cnt[x] == 1) cur[x] = 0, ruc[mx - x] = 0;
  cnt[x]--;
}

int main() {
  n = rd(); m = rd();
  mx = 100001;
  for (int i = 1; i <= n; ++i)
    a[i] = rd(), r[i] = mx - a[i];//, mx = max(mx, a[i]);
  int blo = sqrt(n);
  for (int i = 1; i <= n; ++i)
    bel[i] = (i - 1) / blo + 1;
  for (int i = 1; i <= m; ++i) {
    q[i].t = rd(); q[i].l = rd(); q[i].r = rd(); q[i].x = rd();
    q[i].id = i;
    //mx = max(mx, q[i].x);
  }
  sort(q + 1, q + 1 + m);
  int L = 1, R = 0;
  for (int i = 1; i <= m; ++i) {
    while (L > q[i].l) add(a[--L]);
    while (R < q[i].r) add(a[++R]);
    while (L < q[i].l) del(a[L++]);
    while (R > q[i].r) del(a[R--]);
    if (q[i].t == 1) {
      upd = ((cur >> q[i].x) & cur);
      ans[q[i].id] = upd.count();
    } else if (q[i].t == 2) {
      upd = ((ruc >> (mx - q[i].x)) & cur);
      ans[q[i].id] = upd.count();
    } else {
      int lim = sqrt(q[i].x);
      for (int j = 1; j <= lim; ++j) {
        if (!(q[i].x % j)) {
          if (cnt[j] && cnt[q[i].x / j]) {
            ans[q[i].id] = 1;
            break;
          }
        }
      }
    }
  }
  for (int i = 1; i <= n; ++i)
    puts(ans[i] ? "yuno" : "yumi");
  return 0;
}