Posted on 2012-03-26 12:32
C小加 閱讀(995)
評論(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;
}