「Luogu 3674」小清新人渣的本愿 (Bitset + 莫队 + 复杂度分析)

发表于 | | + s

Luogu 3674
题意：给你一个序列，长度为$n$，有$m$次操作，每次询问一个区间是否可以选出两个数它们的差为$x$，或者询问一个区间是否可以选出两个数它们的和为$x$，或者询问一个区间是否可以选出两个数它们的乘积为x ，这三个操作分别为操作$1,2,3$。选出的这两个数可以是同一个位置的数

无修改无强制在线，则离线即可。
给出了值域范围，那么就是让我们记录这些值
考虑如何记录。可以开桶来记录。但是这里我们并不需要知道某个数出现了几次，只需要知道有没有即可。对于这种01数组，我们可以想到bitset

设维护值域下的bitset为$\operatorname{bs}$
对于询问一个$x=a-b$，那么就相当于bs & (bs >> x)不为假。可以当做一个平移的感觉。
对于询问$x=a+b$，我们可以维护一个反的bitset，然后达到将其左移后能和原来正着的bitset有值的效果，具体可以模拟一下。

对于乘法，直接$\sqrt x$枚举即可。

知识点：
1、Bitset 左移右移 技巧
2、乘法复杂度分析

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<bitset>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 100000 + 5, ZY = 100000;

    int n, m, blolen, bl[MAXN], a[MAXN];
    int nl, nr, tax[MAXN], ans[MAXN];
    bitset<ZY + 5 > bs1, bs2;

    struct qry {
        int l, r, ty, x, id;
        bool operator < (const qry &rhs) const {
            return bl[l] == bl[rhs.l] ? r < rhs.r : bl[l] < bl[rhs.l];
        }
    } xw[MAXN];

    void inc(int pos) {
        if (++tax[a[pos]] == 1) bs1[a[pos]] = bs2[ZY - a[pos]] = 1; 
    }
    void dec(int pos) {
        if (--tax[a[pos]] == 0) bs1[a[pos]] = bs2[ZY - a[pos]] = 0; 
    }

    void clean() {
        ms(ans, 0), ms(bl, 0), ms(tax, 0);
    }
    int solve() {

        clean();
        cin >> n >> m;
        blolen = (int)sqrt(n);
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), bl[i] = (i - 1) / blolen + 1;

        for (int i = 1; i <= m; ++i) {
            scanf("%d%d%d%d", &xw[i].ty, &xw[i].l, &xw[i].r, &xw[i].x);
            xw[i].id = i;
        }

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

        nl = 1, nr = 0;
        for (int i = 1; i <= m; ++i) {
            while (nl > xw[i].l) inc(nl - 1), --nl;
            while (nr < xw[i].r) inc(nr + 1), ++nr;
            while (nl < xw[i].l) dec(nl), ++nl;
            while (nr > xw[i].r) dec(nr), --nr;

            if (xw[i].ty == 1) {
                if ((bs1 & (bs1 >> xw[i].x)).count()) ans[xw[i].id] = 1;
            } else if (xw[i].ty == 2) {
                if ((bs1 & (bs2 >> (ZY - xw[i].x))).count()) ans[xw[i].id] = 1;
                //for (int i = ZY; i >= ZY - 10; --i) printf("%d", (int)bs2[i]);
            } else if (xw[i].ty == 3) {
                for (int j = 1; j * j <= xw[i].x; ++j) {
                    if (xw[i].x % j == 0) {
                        if (bs1[j] && bs1[xw[i].x / j]) {
                            ans[xw[i].id] = 1;
                            break;
                        }
                    }
                }
            }

        }

        for (int i = 1; i <= m; ++i) 
            printf("%s", ans[i] ? "hana\n" : "bi\n");

        return 0;
    }
}
int main() { 
    flyinthesky::solve();
    return 0;
}
/*
5 1
1 1 2 3 4
2 3 5 7
*/
------ 本文结束 ------