莫队：一种离线处理的优化暴力解法，时间复杂度在n * n^(1/2)，会被卡常数，但是极为简单
推荐视频：莫队算法
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int pos[N];
struct node {
int l, r, k;
}t[N];
string s[N];
int cnt[N],sum;
void Add(int x) {
cnt[a[x]]++;
if (cnt[a[x]] == 1) sum++;
}
void Sub(int x) {
cnt[a[x]]--;
if (cnt[a[x]] == 0) sum--;
}
int main() {
int n,m;
cin >> n>>m;
for (int i = 1; i <= n; i++) cin >> a[i];
int siz = sqrt(n);
for (int i = 1; i <= n; i++) {
pos[i] = i / siz;//分区块
}
for (int i = 1; i <= m; i++) {
cin >> t[i].l >> t[i].r;
t[i].k = i;//离线处理
}
sort(t + 1, t + 1 + m, [](node a, node b) {
return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];//排序，如果在一个区块以右端点排序，不在同一区块以区块顺序排序
});
int l = 1, r = 0;//初始化
for (int i = 1; i <= m; i++) {
while (t[i].l < l) Add(--l);//目标点在左，跟新且加上当前点
while (t[i].r > r) Add(++r);
while (t[i].l > l) Sub(l++);//减去
while (t[i].r < r) Sub(r--);
if (t[i].r - t[i].l + 1 == sum) s[t[i].k] = "Yes";
else s[t[i].k] = "No";
}
for (int i = 1; i <= m; i++) {
cout << s[i] << '\n';
}
return 0;
}