链接：https://www.nowcoder.com/acm/contest/136/D
来源：牛客网
题目描述
WHZ送给了HtBest一个“字符串丝带”，这条丝带由n个小写字母按照一定的顺序排列组成，HtBest收到新礼物后有许多问题，类似“第i个位置的字母在前i个位置中出现了几次？”，HtBest很希望知道答案，于是求助你帮忙解答。
输入描述:
第一行有2个正整数n，m，分别表示丝带长度和问题个数。
第二行，有n个小写字母，第i个表示丝带第i位的小写字母。
接下来有m行，每行一个正整数 ，表示HtBest的一个问题。
输出描述:
共m行，对于每个问题，给出答案。
示例1
输入
复制
3 3
abc
1
2
3
输出
复制
1
1
1
示例2
输入
复制
4 4
abba
1
2
3
4
输出
复制
1
1
2
2
示例3
输入
复制
7 7
yyuahhy
7
6
5
4
3
2
1
输出
复制
3
2
1
1
1
2
1
备注:
对于100%的测试数据：
1 ≤ n ≤ 1000000
数据量较大，注意使用更快的输入输出方式。

一开始直接用数组存，然后dp更新，爆内存了
因为一个数组里有很多个相同的数是没必要的，然后用vector，还是超时了，发现不用O(N)找，用lower_bound()二分找就好了

代码：

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
using namespace std;
const int N=1000020;
char s[N];
int n,m;
vector<int> res[26];
int main(void){
    scanf("%d%d",&n,&m);
    scanf("%s",s);
    for(int i=0;i<n;i++){
        res[s[i]-'a'].push_back(i+1);
    }
    int q;
    while(m--){
        scanf("%d",&q);
        int cnt=0;
        int idx=s[q-1]-'a';
        cnt=lower_bound(res[idx].begin(),res[idx].end(),q)-res[idx].begin();
        printf("%d\n",cnt+1);
    }
    return 0;
}