P5355

FiraCode · 2022-11-18 16:11:23 · 个人记录

--------------------------------------求积--------------------------------------

乘积的话就可以枚举因数，若他的两个因子都在区间里出现过，那么就输出 yuno 否则就输出 yumi。

--------------------------------------求差--------------------------------------

差值的话就是用一个二进制来表示区间的出现的数，那么差是否有 x，就是把这个二进制左移 x 位，那么当他于以前的二进制的并还是有 1 的话，就可以。

用 bitset 来维护的话就是 (s&(s << x)).any()。

--------------------------------------求和--------------------------------------

那么加的话就是看把前 x 位翻转之后，原来的第 i 位和现在的第 i 位是不是都是 1。

但是翻转我们怎么做呢？

我们就可以设另一个 bitset，比如叫 T，那么 T 就是当 x 位为 1 的时候，我们把 n - x 设成 1，其中 n 是 bitset 的长度。

那么翻转的结果就是 T 的后 x 个。

那么判断的话就是 (s << (n - x))) & T。

那么时间复杂度就变成了 O(\frac{n}{w})。

但是我们怎么求某一段的二进制的值呢？

我们可以用莫队来做。

然后就可用 bitset + 莫队 来稿。

----------------------------------------CODE----------------------------------------

#include <bits/stdc++.h>

using namespace std;

#define I return
#define AK 0
#define IOI ;

typedef long long ll;

const int N = 100010, B = 500, M = 100000;
int ans[N];
int n, m, a[N], cnt[N];
bitset<N> s, t; //正着和反着的bitset
array<int, 5> q[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for (int i = 0; i < m; ++i) { //读入查询
        int opt, l, r, x;
        scanf("%d%d%d%d", &opt, &l, &r, &x);
        q[i] = {opt, l, r, x, i};
    }

    sort(q, q + m, [&](array<int, 5> a, array<int, 5> b) {
        int c = a[1] / B;
        if (c != b[1] / B) return c < b[1] / B;
        return c % 2 ? a[2] > b[2] : a[2] < b[2]; //莫队玄学优化 
    });

    int l = 1, r = 0;
    auto add = [&](int x) {
        cnt[a[x]] ++;
        if(cnt[a[x]] == 1) {//从没有变成有
            s[a[x]] = 1;//第一次有，都设成1
            t[M - a[x]] = 1;
        }
    };
    auto del = [&](int x) {//删除
        cnt[a[x]] --;
        if (cnt[a[x]] == 0) {//从有变成没有
            s[a[x]] = 0;//没有了，都设成0
            t[M - a[x]] = 0;
        }
    };

    for (int i = 0; i < m; ++i) {
        while(r < q[i][2]) ++r, add(r);
        while(l > q[i][1]) --l, add(l);
        while(r > q[i][2]) del(r), --r;
        while(l < q[i][1]) del(l), ++l;
        int opt = q[i][0], id = q[i][4], x = q[i][3];
        if (opt == 1) {//减法
            ans[id] = (s & (s << x)).any();
        } else if (opt == 2) {//加法
            ans[id] = (t & (s << (M - x))).any();
        } else {//乘法
            for (int y = 1; y <= x / y; ++y) {
                if (x % y == 0) {
                    ans[id] |= s[y] & s[x / y];
                }
            }
        }
    }
    for (int i = 0; i < m; ++i)
        puts(ans[i] ? "yuno" : "yumi");
    I AK IOI
}