[Luogu 3674]小清新人渣的本愿

时间：2023-01-30 07:02:12

Description

题库链接

给你一个序列 \(A\) ，长度为 \(n\) ，有 \(m\) 次操作，每次询问一个区间是否可以

  1. 选出两个数它们的差为 \(x\) ；
  2. 选出两个数它们的和为 \(x\) ；
  3. 选出两个数它们的乘积为 \(x\) 。

\(1\leq n,m,A_i\leq 100000\)

Solution

前两个操作 \(bitset\) 可以解决；后一个操作直接暴力枚举因数单个询问 \(O(\sqrt n)\) 。复杂度承受得起。

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

int n, m, lim, A[N], cnt[N], ans[N];

bitset<(N<<1)>a, b, c;

struct tt {

    int opt, l, r, x, id;

    bool operator < (const tt &b) const {

        return l/lim == b.l/lim ? r < b.r : l < b.l;

    }

}p[N];

void moveout(int x) {

    ++cnt[A[x]]; if (cnt[A[x]] == 1) a[A[x]] = b[N+A[x]] = c[N-A[x]] = 1;

}

void movein(int x) {

    --cnt[A[x]]; if (cnt[A[x]] == 0) a[A[x]] = b[N+A[x]] = c[N-A[x]] = 0;

}

void work() {

    scanf("%d%d", &n, &m), lim = sqrt(n);

    for (int i = 1; i <= n; i++) scanf("%d", &A[i]);

    for (int i = 1; i <= m; i++)

        scanf("%d%d%d%d", &p[i].opt, &p[i].l, &p[i].r, &p[i].x),

        p[i].id = i;

    sort(p+1, p+m+1);

    int curl = 1, curr = 0;

    for (int i = 1; i <= m; i++) {

        int l = p[i].l, r = p[i].r, x = p[i].x;

        while (curr < r) ++curr, moveout(curr);

        while (curl > l) --curl, moveout(curl);

        while (curr > r) movein(curr), --curr;

        while (curl < l) movein(curl), ++curl;

        if (p[i].opt == 1) if ((a&(a<<x)).any()) ans[p[i].id] = 1;

        if (p[i].opt == 2) if ((b&(c<<x)).any()) ans[p[i].id] = 1;

        if (p[i].opt == 3) {

            int lim = sqrt(x);

            for (int j = 1; j <= lim; j++)

                if (x%j == 0 && cnt[j] && cnt[x/j]) {ans[p[i].id] = 1; break; }

        }

    }

    for (int i = 1; i <= m; i++) puts(ans[i] ? "hana" : "bi");

}

int main() {work(); return 0; }

else

对于一个叫做 foo 的 bitset ：

  • foo.size() 返回大小（位数）
  • foo.count() 返回1的个数
  • foo.any() 返回是否有1
  • foo.none() 返回是否没有1
  • foo.set() 全都变成1
  • foo.set(p) 将第p + 1位变成1
  • foo.set(p, x) 将第p + 1位变成x
  • foo.reset() 全都变成0
  • foo.reset(p) 将第p + 1位变成0
  • foo.flip() 全都取反
  • foo.flip(p) 将第p + 1位取反
  • foo.to_ulong() 返回它转换为unsigned long的结果，如果超出范围则报错
  • foo.to_ullong() 返回它转换为unsigned long long的结果，如果超出范围则报错
  • foo.to_string() 返回它转换为string的结果

相关文章