PKU 3368 Frequent values

http://poj.org/problem?id=3368
ソートされた数列が与えられる。
範囲iからjで最も出現回数の多い数字の出現個数を求めろというような問題。

レンジクエリー(というのでしょうか？これもRMQ?)。
ある範囲の中で、その左端から連続する数列の個数と値
右端から連続する数列の個数と値
真ん中で連続する数が最大の個数と値
を処理していく感じで実装しました。

まずinsert関数、query関数を書くのに大分時間がかかり、TLEと戦うのにも大分時間がかかりました。
結局merge関数を出来るだけ早くして何とか通しました。

char input[18167830];
int pos;
char c;
int gret;
int getnum(){
  while(!isdigit(c=input[pos++]))
    if(c=='-')return -getnum();
  gret=c&15;
  while(isdigit(c=input[pos++]))gret=(gret<<3)+(gret<<1)+(c&15);
  return gret;
}


typedef struct{
  int rs[3];
  int re[3];
  int v[3];
}node;

int n_,n;
node arr[1000000];
node empty;

void pr(const node& in){
  rep(i,3){
    cout<<' '<<in.rs[i]<<' '<<in.re[i]<<' '<<in.v[i]<<endl;
  }
}

node merge(const node& le,const node& ri){
  if(le.re[0]==0)return ri;
  if(ri.re[0]==0)return le;

  node ret(le);
  rep(i,3){
    if(ret.v[0]==ri.v[i])ret.re[0]=max(ret.re[0],ri.re[i]);
  }
  if(ret.v[2]!=ri.v[2]){
    ret.rs[2]=ri.rs[2];
    ret.re[2]=ri.re[2];
    ret.v[2]=ri.v[2];
  }else ret.re[2]=ri.re[2];

  if(ret.re[1]-ret.rs[1]<ri.re[1]-ri.rs[1]){
    ret.re[1]=ri.re[1];
    ret.rs[1]=ri.rs[1];
    ret.v[1]=ri.v[1];
  }

  if(ret.re[1]-ret.rs[1]<ret.re[2]-ret.rs[2]){
    ret.re[1]=ret.re[2];
    ret.rs[1]=ret.rs[2];
    ret.v[1]=ret.v[2];
  }
  if(le.v[2]==ri.v[0] &&
     ret.re[1]-ret.rs[1]<ri.re[0]-le.rs[2]){
    ret.rs[1]=le.rs[2];
    ret.re[1]=ri.re[0];
    ret.v[1]=le.v[2];
  }
  return ret;
}

void insert(int pos,int x){
  node v;
  
  rep(i,3){
    v.rs[i]=pos;
    v.re[i]=pos+1;
    v.v[i]=x;
  }
  
  pos+=n_;
  arr[pos]=v;
  
  do{
    pos=(pos-1)/2;
    v=arr[pos]=merge(arr[pos],v);
  }while(pos);
}

node query(int qs,int qe,int as,int ae,int k){
  if(ae<=qs || qe<=as)return empty;
  if(qs<=as && ae<=qe)return arr[k];
  return merge(query(qs,qe,as,(as+ae)/2,k*2+1),query(qs,qe,(as+ae)/2,ae,k*2+2));
}

int nmax(const node &in){
  int ret(in.re[2]-in.rs[2]);
  rep(i,2){
    ret=max(ret,in.re[i]-in.rs[i]);
  }
  return ret;
}

void solve(){
  int q(getnum());
  n_=1;
  while(n_<n)n_<<=1;
  --n_;
  memset(arr,0,sizeof(arr));
  rep(i,n){
    insert(i,getnum());
  }
  
  rep(i,q){
    int s(getnum());
    int e(getnum());
    printf("%d\n",nmax(query(s-1,e,0,n_+1,0)));
  }
}

main(){
  fread(input,sizeof(input),1,stdin);
  while(n=getnum())solve();
}