萌新刚学莫队,WA #1 #3 求助
查看原帖
萌新刚学莫队,WA #1 #3 求助
610557
shinzanmonoszm 妹妹楼主2023/1/8 17:24
#include<iostream>
#include<algorithm>
#include<cmath>
#include<bitset>
#include<vector>
const int sz = 1e5 + 10;
const int sqsz = 500;
std::bitset<sz> b1, b2;
int cnt[sz], arr[sz], ans[sz], n, q, qpp;
struct Query {
    int op, l, r, id, bl, x;
    bool operator<(const Query &a) const {
        if (bl != a.bl) return bl < a.bl;
        if (bl & 1) return r < a.r;
        return r > a.r;
    }
} que[sz];
struct qnode {
    int l, r, id;
};
void add(int x) {
    cnt[arr[x]]++;
    if (cnt[arr[x]] == 1) b1[arr[x]] = b2[n - arr[x]] = 1;
}
void del(int x) {
    cnt[arr[x]]--;
    if (cnt[arr[x]] == 0) b1[arr[x]] = b2[n - arr[x]] = 0;
}
std::vector<qnode> query[sqsz];
int lst[sz], maxl[sz];
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n >> q;
    for (int i = 1; i <= n; i++) std::cin >> arr[i];
    int lim = std::sqrt(n);
    for (int i = 1; i <= q; i++) {
        int op, l, r, x;
        std::cin >> op >> l >> r >> x;
        if (op == 4 && x < sqsz)
            query[x].push_back(qnode{l, r, i});
        else {
            int b = (l - 1) / lim + 1;
            que[++qpp] = Query{op, l, r, i, b, x};
        }
    }
    for (int x = 1; x < sqsz; x++) {
        if (query[x].empty()) continue;
		int last = 0;
		for (int i = 1; i <= n; i++) {
			int y = arr[i];
			lst[y] = i;
		    if (x * y <= 100000) last = std::max(last, lst[x * y]);
			if (y % x == 0) last = std::max(last, lst[y / x]);
			maxl[i] = last;
		}
		for (qnode node: query[x])
			ans[node.id] = (node.l <= maxl[node.r]);
		std::fill(lst + 1, lst + 100001, 0);
		std::fill(maxl + 1, maxl + 100001, 0);
    }
    std::sort(que + 1, que + qpp + 1);
    int l = 1, r = 0;
    for (int i = 1; i <= qpp; i++) {
        int le = que[i].l, re = que[i].r, x = que[i].x;
        while (l > le) add(--l);
        while (r < re) add(++r);
        while (l < le) del(l++);
        while (r > re) del(r--);
        if (que[i].op == 1) ans[que[i].id] = (b1 & (b1 << x)).any();
        if (que[i].op == 2) ans[que[i].id] = (b1 & (b2 >> (n - x))).any();
        if (que[i].op == 3) {
            for (int k = 1; k * k <= x; k++){
                if (x % k == 0 && b1[x] && b1[x / k]) {
                    ans[que[i].id] = 1;
                    break;
                }
            }
        }
        if (que[i].op == 4) {
            for (int k = 1; k * x <= 100000; k++) {
                if (b1[k] && b1[k * x]) {
                    ans[que[i].id] = 1;
                    break;
                }
            }
        }
    }
    for (int i = 1; i <= q; i++)
        std::cout << (ans[i] ? "yuno\n" : "yumi\n");
    return 0;
}

2023/1/8 17:24
加载中...