UVa 11235 (RMQ) Frequent values

范围最值问题，O(nlogn)的预处理，O(1)的查询。

这个题就是先对这些数列进行游程编码，重复的元素只记录下重复的次数。

对于所查询的[L, R]如果它完全覆盖了某些连续的重复片段，那么查询的就是这几种元素重复最多的次数，也就是RMQ。

如果[L, R]还覆盖了某一部分边界，也要单独计算取最大值。

还有个特殊情况就是查询区间都在某一个元素的重复片段中，答案直接就是R-L+1

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 100000 + 10;
const int maxl = 20;

struct RMQ
{
    int d[maxn][maxl];
    void Init(const vector<int>& a)
    {
        int n = a.size();
        for(int i = 0; i < n; i++) d[i][0] = a[i];
        for(int j = 1; (1<<j) <= n; j++)
            for(int i = 0; i + (1<<j) - 1 < n; i++)
                d[i][j] = max(d[i][j-1], d[i + (1<<(j-1))][j-1]);
    }

    int query(int L, int R)
    {
        int k = 0;
        while(1<<(k+1) <= R-L+1) k++;
        return max(d[L][k], d[R-(1<<k)+1][k]);
    }
};

int a[maxn], num[maxn], left[maxn], right[maxn];
RMQ rmq;

int main()
{
    //freopen("in.txt", "r", stdin);

    int n, q;
    while(scanf("%d%d", &n, &q) == 2)
    {
        for(int i = 0; i < n; i++) scanf("%d", &a[i]);
        a[n] = a[n-1] + 1;
        vector<int> count;
        for(int i = 0; i < n; )
        {
            int j = i;
            while(a[j] == a[i]) j++;
            count.push_back(j-i);
            for(int k = i; k < j; k++)
            {
                num[k] = count.size() - 1;
                left[k] = i;
                right[k] = j - 1;
            }
            i = j;
        }

        //for(int i = 0; i < count.size(); i++) printf("%d
", count[i]);

        rmq.Init(count);
        while(q--)
        {
            int L, R, ans;
            scanf("%d%d", &L, &R); L--; R--;
            if(num[L] == num[R]) ans = R - L + 1;
            else
            {
                ans = max(right[L]-L+1, R-left[R]+1);
                if(num[L] + 1 < num[R])
                {
                    ans = max(ans, rmq.query(num[L]+1, num[R]-1));
                }
            }
            printf("%d
", ans);
        }
    }

    return 0;
}