第一次做莫队的题,改了几次调试感觉没问题,但就是全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;
}