题目大意:给定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;
}