UVA 11235 - Frequent Values

/*
PROBLEMA: UVa 11235 - Frequent Values

Salio usando Range Maximum Query con Segment Tree. La idea es la siguiente:

Hacemos un array count[i] que cuenta cuantos elementos hay iguales al i-esimo elemento sin considerar repetidos.
Despues hacemos el acumulado (inclusive) ac[i] = suma(count[i..j]).

Hacemos el segment tree del arreglo count.

Supongamos que nos hacen la query i,j

Con busqueda binaria obtenemos l y r tales que ac[l] <= i y ac[r] <= j. Si l == r entonces es fácil porque a[i] = a[j] y entonces es la cantidad de elementos que hay en el medio. Sino, lo que hacemos es usar el set de segment tree para corregir los valores de count[l] y de count[r] a la cantidad de elementos entre ac[l] e i y entre ac[r] y j. Eso lo puedo hacer en O(log n) por la magia de segment tree. Despues es hacer el range maximum query común y silvestre.

O sea que nos queda O(n + q log n)

*/

#include <iostream>
#include <cstdio>
#include <climits>
#include <cstring>
using namespace std;
typedef pair<int,int> pii;
#define forn(i,n) for(int i=0;i<(int)(n);i++)
#define forsn(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

const int MAXN=100100;
int n,q,a[MAXN];
int S,count[MAXN],ac[MAXN];
int rmq[4*MAXN], R;

//Segment Tree
void initTree(){
    R = 1 << (32-__builtin_clz(S));
    forsn(i,R,2*R) rmq[i] = 0;
    forn(i,R) rmq[R+i] = count[i];
    for(int i = R-1; i >= 0; i--)
        rmq[i] = max(rmq[2*i],rmq[2*i+1]);
}
void set(int i, int v){
    rmq[i+=R] = v;
    for(int p = i/2; p != 0; p = p/2){
        rmq[p] = max(rmq[2*p],rmq[2*p+1]);
    }
}
int _get(int i, int j){
    int res = 0;
    if(j-i <= 0) return res;
    if(i % 2) res = max(res,rmq[i++]);
    res = max(res, _get(i/2,j/2));
    if(j % 2) res = max(res,rmq[--j]);
    return res;
}
int get(int i, int j){ return _get(i+R, j+R); }
//Fin Segment Tree

void init(){
    int b = INT_MIN; S = 0;
    forn(i,n){
        if(a[i] == b){
            count[S-1]++;
        }else{
            b = a[i]; count[S++] = 1;
        }
    }
    ac[0] = count[0];
    forn(i,S) ac[i] = ac[i-1] + count[i-1];

    initTree();
}
int bsearch(int v){
    int l = 0, r = S;
    while(r-l>1){
        int m = (r+l)/2;
        if(ac[m] <= v) l = m; else r = m;
    }
    return l;
}
int query(int left, int right){
    int l = bsearch(left), r = bsearch(right);
    if(l == r) return right-left;
    int oril = -1, orir = -1;
    if(left - ac[l] > 0){
        oril = count[l];
        set(l,count[l]-left+ac[l]);
    }
    if(ac[r] + count[r] - right > 0){
        orir = count[r];
        set(r,right-ac[r]);
    }

    int res = get(l,r+1);

    if(oril >= 0) set(l,oril);
    if(orir >= 0) set(r,orir);
    return res;
}
int main(){
    #ifdef JUAMPI
        freopen("11235.in","r",stdin);
    #endif

    while(scanf("%d",&n) == 1 && n > 0){
        scanf("%d",&q);

        forn(i,n) scanf("%d",&a[i]);
        init();

        forn(i,q){
            int l,r; scanf("%d %d",&l,&r);
            l--;
            printf("%d\n",query(l,r));
        }
    }

    return 0;
}