UVa 11235 Problem F: Frequent values

問題概要

http://uva.onlinejudge.org/external/112/11235.html
非増加列が与えられる。
範囲を指定するクエリが与えられる。
その範囲のなかの最頻値の頻度を答えよ。

解法

セグメントツリー＋分割統治

ノードは

• 自分の範囲のなかでの最頻値の頻度
• 一番右の値が連続する数
• 一番右の値
• 一番左の値が連続する数
• 一番左の値

を持てばよい。

二つの領域をマージするとき、

• どちらか一方の最頻値
• 両方の領域にまたがり、連続する数字

が、最頻値になり得るので、上記の情報を持つ必要がある。

初めてのセグメントツリー。
あまり、スマートに書けなかった気がする。

ソース

簡潔化前　下に簡潔化後

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>
#include<bitset>
#include<cstring>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)

using namespace std;
const double EPS = 0.00000001;
const int INF = 100000000;
typedef long long lli;
const int N = (1 << 17);

int t[N];
int n;
class Data{
public:
  int rCnt, rNum, lCnt, lNum, maxCnt;
  Data(){
  }
  Data init(){
    rCnt = rNum = lCnt = lNum = maxCnt = 1;
    return *this;
  }
  Data zero(){
    rCnt = rNum = lCnt = lNum = maxCnt = -INF;
    return *this;
  }
  bool operator<(const Data &d)const{
    if(lNum != d.lNum) return lNum < d.lNum;
    return rNum < d.rNum;
  }
};

Data unite(Data d1, Data d2){
  Data d;
  d.lNum = d1.lNum;
  d.rNum = d2.rNum;
  d.rCnt = d2.rCnt;
  d.lCnt = d1.lCnt;
  d.maxCnt = max(d1.maxCnt, d2.maxCnt);
  if(d1.rNum == d2.lNum){
    d.maxCnt = max(d.maxCnt, d1.rCnt + d2.lCnt);
    if(d1.lNum == d1.rNum)d.lCnt = max(d.lCnt, d1.rCnt + d2.lCnt);
    if(d2.rNum == d2.lNum)d.rCnt = max(d.rCnt, d1.rCnt + d2.lCnt);
  }
  return d;
}

vector<Data> RES;


class Tree{
public:
  Data d[2*N];
  int R;
  Tree(){
  }
  Tree(int n){
    int e = 1;
    while(n >= e){
      e *= 2;
    }
    R = e;
    assert(e < 2*N);
    set(0, e-1, 1);
  }
  void set(int b, int e, int id){
    if(b >= n){
      d[id] =  Data().zero();
      return;
    }
    if(b == e){
      d[id] = Data().init();
      d[id].rNum = d[id].lNum = t[b];
      return;
    }
    int rid, lid, rb, re, lb, le;
    rid = id * 2 + 1;
    lid = id * 2;
    lb = b;
    le = b + (e - b+1)/ 2 - 1;
    rb = b + (e - b+1)/2;
    assert((e - b+1)%2 == 0);
    re = e;
    set(lb, le, lid);
    set(rb, re, rid);
    d[id] = unite(d[lid], d[rid]);
  }
  int query_init(int b, int e){
    RES.clear();
    query(b, e, 0, R-1, 1);
    sort(ALL(RES));
    rep(i, RES.size() -1){
      RES[i+1] = unite(RES[i], RES[i+1]);
     }
     return RES.back().maxCnt;
   }
  void query(int b, int e, int tb, int te, int id){
    if( b <= tb && e >= te){
      RES.push_back(d[id]);
      return;
    }
    int nid = id * 2 + 1;
    int ntb = tb + (te-tb+1)/2;
    int nte = te;
    if( b <= nte && ntb <= e){
      query(b, e, ntb, nte, nid);
    }
    nid = id * 2;
    ntb = tb;
    nte = tb + (te-tb + 1)/2 - 1;
    if( ntb <= e  && nte >= b){
      query(b, e, ntb, nte, nid);
    }
  }
};

int main(){
  while(cin >> n){
    if(n == 0)break;
    int q;
    cin >> q;
    rep(i, n)cin>> t[i];
    Tree t(n);
    rep(i, q){
      int b, e;
      cin >> b >> e;
      RES.clear();
      cout << t.query_init(b-1, e-1) << endl;
    }
  }
  return 0;
}

あまりに、あれなので、少し簡潔にしてみる。

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>
#include<bitset>
#include<cstring>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)

using namespace std;
const double EPS = 0.00000001;
const int INF = 100000000;
typedef long long lli;
const int N = (1 << 17);

int t[N];
int n;
class Data{
public:
  int rCnt, rNum, lCnt, lNum, maxCnt;
};

Data unite(Data d1, Data d2){
  Data d;
  d.lNum = d1.lNum;
  d.rNum = d2.rNum;
  d.rCnt = d2.rCnt;
  d.lCnt = d1.lCnt;
  d.maxCnt = max(d1.maxCnt, d2.maxCnt);
  if(d1.rNum == d2.lNum){
    d.maxCnt = max(d.maxCnt, d1.rCnt + d2.lCnt);
    if(d1.lNum == d1.rNum)d.lCnt = max(d.lCnt, d1.rCnt + d2.lCnt);
    if(d2.rNum == d2.lNum)d.rCnt = max(d.rCnt, d1.rCnt + d2.lCnt);
  }
  return d;
}

class Tree{
public:
  Data d[2*N];
  int V;
  Tree(int n){
    int e = 1;
    while(n >= e){
      e *= 2;
    }
    V = e;
    set(0, e, 1);
  }
  Data set(int b, int e, int id){
    if(b >= n){
      d[id] = (Data){0, 0, 0, 0, 0};
      return d[id];
    }
    if(b == e-1){
      d[id] = (Data){1, t[b], 1, t[b], 1};
      return d[id];
    }
    Data L = set(b, (e+b)/2, 2*id );
    Data R =set((e+b)/2, e, 2*id + 1);
    d[id] = unite(d[2*id], d[2*id+1]);
    return d[id];
  }
  int query_init(int b, int e){
    return query(b, e, 0, V, 1).maxCnt;
  }
  Data query(int b, int e, int tb, int te, int id){
    if(te <= b || e <= tb)return (Data){0, 0, 0, 0, 0};
    if( b <= tb && e >= te){
      return d[id];
    }
    Data L = query(b, e, tb, (tb+te)/2, id*2);
    Data R = query(b, e, (tb+te)/2, te, id*2+1);
    return unite(L, R);
  }
};

int main(){
  while(cin >> n){
    if(n == 0)break;
    int q;
    cin >> q;
    rep(i, n)cin>> t[i];
    Tree t(n);
    rep(i, q){
      int b, e;
      cin >> b >> e;
      cout << t.query_init(b-1, e) << endl;
    }
  }
  return 0;
}

このくらいに最初から書きたいものです。
プログラミングで、範囲を指定する時、下限はinclusiveで上限はそうではないのは
実装上、簡単だから、ということに気づいた。
ほかのものを実装するときもそうしたいと思う。