Input
There are several cases. The first line of each case contains tow integers n, q(1<=n,q<=100000), indicating the array length and the number of queries.The second line contains n positive integers ai(1 <= ai <= 100000).Next q lines contain three positive integers i,j,x(1<=i<=j<=n).
Output
Sample Input
Sample Output
/*
lower_bound( , , x)
是用二分从begin 到 end 找序号大于等于 x 的第一个值为y的迭代器下标
大意：在l到r之间询问k出现的次数
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int MAX = 1000100;
vector<int> G[MAX];
int a[MAX];
int cal(int x, int y)
{
return lower_bound( G[y].begin(), G[y].end(), x) - G[y].begin();
}
int main()
{
int n, m;
int l, r, k;
while(~scanf("%d%d", &n, &m)){
for(int i = 1; i <= n; i++)
G[a[i]].clear();
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
G[a[i]].push_back(i);
}
for(int i = 1; i <= m; i++){
scanf("%d%d%d", &l, &r, &k);
printf("%d\n", cal(r + 1 , k) - cal(l , k));
}
}
return 0;
}
原文：http://www.cnblogs.com/zero-begin/p/4656680.html