POJ 3368 Frequent Values

N = 100000問題が深刻に解けない現実（かと言ってtopcoderのN = 50もあんまり解けてないが）をふまえSegmentTreeの問題を解くことにした。
3368 -- Frequent values
広義単調増加の数列が与えられるので、区間[l, r]で一番たくさん出てくる数字の出現回数を答えろ、という非常にシンプルな問題。
とりあえず
[-1 -1 1 1 1 1 3 10 10 10] →　[2 4 1 3]
のようにおきかえてRange Max Queryの問題に変換することを考える。
iについて、iが入る区間[l,r]と簡単に対応させられるようにインデックスを持っておくと実装が楽になる（たぶん）。

#include <vector>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)

const int INF = 1e9;
template<class T, int MAX_N>
struct SegmentTree_MAX {
    int n;
    T data[MAX_N * 2 - 1];
    void init(int n_) {
        n = 1;
        while(n < n_) n *= 2;
        fill_n(data, 2 * n - 1, 0);
    }
    void update(int k, T a) {//0-indexed
        k += n - 1;
        data[k] = a;
        while(k > 0) {
            k = (k - 1) >> 1;
            data[k] = max(data[k * 2 + 1], data[k * 2 + 2]); 
        }
    }
    T __query(int a, int b, int k, int l, int r) {
        if(r <= a || b <= l) return 0;
        if(a <= l && r <= b) return data[k];
        else {
            T val_l = __query(a, b, k * 2 + 1, l, (l + r) >> 1);
            T val_r = __query(a, b, k * 2 + 2, (l + r) >> 1, r);
            return max(val_l, val_r);
        }
    }
    T query(int a, int b) { //[a, b)
        return __query(a, b, 0, 0, n);
    }
};
SegmentTree_MAX<int, 1 << 17> segMax;

int a[100000];
int b[100000];
void solve(int N) {
    int Q; scanf("%d", &Q);
    rep(i, N) scanf("%d", a + i);
    vector<pair<int, int> > range;
    int l = 0, before = 0;
    rep(i, N) {
        if(i == 0) {
            before = a[i];
            continue;
        }
        if(before != a[i]) {
            range.push_back(make_pair(l, i - 1));
            l = i;
        }
        before = a[i];
        b[i] = range.size();
    }
    range.push_back(make_pair(l, N - 1));
    segMax.init(range.size());
    rep(i, range.size()) segMax.update(i, range[i].second - range[i].first + 1);
    rep(_, Q) {
        int l, r;
        scanf("%d%d", &l, &r);
        --l; --r;
        int cl = 0, cr = 0;
        int ql = b[l], qr = b[r];
        if(ql == qr) {
            printf("%d\n", r - l + 1);
            continue;
        }
        if(range[ql].first < l) {
            ++ql;
            cl = range[ql].first - l;
        }
        if(range[qr].second > r) {
            --qr;
            cr = r - range[qr].second;
        }
        printf("%d\n", max(max(cl, cr), segMax.query(ql, qr + 1)));
    }
    return;
}

int main() {
    int N;
    while(~scanf("%d", &N) && N) solve(N);
}

複数ケースあるのにテストケースを一つしか書かないのやめてほしい。