题目描述

给定一个元素个数为 n 的整数数组 a 和 Q 个问题，每个问题有 x，y 两个参数，请统计共有多少个整数 K 满足 K 在 a[x]…a[y] 中出现了恰好 K 次。

输入格式

第一行两个整数 n，Q，表示数组 a 的元素个数和询问数；

接下来一行 n 给整数，描述数组 a ；

接下来 Q 行，每行两个数 xi,yi（1≤xi≤yi≤n），表示询问的左右边界。

输出格式

输出 Q 行，每行一个整数表示满足询问的 K 的个数。

样例数据 1

输入

7 2

3 1 2 2 3 3 7

1 7

3 4

输出

3

1

备注

样例说明

Q1: 1、2、3 分别满足，所以共有 3 个数满足要求。

Q2: 2 满足，所以只有 1 个数满足要求。

数据范围

对 50% 的输入数据：1≤n,Q≤1000

对 100% 的输入数据：1≤n,Q≤100000，1≤a[i]≤109

题目分析

莫队裸题，因为不熟练所以第一次没有分块，导致时间复杂度退化。

一定要分块！！！

转莫队的时间复杂度证明：

右端点移动：

首先我们考虑一个块里面的转移情况

由于一个块里面的询问都按右端点排序

所以我们右端点在一个块里面最多移动n次

有 O(√n)个块，那么同一个块内的右端点移动最多就是O(n√n)

然后考虑从一个块到另一个块导致的右端点变化

最坏情况，右端点由n到1，那么移动n次

有 O(√n)个块

那么从一个块到另一个块的事件只会发生O(√n)次……

所以这种右端点移动的次数也是O(n√n)次

没有别的事件导致右端点移动了

左端点移动：

同一个块里面，由于左端点都在一个长度为O(√n)的区间里面

所以在同一块里面移动一次，左端点最多变化O(√n)

总共有n个询问……

所以同一块里面的移动最多n次

那么同一个块里面的左端点变化最多是O(n√n)的

考虑跨越块

每由第i个块到第i+1个块，左端点最坏加上O(√n)

总共能加上O(√n)次

所以跨越块导致的左端点移动是O(n)的

综上，分块做法是O(n∗√n)。

code

#include<iostream>

#include<cstdio>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<cmath>

#include<vector>

#include<algorithm>

#include<queue>

using namespace std;

const int N = 100000;

int n, Q, cnt[N + 5], ans;

int a[N + 5], b[N + 5], len, ret[N + 5];

bool vst[N + 5];

int S;

struct node{

	int x, y, id, bl;

	node(){}

	node(int _x, int _y, int o, int b):x(_x), y(_y), id(o), bl(b){}

	inline bool operator < (const node &p) const{

		if(bl != p.bl) return bl < p.bl;

		return y < p.y;

	}

}qry[N + 5];

inline int read(){

	int i = 0, f = 1; char ch = getchar();

	for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());

	if(ch == '-') f = -1, ch = getchar();

	for(; ch >= '0'&& ch <= '9'; ch = getchar())

		i = (i << 1) + (i << 3) + (ch - '0');

	return i * f;

}

inline void disc_init(){

	sort(b + 1, b + n + 1);

	len = unique(b + 1, b + n + 1) - (b + 1);

	for(int i = 1; i <= n; i++){

		a[i] = lower_bound(b + 1, b + len + 1, a[i]) - b;

		cnt[a[i]]++;

	}

}

inline void wr(int x){

	if(x < 0) x = -x, putchar('-');

	if(x > 9) wr(x / 10);

	putchar(x % 10 + '0');

}

int main(){

//	freopen("count.in", "r", stdin);

//	freopen("count.out", "w", stdout);

	n = read(), Q = read();

	S = sqrt(n);

	for(int i = 1; i <= n; i++) a[i] = b[i] = read();

	for(int i = 1; i <= Q; i++){

		int x = read(), y = read();

		qry[i] = node(x, y, i, (x - 1) / S + 1);

	}

	sort(qry + 1, qry + Q + 1);

	disc_init();

	for(int i = 1; i <= n; i++){

		if(vst[a[i]]) continue;

		vst[a[i]] = true;

		if(cnt[a[i]] == b[a[i]])

			ans++;

	}

	int head = 1, tail = n;

	for(int i = 1; i <= Q; i++){

		int x = qry[i].x, y = qry[i].y;

		while(head > x){

			head--;

			if(cnt[a[head]] == b[a[head]]) ans--;

			cnt[a[head]]++;

			if(cnt[a[head]] == b[a[head]]) ans++;

		}

		while(head < x){

			if(cnt[a[head]] == b[a[head]]) ans--;

			if(cnt[a[head]] - 1 == b[a[head]]) ans++;

			cnt[a[head]]--, head++;

		}

		while(tail > y){

			if(cnt[a[tail]] == b[a[tail]]) ans--;

			if(cnt[a[tail]] - 1 == b[a[tail]]) ans++;

			cnt[a[tail]]--, tail--;

		}

		while(tail < y){

			tail++;

			if(cnt[a[tail]] == b[a[tail]]) ans--;

			cnt[a[tail]]++;

			if(cnt[a[tail]] == b[a[tail]]) ans++;

		}

		ret[qry[i].id] = ans;

	}

	for(int i = 1; i <= Q; i++)

		wr(ret[i]), putchar('\n');

	return 0;

}

巴特西

NOIP模拟 - 莫队