POJ K-th Numberを通すまでに苦労したこと～領域木(l,rの範囲にx以下の値は何個あるか)～

Quiz
- http://poj.org/problem?id=2104

POJ一般

auto使えない
using使えない
include bits使えない

苦労したこと

問題文の読み間違い。Aは負値もある
cinではなくscanfを使わないとTLE（問題文に書いてある）
scanfで読み込み先がintかlong longかで指定を変える必要（変えないと変な値が入る）
- %dか、%lld
Time Limitが厳しいので、二分探索するにも-inf～infでは間に合わないので、ありうる値のみを探索する
- ありうる値のsort済み配列を用意して左右から範囲を絞り込んでいく
平方分割のサイズを適切にしないと通らない
- バケットサイズB=900でAC, 800や1000だとTLE
- （平方分割は計算量的に厳しいことを体感した）
long longだと通らない
- Aの配列の型としてlong longを使っていたが、これだとB=900でも通らない。intに書き換えるとAC
- 入力がボトルネックでそこのメモリサイズが2倍になる

その他

includeを削っても意味がない
- bitsが使えないので全部展開したが不要なのも多いので削ったが改善には貢献しなかった
配列のコピーはTLEの成否を分ける程ではない
- 構造体のメンバ変数としてコピーしてもACした
coutをprintfにするのは効果なし（クエリが5000個なのでボトルネックではない）
- とはいえscanfを使い始めるとcinを同居させたくなくなる（同居は可能）↓

// 同居するならコメントアウトしておこう
// cin.tie(0);
// ios::sync_with_stdio(false);

適切なバケットサイズ

f:id:peroon:20210107024510p:plain

計算量

配列の長さ N=100000
バケットサイズ B=900
クエリ数 Q=5000
.
1回のcountを呼ぶのにN/B x log2(B) = 1090
N=100000を二分探索するのでlog2(N)=16.6
全体として、1090 x 16.6 x 5000 = 90470000 = 10⁸ = ギリギリ
全体計算量を記号で書くと
- O(N/B x log2(B) x log2(N) x Q)

ライブラリ領域木

これを作りたかったのだがPOJの落とし穴やTLでかなり時間がかかった

// 蟻本p170
struct RangeTree{
  static const int B = 900;
  static const int MAXN = 110010;
  VI A; // 入力そのもの
  vector<VI> bucket;
  ll N;
  RangeTree(VI _A){
    A = _A;
    N=SZ(A);
    bucket.resize(MAXN/B);
    rep(i,N){
      bucket[i/B].push_back(A[i]);
    }
    rep(i,MAXN/B){
      SORT(bucket[i]);
    }
  }
 
  // [l,r)にて、x以下の数は何個あるか
  // 計算量O(N)
  ll count_naive(ll l, ll r, ll x){
    // naive
    ll cnt=0;
    FOR(i,l,r){
      if(A[i]<=x)cnt++;
    }
    return cnt;
  }
  // [l,r)にて、x以下の数は何個あるか
  // 計算量 O(min(B, N/B * log(B))) ... NをBで分割してそれぞれ二分探索するので
  // 
  ll count(ll l, ll r, ll x){
    ll cnt=0;
    // バケットをはみ出す部分
    while(l<r && l%B!=0){
      if(A[l]<=x)cnt++;
      l++;
    }
    while(l<r && r%B!=0){
      if(A[r-1]<=x)cnt++;
      r--;
    }
    // バケットごと
    while(l<r){
      ll b = l/B;
      ll num = upper_bound(ALL(bucket[b]), x) - bucket[b].begin();
      cnt += num;
      l += B;
    }
    return cnt;
  }
};

AC (自分用) 他人からは見えない

sample (AC) http://poj.org/showsource?solution_id=22251916
二分探索をより自然に使ったもの(TLE) http://poj.org/showsource?solution_id=22251918

all code (AC)

#ifdef LOCAL
    // #define _GLIBCXX_DEBUG
    #define __clock__
#else
    #pragma GCC optimize("Ofast")
#endif
#include <algorithm>
#include <bitset>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <numeric>
#include <ostream>
#include <stdexcept>
#include <streambuf>

#include <vector>
using namespace std;

// typedef long long ll; // これだとTLE
typedef int ll;
typedef vector<ll> VI;

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,b) FOR(i, 0, b)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<'\n'
#define p2(s, t) cout << (s) << " " << (t) << '\n'
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << '\n'
#define SZ(x) ((int)(x).size())
#define SORT(A) sort(ALL(A))
#define RSORT(A) sort(ALL(A), greater<ll>())

const ll mod = 1e9 + 7;
// const ll mod = 998244353;
// const ll inf = 1e18;
const ll inf = 1e9+10;

// 蟻本p170
struct RangeTree{
  static const int B = 900;
  static const int MAXN = 110010;
  VI A; // 入力そのもの
  vector<VI> bucket;
  ll N;
  RangeTree(VI _A){
    A = _A;
    N=SZ(A);
    bucket.resize(MAXN/B);
    rep(i,N){
      bucket[i/B].push_back(A[i]);
    }
    rep(i,MAXN/B){
      SORT(bucket[i]);
    }
  }
 
  // [l,r)にて、x以下の数は何個あるか
  // 計算量O(N)
  ll count_naive(ll l, ll r, ll x){
    // naive
    ll cnt=0;
    FOR(i,l,r){
      if(A[i]<=x)cnt++;
    }
    return cnt;
  }
  // [l,r)にて、x以下の数は何個あるか
  // 計算量 O(min(B, N/B * log(B))) ... NをBで分割してそれぞれ二分探索するので
  // 
  ll count(ll l, ll r, ll x){
    ll cnt=0;
    // バケットをはみ出す部分
    while(l<r && l%B!=0){
      if(A[l]<=x)cnt++;
      l++;
    }
    while(l<r && r%B!=0){
      if(A[r-1]<=x)cnt++;
      r--;
    }
    // バケットごと
    while(l<r){
      ll b = l/B;
      ll num = upper_bound(ALL(bucket[b]), x) - bucket[b].begin();
      cnt += num;
      l += B;
    }
    return cnt;
  }
};

int main(){
    // scanfを使うので切っておく
    // cin.tie(0);
    // ios::sync_with_stdio(false);

    // input
    ll N,Q;
    cin>>N>>Q;
    VI A(N);
    rep(i, N){
      scanf("%d",&A[i]); // intを受け取る時
      // scanf("%lld",&A[i]); // long longを受け取る時
    }

    VI so = A;
    SORT(so);

    RangeTree tree(A);

    while(Q--){
      ll l,r,k;
      cin>>l>>r>>k;
      l--;r--;

      // 本当はこれで解ければいいのだがTLがきつい・・・
      // xを二分探索
      // ll left=-inf; // can't (k個未満)
      // ll right=inf; // can (k個以上を達成)
      // while(left+1!=right){
      //   ll center = (left+right)/2;
      //   ll num = tree.count(l,r+1,center);
      //   if(num<k){
      //     left=center;
      //   }else{
      //     right=center;
      //   }
      // }
      // p(right);

      ll left = -1; // can't
      ll right=N-1; // can
      while(left+1!=right){
        ll center = (left+right)/2;
        ll v = so[center];
        ll num = tree.count(l,r+1,v);
        if(num<k){
          left=center;
        }else{
          right=center;
        }
        if(left+1==right)break;
      }
      ll ans = so[right];
      p(ans);
    }
    
    return 0;
}

POJ一般

苦労したこと

その他

適切なバケットサイズ

計算量

ライブラリ 領域木

AC (自分用) 他人からは見えない

all code (AC)

ライブラリ領域木