codeforces 221D

题意：给出一个数组，查询区间刚好x出现的次数等于x的数的个数。

思路：首先x的值得符合小于等于n,其次假设有n个符合，那么的话1+2+……+n=1e5，我们会发现最多有400多个数。

那么符合的数满足什么呢？或者说满足什么条件才有可能是这种数呢，那当然是x在数组中出现的次数大于x的数才有可能对答案有贡献，这样的数不超过500个。然后对于每一个数求一次个数前缀和，计算对每一个查询区间的贡献值。

#include
using namespace std;
const int maxn = 100000 + 10;
typedef long long ll;
#define clr(x,y) memset(x,y,sizeof x)
#define INF 0x3f3f3f3fint a[maxn];
int ans[maxn],cnt[maxn];
int L[maxn],R[maxn];
int sum[maxn];int main()
{int n,m;while( ~ scanf("%d%d",&n,&m)){clr(ans,0);clr(cnt,0);for(int i = 1;i <= n;i ++){scanf("%d",&a[i]);if(a[i] <= n)cnt[a[i]] ++;}for(int i = 1;i <= m;i ++)scanf("%d%d",&L[i],&R[i]);sum[0] = 0;for(int i = 1;i <= n;i ++){if(cnt[i] >= i)//最多存在500个{for(int j = 1;j <= n;j ++)sum[j] = sum[j - 1] + (a[j] == i);for(int j = 1;j <= m;j ++)if(sum[R[j]] - sum[L[j] - 1] == i)ans[j] ++;}}for(int i = 1;i <= m;i ++)printf("%d\n",ans[i]);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！