POI 21 Stage 1 Couriers ( Persistent Segment Tree )

http://main.edu.pl/en/archive/oi/21/kur

題意：
給一個長度 N 的數列，接著 M 筆詢問 [ L, R ] 中是否有個數字是絕對多數，有的話輸出該數字。

資料規模：
N, M ≤ 5e5
1 ≤ P ≤ N
TL: 12000 ms
ML: 128 MB

解法：
一個持久化裸題，但記憶體卡得比較緊，要用離散化線段樹避免開展過多不必要的節點。
另外這題有基於拆散位元的思想的二分解法。

時間 / 空間複雜度：
O( N lg N + M lg N ) / O( N lg^2 N )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 5e5;

int N, M;

struct pst{
  static pst mem_pool[ ( int ) 1.05e7 ];
  int cnt;
  pst *lc, *rc;
  pst(){
    cnt = 0;
    lc = rc = NULL;
  }
  void pull(){
    cnt = ( lc ? lc->cnt : 0 ) + ( rc ? rc->cnt : 0 );
  }
} *root[ MAXN + 1 ], pst::mem_pool[ ( int ) 1.05e7 ], *mem_ptr = pst::mem_pool;

pst* clone( pst *t ){
  pst *res = new ( mem_ptr++ ) pst();
  res->lc = t->lc;
  res->rc = t->rc;
  res->cnt = t->cnt;
  return res;
}

pst* update( pst *t, int lb, int rb, int k, int v ){
  pst *res;
  if( t ) res = clone( t );
  else res = new ( mem_ptr++ ) pst();
  if( lb + 1 == rb ){
    res->cnt += v;
    return res;
  }
  int mid = lb + rb >> 1;
  if( k < mid ) res->lc = update( res->lc, lb, mid, k, v );
  else res->rc = update( res->rc, mid, rb, k, v );
  res->pull();
  return res;
}

int dfs( pst *tl, pst *tr, int lb, int rb, int v ){
  if( lb + 1 == rb ){
    return lb;
  }
  int mid = lb + rb >> 1;
  int rl = tr ? tr->lc ? tr->lc->cnt : 0 : 0;
  int ll = tl ? tl->lc ? tl->lc->cnt : 0 : 0;
  int rr = tr ? tr->rc ? tr->rc->cnt : 0 : 0;
  int lr = tl ? tl->rc ? tl->rc->cnt : 0 : 0;
  if( rl - ll << 1 > v ){
    return dfs( ( tl ? tl->lc : NULL ), ( tr ? tr->lc : NULL ), lb, mid, v );
  }
  if( rr - lr << 1 > v ){
    return dfs( ( tl ? tl->rc : NULL ), ( tr ? tr->rc : NULL ), mid, rb, v );
  }
  return -1;
}

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  for( int i = 0; i < N; ++i ){
    int P; cin >> P; --P;
    root[ i + 1 ] = update( root[ i ], 0, N, P, 1 );
  }
  for( int i = 0; i < M; ++i ){
    int ql, qr; cin >> ql >> qr; --ql; // [ ql, qr )
    cout << dfs( root[ ql ], root[ qr ], 0, N, qr - ql ) + 1 << "\n";
  }
  return 0;
}