蒟蒻初学莫队求助大神
查看原帖
蒟蒻初学莫队求助大神
846637
ThChamp楼主2023/7/15 11:56

第一次做莫队的题,改了几次调试感觉没问题,但就是全wa,实在不好调试,只好来求助大神

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

// B = N/√Q N为序列长度,Q为查询次数
struct Q {
    int l;
    int r;
};
int n, q, a[100003], B, cnt[100003], l=1, r, ans;
Q ques[100003];
bool cmp (Q a, Q b) {
    if (a.l/B != b.l/B) { // 左端点不在同一块
        return a.l/B < b.l/B; // 按块排
    } else { // 左端点在同一块
        return a.r > b.r; // 右端点单调递增排
    }
}

void add(int x) { // 在区间中加入x
    cnt[x]++;
    if (cnt[x] == 1)
        ans++;
}

void del(int x) { // 在区间中删除x
    cnt[x]--;
    if (cnt[x] == 0)
        ans--;
} 

int main() {
    cin >> n >> q;
    r = n;
    B = n/sqrt(q);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= q; i++)
        scanf("%d %d", &ques[i].l, &ques[i].r);
    sort(ques+1, ques+1+q, cmp);
    for (int i = 1; i <= n; i++) {
        cnt[a[i]]++;
        if (cnt[a[i]] == 1)
            ans++;
    }
    for (int i = 1; i <= q; i++) {
        Q t = ques[i];
        while (l < t.l) { // l往右移
            del(a[l++]);
        } 
        while (r < t.r) { // r往右移
            add(a[r++]);
        }
        while (l > t.l) { // l往左移
            add(a[--l]);
        }
        while (r > t.r) { // r往左移
            del(a[r--]);
        }
        if (ans == r-l+1)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}

2023/7/15 11:56
加载中...