牛客NOIP暑期七天营-普及组3-C区间中最多的数

题目大意：给定n个数，q次询问，每次问区间[l, r]直接出现最多的数字是什么？并列的话输出较大数。

从数据范围看，O(qn)超时，O(qa)不超时。

空间限制128M，开一个100*200000的数组刚好不超时。

预处理每种数字出现的前缀和，对于每个循环，分别O(1)求出每种数字的数量，记录最优值即可。

（c[i][j]表示数字i在[1, j]出现的次数。）

#include <stdio.h>
int n, m, i, j, k, x, y;
int c[105][200005], d[105];
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++){
        scanf("%d", &k);
        c[k][i] = 1;
    }
    for(i=1; i<=100; i++){
        for(j=1; j<=n; j++){
            c[i][j] += c[i][j-1];
        }
    }
    while(m--){
        scanf("%d%d", &x, &y);
        for(i=k=1; i<=100; i++){
            d[i] = c[i][y] - c[i][x-1];
            if(d[i] >= d[k]) k = i;
        }
        printf("%d\n", k);
    }
    return 0;
}