PKU3368 Frequent values

問題概要

a[] = { a₁, a₂, a₃, ... , a_n } の増加部分列が与えられる。
a[i,j]の区間の最頻値が何度現れるかというクエリQ個(Q ≦ 10⁵個)に答えよ。

解法

見た感じセグ木で解けそうな問題。
それぞれの数字の出現回数を求めて、ノードに最大値と合計の情報を持たせたセグ木に入れる。
合計の情報は累積和でやっても同じ。
クエリに対しては、合計の情報より二分探索で左端と右端を求めてRangeMaximumQuery。
左端と右端は微妙に被るので、例外処理する。
これで計算量はO((さんきゅー + N) log N) くらいになる。

ソース

#include<bits/stdc++.h>
using namespace std;
typedef pair< int, int > Pi;

struct SegmentTree {
  int sz;
  vector< int > data, big;
  SegmentTree(int n) {
    sz = 1;
    while(sz < n) sz *= 2;
    data.assign(2 * sz + 1, 0);
    big.assign(2 * sz + 1, 0);
  }
  Pi Lower_Bound_Lower(int k, int x) { // 上の節目からどれだけ離れているか
    if(k >= sz - 1) return(make_pair(k - sz + 1, data[k] - x));
    if(data[2 * k + 1] >= x) return(Lower_Bound_Lower(2 * k + 1, x));
    return(Lower_Bound_Lower(2 * k + 2, x - data[2 * k + 1]));
  }
  int RangeMaximumQuery(int a, int b, int k, int l, int r) {
    if(a >= r || b <= l) return(0);
    if(a <= l && r <= b) return(big[k]);
    return(max(RangeMaximumQuery(a, b, 2 * k + 1, l, (l + r) >> 1), RangeMaximumQuery(a, b, 2 * k + 2, (l + r) >> 1, r)));
  }
  int Query(int a, int b) { // [a,b)
    Pi Left = Lower_Bound_Lower(0, a), Right = Lower_Bound_Lower(0, b);
    int l = data[sz - 1 + Left.first] - Left.second - 1, r = Right.second;
    if(Left.first == Right.first) return(data[sz - 1 + Left.first] - r - l);
    int hasiL = data[sz - 1 + Left.first] - l;
    int hasiR = data[sz - 1 + Right.first] - r;
    return(max(max(hasiL, hasiR),RangeMaximumQuery(Left.first + 1, Right.first, 0, 0, sz)));
  }
  void Update(int k, int x) {
    k += sz - 1;
    data[k] += x;
    big[k] = data[k];
    while(k > 0) {
      k = (k - 1) >> 1;
      data[k] = data[2 * k + 1] + data[2 * k + 2];
      big[k] = max(big[2 * k + 1], big[2 * k + 2]);
    }
  }
};


int main() {
  int n, q, digit[100000];
  while(scanf("%d", &n), n){
    SegmentTree seg(200002);
    scanf("%d", &q);
    for(int i = 0; i < n; i++) {
      scanf("%d", &digit[i]); digit[i] += 100000;
    }
    int cnt = 1;
    for(int i = 1; i < n; i++) {
      if(digit[i - 1] != digit[i]) {
        seg.Update(digit[i - 1], cnt); cnt = 1;
      } else {
        ++cnt;
      }
    }
    seg.Update(digit[n - 1], cnt);
    
    for(int i = 0; i < q; i++) {
      int a, b;
      scanf("%d %d", &a, &b);
      printf("%d\n", seg.Query(a, b));
    }
  }
}