Posted on 2012-03-26 12:32
C小加 阅读(981)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
比赛的时候手写的二分，总是RE。边界处理的能力还有待加强。
看了解题报告之后感觉自己弱爆了，知道方法的题都写不出来。而且当时还是用的map写的，悲剧的超时了。改用vector就过了。
把每个数字出现的位置存储下来，然后对所求的位置进行两次二分，就OK了。用的是stl里的二分，没想到迭代器还可以这样用。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#include<vector>
using namespace std;
vector<
int> m[100003];
int main()
{
int n,q;
while(scanf("%d %d",&n,&q)!=EOF)
{
for(
int i=0;i<100003;++i)
m[i].clear();
int val,l,r,x;
for(
int i=1;i<=n;++i)
{
scanf("%d",&val);
m[val].push_back(i);
}
for(
int i=1;i<=q;i++)
{
scanf("%d %d %d",&l,&r,&x);
if(m[x].size()!=0)
if( *(--m[x].end())<l || *m[x].begin()>r )
printf("0\n");
else {
int ans=( (--upper_bound(m[x].begin(),m[x].end(),r))-m[x].begin() )-( lower_bound(m[x].begin(),m[x].end(),l)-m[x].begin() )+1;
printf("%d\n",ans);
}
else printf("0\n");
}
}
return 0;
}