POJ-3368, SPOJ-FREQUENT, UVa-11235, TJU-2913: Frequent values

keyword

RMQ　C++

問題概要

長さN(<10^5)の増加数列a(abs(a[i])<10^6)が与えられる。a[i], ..., a[j]の区間で最頻値が何度表れるかというQ(<10^5)個のクエリに答える問題。

解法

まず、数列が単調なので連続する同じ数を調べる。例えば、{-1,-1,1,1,1,1,3,10,10,10}は新しい数列x={2,4,1,3} に変換する。そしてxの累積和も持っておく。クエリp,qに対して、p,qに完全に含まれる区間(これを累積和で求める)の最大値はRMQで求める。後は端と比較してやればよい(この処理が一番引っかかった)。引っかかってたテストケースは{0,1,1,1,1,2,3}に対するクエリ3,4とか(答えは2)。
計算量はO((N+Q)*log N)。

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

const int MAX_N = 1<<20;
const int INF = 1<<30;
int dat[2*MAX_N];
int as[MAX_N];
int xs[MAX_N];
int accum[MAX_N];
int RMQ_N, N, Q;

void init2(){
    int cur, prev=INF-1, cnt=1, p=0;
    for(int i=0; i<N-1; i++){
        if(as[i] == as[i+1]){
            cnt++;
        }
        else{
            xs[p++] = cnt;
            cnt = 1;
        }
    }
    xs[p++] = cnt;
    N = p;

    //calc accumulate
    accum[0] = 0;
    for(int i=0; i<N; i++){
        accum[i+1] = accum[i] + xs[i];
    }

    init(N);
    for(int i=0; i<N; i++) update(i, xs[i]);
}

//[from, to] 1-indexed
int proc(int from, int to){
    int a = lower_bound(accum, accum+(N+1), from) - accum;
    int b = (lower_bound(accum, accum+(N+1), to) - accum) - 1;
    if(a==b+1) return to - from + 1;
    int aa = accum[a] - from + 1;
    int bb = to - accum[b];
    int ret = max(aa, bb);
    ret = max(ret, query(a, b, 0, 0, RMQ_N));
    return ret;
}

int main(){
    while(scanf("%d",&N), N){
        scanf("%d",&Q);
        for(int i=0; i<N; i++) scanf("%d",as+i);
        init2();
        for(int i=0; i<Q; i++){
            int from, to;
            scanf("%d%d",&from, &to);
            printf("%d\n",proc(from,to));
        }
    }
    return 0;
}