Frequent values

题目链接：https://vjudge.net/problem/POJ-3368

思路

我的代码有两个预处理：
第一个init: 将数组中的相等的元素，用首项是1，公差是1的等差数列表示，放在cnt[]中 然后用R[]数组，来表示某个元素所在段的下一段的起点 这个初始化，可以把我代码中的cnt[]和R[]打印出来，一看就能明白
预处理init_st:
就是对于cnt这个数组，求区间最大值。
处理的时候，有可能L所在段是被切断的，所以第一段可能不完整，但是在一段内cnt[]是一个前缀和，所以可以通过上面R[]定位到下一段的开始，就可以用前缀和高出这一段的元素个数，然后l = R[l]就把l移动到下一段的开始，然后直接查ST表就得出了[l,r]区间cnt[]中的最大值

代码

#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5+10;
using namespace std;

int N,Q;
int arr[maxn];
int cnt[maxn],R[maxn];
int st[maxn][30];

inline void read(int &x){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}

void init_st(){
    for(int i = 1;i<=N;i++) st[i][0] = cnt[i];
    int len = log(N)/log(2);
    for(int j = 1;j<=len;j++){
        for(int i = 1;i<=N-(1<<j)+1;i++){
            st[i][j] = max(st[i][j-1],st[i + (1<<(j-1))][j-1]);
        }
    }
}
void init(){
    arr[0] = -2e9;
    for(int i = 1;i<=N;i++){
        if(arr[i] != arr[i-1]) cnt[i] = 1;
        else cnt[i] = cnt[i-1] + 1;
    }
    int last = N+1;
    for(int i = N;i>=1;i--){
        R[i] = last;
        if(cnt[i] == 1) last = i;
    }
}
int main(){
    while(scanf("%d",&N)){
        if(N == 0) break;read(Q);
        for(int i = 1;i<=N;i++) read(arr[i]);
        init();
        init_st();
        while(Q--){
            int l,r;read(l),read(r);
            int ans = cnt[min(R[l]-1,r)] - cnt[l] + 1;
            l = R[l];
            if(l<=r){
                int len = log(r-l+1)/log(2);
                ans = max(ans,max(st[l][len],st[r-(1<<len)+1][len]));
            }
            printf("%d\n",ans);
        }

    }

    return 0;
}