题目链接
个人思路
本题需要统计区间范围内 数值为 x 在区间出现次数也为 x 的数的个数。区间询问 + 多次询问,我们选择 莫队。
将多次询问按照区间边界进行排序,每一次区间的移动,先去判断当前区间指针所指向的数是否符合题目条件,然后对该数的数量进行对应的增减操作,操作完之后,仍需判断当前数是否符合题目条件,因为数量发生了变化。
参考代码
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 3;
/*
https://www.lanqiao.cn/problems/3247/learning/
*/
int n, m, maxn, arr[N], cnt[N], sumn = 0, ans[N];
class Query
{
public:
int id, l, r;
int operator<(const Query &x) const
{
if (l / maxn != x.l / maxn)
return l < x.l;
return (l / maxn) & 1 ? r < x.r : r > x.r;
}
} q[N];
void add(int i)
{
if (cnt[arr[i]] == arr[i])
sumn--;
cnt[arr[i]]++;
if (cnt[arr[i]] == arr[i])
sumn++;
}
void del(int i)
{
if (cnt[arr[i]] == arr[i])
sumn--;
cnt[arr[i]]--;
if (cnt[arr[i]] == arr[i])
sumn++;
}
int main()
{
cin >> n >> m;
maxn = sqrt(n);
for (int i = 1; i <= n; ++i)
cin >> arr[i];
for (int i = 0; i < m; ++i)
{
q[i].id = i;
cin >> q[i].l >> q[i].r;
}
sort(q, q + m);
int l = 1, r = 0;
for (int i = 0; i < m; ++i)
{
while (l > q[i].l)
{
add(--l);
}
while (r < q[i].r)
{
add(++r);
}
while (l < q[i].l)
{
del(l++);
}
while (r > q[i].r)
{
del(r--);
}
ans[q[i].id] = sumn;
}
for (int i = 0; i < m; ++i)
{
cout << ans[i] << "\n";
}
return 0;
}
Java
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static class Query implements Comparable<Query> {
public int id, l, r;
@Override
public int compareTo(Query x) {
if (l / maxn != x.l / maxn)
return Integer.compare(l, x.l);
return (l / maxn) % 2 == 1 ? Integer.compare(r, x.r) : Integer.compare(x.r, r);
}
}
static int n, m, maxn, sumn = 0;
static int[] arr, cnt, ans;
static Query[] q;
static void add(int i) {
if (cnt[arr[i]] == arr[i])
sumn--;
cnt[arr[i]]++;
if (cnt[arr[i]] == arr[i])
sumn++;
}
static void del(int i) {
if (cnt[arr[i]] == arr[i])
sumn--;
cnt[arr[i]]--;
if (cnt[arr[i]] == arr[i])
sumn++;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
maxn = (int) Math.sqrt(n);
arr = new int[n + 1];
cnt = new int[n + 1];
ans = new int[m];
q = new Query[m];
for (int i = 1; i <= n; ++i)
arr[i] = scanner.nextInt();
for (int i = 0; i < m; ++i) {
q[i] = new Query();
q[i].id = i;
q[i].l = scanner.nextInt();
q[i].r = scanner.nextInt();
}
Arrays.sort(q, 0, m);
int l = 1, r = 0;
for (int i = 0; i < m; ++i) {
while (l > q[i].l) {
add(--l);
}
while (r < q[i].r) {
add(++r);
}
while (l < q[i].l) {
del(l++);
}
while (r > q[i].r) {
del(r--);
}
ans[q[i].id] = sumn;
}
for (int i = 0; i < m; ++i) {
System.out.println(ans[i]);
}
}
}
由于还处于初学莫队,找了几个简单的莫队类型题目练练手,近期类似问题做了好几个,有兴趣的可以去我的蓝桥专栏下面看看。