Description

我有一个元素个数为\(n\)的整数数组\(a\)和\(Q\)个问题，每个问题有\(x,y\)两个参数，我要数有多少个整数\(K\)满足\(K\)在\(a[x]…a[y]\)中出现了恰好\(K\)次。

题面就这么简单了。

Input

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

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

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

Output

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

Sample Input

7 2

3 1 2 2 3 3 7

1 7

3 4

Sample Output

3

1

Hint

对于30%的数据，\(1 \le n,Q \le 1000\);

对于100%的数据，\(1 \le n,Q \le 100000，1 \le a[i] \le 10^9\)；

sb莫队题目。。。1个元素支持\(O(1)\)加入。

#include<cmath>

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstdlib>

using namespace std;

#define maxn (100010)

int N,tot,Q,A[maxn],num[maxn],ans[maxn],lim,size;

inline int gi()

{

	char ch; int f = 1,ret = 0;

	do ch = getchar(); while (!(ch >= '0'&&ch <= '9')&&ch != '-');

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

	do ret = ret*10+ch-'0',ch = getchar(); while (ch >= '0'&&ch <= '9');

	return ret*f;

}

struct node

{

	int l,r,id;

	inline void read(int i) { l = gi(),r = gi(); id = i; lim = max(lim,r); }

}query[maxn];

inline bool cmp1(const node &a,const node &b) { return a.l < b.l; }

inline bool cmp2(const node &a,const node &b) { return a.r < b.r; }

inline void work()

{

	int res = 0,L = query[1].l,R = query[1].r;

	for (int i = L;i <= R;++i)

		if (A[i] <= N)

		{

			if (num[A[i]] == A[i]) --res;

			if (++num[A[i]] == A[i]) ++res;

		}

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

	{

		while (R < query[i].r)

		{

			++R;

			if (A[R] <= N)

			{

				if (num[A[R]] == A[R]) --res;

				if (++num[A[R]] == A[R]) ++res;

			}

		}

		while (R > query[i].r)

		{

			if (A[R] <= N)

			{

				if (num[A[R]] == A[R]) --res;

				if (--num[A[R]] == A[R]) ++res;

			}

			--R;

		}

		while (L > query[i].l)

		{

			--L;

			if (A[L] <= N)

			{

				if (num[A[L]] == A[L]) --res;

				if (++num[A[L]] == A[L]) ++res;

			}

		}

		while (L < query[i].l)

		{

			if (A[L] <= N)

			{

				if (num[A[L]] == A[L]) --res;

				if (--num[A[L]] == A[L]) ++res;

			}

			++L;

		}

		ans[query[i].id] = res;

	}

}

int main()

{

	freopen("1364.in","r",stdin);

	freopen("1364.out","w",stdout);

	N = gi(); Q = gi();

	for (int i = 1;i <= N;++i) A[i] = gi();

	for (int i = 1;i <= Q;++i) query[i].read(i);

	size = ceil(sqrt(lim)+0.5);

	sort(query+1,query+Q+1,cmp1);

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

	{

		for (j = i;j < Q&&query[j+1].l - query[i].l <= size;++j);

		sort(query+i,query+j+1,cmp2);

	}

	work();

	for (int i = 1;i <= Q;++i) printf("%d\n",ans[i]);

	fclose(stdin); fclose(stdout);

	return 0;

}

巴特西

sjtu1364 countcountcount

Description

Input

Output

Sample Input

Sample Output

Hint

最新文章

热门文章