Lexicographically Minimal String Rotation (Booth's Algorithm)

概要

何となく理解したので自分用のメモ
文字列 s を cyclic に回転させた時の辞書順最小の文字列を求める問題をO(n)で解く
呼び方が色々ありそうだけど Wikipedia の Lexicographically Minimal String Rotation (以下 LMSR) を採用する

LMSR は Suffix Array でも求められそうだけどこっちのほうが効率いいだろうし文字列アルゴリズムの勉強ということで

コード

int LMSR(const string &s) {
  string S = s + s;
  int N = S.size();
  vector<int> f(N, -1);
  int k = 0;
  for (int j=1; j<N; ++j) {
    int i = f[j-k-1];
    while(i!=-1 && S[j]!=S[k+i+1]) {
      if (S[j]<S[k+i+1])
        k = j-i-1;
      i=f[i];
    }
    if (S[j]!=S[k+i+1]) {
      if (S[j]<S[k+i+1]) k = j;
      f[j-k] = -1;
    } else {
      f[j-k] = i + 1;
    }
  }
  return k;
}

解説

表記
  • s = 入力文字列
  • s[i:j] = s[i] s[i+1] ... s[j]
  • n = |s|
  • S = s + s
  • N = |S|
  • 文字列の prefix と suffix はその文字列自身を含まない
  • 「辞書順最小な suffix」における辞書順最小は,通常の辞書順最小と異なり文字列 A が文字列 B の suffix である場合 A > B とする

- すなわち aa における辞書順最小な suffix は a ではなく aa である
- (できたら呼び方変えたい)

j = j のループが終わったあとの各変数の意味
  • k = S[:j] において辞書順最小なsuffix
  • i = S[k:j] のprefixとsuffixが最大何文字一致しているか
  • f[a] = S[k:k+a-1] においてprefixとsuffixが最大何文字一致しているか(failure link)

通常の KMP に k が加わったという感じになる

j のループが全て終わったあと
  • k < n

- すぐ示せる

  • S[k:k+n-1] が s のLMSR

- l < n, l != k のとき S[k:k+n-1] < S[l:l+n-1] を示せれば良い
- s[k:] < s[l:] を使って場合分けすれば示せる

AtCoderList

AtCoderで自分がどの問題を解いたか確認しようと思うと,
コンテストページに行って自分の提出を見ないといけないので非常に面倒です.
そこで,AtCoderのコンテストから自分の提出を自動的に収集して各問題を解いたかどうか確認するためのプログラムを作りました.
GitHubで公開しています.
GitHub - sune2/AtCoderList

ついでに,拙作AtCoder Colorもよろしくお願いします.
AtCoder Color - Chrome ウェブストア
これは,問題一覧のページを提出状況に応じて色付けするためのChrome拡張です.

yukicoder No.78 クジ付きアイスバー

解法

1箱目と最後の箱はシミュレーションし,間の箱はまとめて処理する.
間の箱をまとめて処理するため,以下の事実を使う.
まず,

  • n = 1箱に入っているアイスバーの数
  • s = 1箱に入っている当たりの数の和(2本当たりなら2加算される)

とする.
このとき,

  • n < s なら,2箱目以降の箱でアイスバーを新しく買う必要はない.
  • n >= s なら,間の箱を1箱分買うために,n - s 個アイスバーを新しく買えば良い.
証明

1箱目の箱を全て「買った」か「当たりとして貰った」後に,
「買った数」と「当たりとして残っている数」をそれぞれ,x, y とする.
例えば,"2100"なら,(x,y)=(1,0),"0021"なら,(x,y)=(3,2)である.
このとき,

  • x + s = 「買った数」+「1箱の当たりの数の和」 = 手に入れた(手に入れる予定の)アイスバーの数
  • n + y = 「1箱のアイスバーの数」+「当たりとして残っている数」 = 手に入れた(手に入れる予定の)アイスバーの数

であることから,
x + s = n + y
が成り立つ.
n < s のとき
1箱目,すなわち,前の箱からの当たりの繰り越しが0なとき,x 回アイスバーを買う必要があった.
2箱目では,当たりの繰り越しが y である.
y - x = s - n > 0 から,y > x であることより,
1箱目で買う必要があった x 回のタイミング全てで,繰り越し分 y を利用する事ができる.
よって,2箱目で新たにアイスバーを買う必要がない.
3箱目における2箱目からの繰り越し分は y よりも大きくなるので,3箱目以降も同様にアイスバーを買う必要がない.
n >= s のとき
このとき, y < x となることから,
2箱目において,1箱目で買う必要があったタイミング全てで,繰り越し分 y を利用する事はできない.
しかし,x 回のうち,y 回分は利用できる.
よって,
x - y = n - s
回だけアイスバーを新たに買えば良い.
3箱目における2箱目からの繰り越し分は y のままであるから,3箱目以降も n - s 回アイスバーを新たに買うことになる.

ソースコード

テンプレ略

int n,k;
string s;

int solve() {
  int sum = 0;
  FOR(it, s) sum += *it - '0';
  int x = 0, y = 0;
  REP(i,n) {
    if (i >= k) return x;
    if (y == 0) {
      x++;
    } else {
      y--;
    }
    y += s[i]-'0';
  }
  k -= n;
  if (n < sum) return x;
  x += (k / n) * (n - sum);
  k %= n;
  REP(i,k) {
    if (y == 0) {
      x++;
    } else {
      y--;
    }
    y += s[i]-'0';
  }
  return x;
}

int main() {
  while(cin >> n >> k) {
    cin >> s;
    cout << solve() << endl;
  }
}

KUPC2014

7月5日にKUPC2014がありました.
僕は第一回のKUPC2011にはコンテスタントとして参加して(参加記d:id:sune2:20110807:1312714641),
その後の2012,2013には運営側として携わりました.
今年は運営の取りまとめ役として携わり,思い入れも強いので記事を書こうと思います.

準備

準備は3月くらいから始めました.
結構余裕があったはずですがやっぱり直前は忙しかったです.

本番

今年も京都と東京の2つのオンサイト会場を用意しました.
ATNDによると京都が36人,東京が50人(満員)の参加があり,大盛況となりました.
昨年は京都19人,東京22人だったようなので,かなり増えたことになります.
AtCoderでの参加者も300人超えで,早めに宣伝したことや,競技者人口が増加した?こと等によるのかなあと思います.

問題

全問についてコメントをします.

A. マッサージチェア

京大の情報学研究科の人たちがよくいる総合研究7号館にはマッサージチェアがあります(使ったことない).
どうもそれが壊れているらしくて,それをネタにしたA問題を作ると言っていたのですが,できた問題では壊れていませんでした.

B. 数当てゲーム

B相当の問題がなくて,リアクティブもDarkroomの1問しかなかったので簡単なリアクティブを目指して作ったのがこれです.
KUPCは色々な言語で参加してくれる方々がいますが,例を書いたC/C++以外の言語での解答でflushを忘れてTLEになっているものがそこそこあって,申し訳ない気持ちになりました.

C. 占い

元々は等号制約がなくて,N,M<=10^18でした.
この場合(僕はわかりませんでしたが)N+M-gcd(N,M)が答えになるのですが,それだけだと寂しいという事で
等号制約をつけてこのポジションに落ち着きました.

D. ハミング

ハミング距離といえば0-0,0-1,1-0,1-1をカウントしてどうにかするというのが主流でこれもそういうものです.
割と好きな問題です.

E. 何しちゃおっかな?

普通2x4しか思いつかないですよね….
タイリングというものをもっと知ってみたいなーと思いました.

F. テレパシー

割と普通の木DP?
最初自分が使ったINFが小さくてやられました.
Tの辺を自分で決められるという問題は解けるのでしょうか.

G. Darkroom

元々の想定解法はウロボロスの蛇(http://poj.org/problem?id=1392) を使う解法で,
これを愚直に使うと2logN回くらい,頑張って使うと2loglogN回くらいになるというものでした.
この問題がクエリ数4回で解けるというのはなかなか衝撃的です.

H. 自転車走

自分で作ったからか,結構簡単だと思っていたのですが,想像以上に解かれなくて驚きました.
結構WAやTLEが多く,AC率も悪かったようです.
適当に嘘解法っぽいものを信じて投げたら通ります.

I. Rain

最小費用流をする前にあらかじめ小さいグラフを構築する必要があると思ったのですがそんなことありませんでした.
ライブラリ以外のコード量は殆ど無いです.

J. カード

dp[i][j] = i 日目までに j 枚カードを持っているときの 所持ポイントのMAX
が全く思いつかなかったです.
実は,昇順にポイントを使うことにすると,毎日Pポイント貰うという制約がはずれるので,
dp[i][j] = i 日目までに j 枚カードを持っているときに必要なポイントのMIN
というDPを使って解くこともできます(解説はこれ).

K. 弱点

初め見た時,すぐにSA,LCPはわかったのですが,最大長方形をとって中に何種類の文字列に起因する接尾辞が入っているのかを調べるパートで少しつまりました.
Mを文字列の長さの合計とすると,setをマージしていく方法でO(M log^2 M)なのですが,実はNが大きければLCPをそんなに大きくできないことから,適当でも通ってしまったりします.
Wavelet何とかを使うと区間内のdistinctな値の数が効率的に求められるようですが知りません.

L. べき乗数

少し解説の補足をします.
まず,xがyより非常に大きいならo^..^o^x > o^..^o^yが,各oに2,3,5,7の何を入れても成り立つ,というのが大事です(oの数は両辺一緒).
L以上のべき乗数をp1^...^pm^xと表した時,その大小関係は
(m, x, pm, … , p1)
の辞書順によって決まると言っています.
まずmですが,これは2^LがHより非常に大きいことによります.
2^LがHより非常に大きいことにより,例えば,2^2^2^2^L > 7^7^7^H が成り立ちます.
これより,x,pm,...,p1がなんであろうと,mが大きい方が大きいということが言えるのです.
次にxですが,これはxがそれぞれ非常に異なるので,その後の列がなんであろうとやっぱりそれらも非常に異なることになります.
pmが入ったあとも,pm^xはそれぞれ非常に異なるので同様のことが言え,以下同様となります.

このような辞書順の比較に帰着したかったので,あのような性質を持つLとHを見つける訳ですね.
ちなみにLとHはべき乗数を小さいものから順にヒープを使って生成していくと見つけることができます.

難しいです….

まとめ

難易度調整がうまくいったか不安ですが,全ての問題が解かれ全完が出ないという基準は達成されたのでよかったです.
参加して頂いた皆さんありがとうございました.

Convex Hull Trick

概要

問題 : 「多数の f_i(x) = a_i * x + b_i と,多数のクエリ x に対し min f_i(x) を求めよ.」


この問題を解くためにConvex Hull Trickというものがある.
蟻本において,K-anonymous Sequenceという問題の解法として紹介されている(Convex Hull Trickという名前は出てきていない).
蟻本で紹介されているパターンには以下の条件がある.

  • 追加される直線の係数が単調減少
  • クエリが単調増加

この記事では,これらの条件が無いパターンの解き方とその実装を紹介する.
http://wcipeg.com/wiki/Convex_hull_trickアルゴリズムの説明はあるので英語を読むのが苦でない人はこれを見たほうがいい.

注意:蟻本のパターンに比べて条件がない場合は log N 分計算量が悪くなる.

クエリが単調増加でない場合

蟻本パターンと同様に適当に直線を管理する.
クエリに対しては二分探索する.
おわり.

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

struct CHT {
  vector<pii> deq;              // first * x + second
  int s,t;
  CHT(int n) {                  // n : クエリ数
    deq.resize(n);
    s=0, t=0;
  }
  void add(int a, int b) {      // a : 単調減少
    const pii p(a,b);
    while(s+1<t && check(deq[t-2],deq[t-1],p)) t--;
    deq[t++] = p;
  }
  int incl_query(int x) {            // x : 単調増加
    while(s+1<t && f(deq[s], x) >= f(deq[s+1], x)) s++;
    return f(deq[s], x);
  }
  int query(int x) {           // 条件なし
    int low = s-1, high = t-1;
    while(low+1<high) {
      int mid = low+high>>1;
      if (isright(deq[mid], deq[mid+1], x)) low = mid;
      else high = mid;
    }
    return f(deq[high], x);
  }
private:
  bool isright(const pii &p1, const pii &p2, int x) {
    return (p1.second-p2.second) >= x * (p2.first-p1.first);
  }
  bool check(const pii &p1, const pii &p2, const pii &p3) {
    return (p2.first-p1.first)*(p3.second-p2.second) >=
      (p2.second-p1.second)*(p3.first-p2.first);
  }
  int f(const pii &p, int x) {
    return p.first * x + p.second;
  }
};
int main() {
  CHT cht(3);
  cht.add(2,3);
  cht.add(-1,4);
  cout << cht.query(1) << endl; // 3
}

直線の係数が単調減少でない場合

直線の追加
係数が単調減少の場合,直線は後ろに追加すると決まっていたので嬉しかった.
そうでない場合,追加する場所を二分探索木(Sとする)で探す.
Sは係数をキーとする.

Sに直線を追加したとき,その左右の直線が不要になれば,不要な分だけ削除する.

クエリ
Sにおけるどの直線がクエリに対して最小を達成するかを探すために,別の二分探索木(Cとする)を用意する.
Cにおけるキーは,Sにおいて隣接する直線の交点とする.

実装のコメント

  • 簡潔にするため,番兵となる直線を追加した.
  • doubleにしてもいいけど,全部整数型で扱うようにした.
  • イテレータを(+1,-1)動かす関数を用意した.
  • a,bの条件は |ab| < LLONG_MAX/4 くらいだと思うけどよく分からない.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = LLONG_MAX;

struct CHT2 {  
  CHT2() {
    // 番兵
    S.insert({L(INF,0), L(-INF,0)});
    C.insert(cp(L(INF,0),L(-INF,0)));
  }
  // for debug
  void print() {
    cout << "S : "; for (auto it : S) printf("(%lld,%lld)", it.a, it.b); puts("");
    cout << "C : "; for (auto it : C) printf("(%lld,%lld)", it.n, it.d); puts("");
  }
  // |ab| < LLONG_MAX/4 ???
  void add(ll a, ll b) {
    const L p(a,b);
    It pos = S.insert(p).first;
    if (check(*it_m1(pos), p, *it_p1(pos))) {
      // 直線(a,b)が不要
      S.erase(pos);
      return;
    }
    C.erase(cp(*it_m1(pos), *it_p1(pos)));
    {
      // 右方向の削除
      It it = it_m1(pos);
      while(it!=S.begin() && check(*it_m1(it), *it, p)) --it;
      C_erase(it, it_m1(pos));
      S.erase(++it,pos);
      pos = S.find(p);
    }
    {
      // 左方向の削除
      It it = it_p1(pos);
      while(it_p1(it)!=S.end() && check(p,*it, *it_p1(it))) ++it;
      C_erase(++pos, it);
      S.erase(pos, it);
      pos = S.find(p);
    }
    C.insert(cp(*it_m1(pos), *pos));
    C.insert(cp(*pos, *it_p1(pos)));
  }
  ll query(ll x) {
    const L &p = (--C.lower_bound(CP(x,1,L(0,0))))->p;
    return p.a*x + p.b;
  }
  
private:
  
  template<class T> T it_p1(T a) { return ++a; }
  template<class T> T it_m1(T a) { return --a; }  
  struct L {
    ll a, b;
    L(ll a, ll b) : a(a),b(b) {}
    bool operator<(const L &rhs) const {
      return a != rhs.a ? a > rhs.a : b < rhs.b;
    }
  };
  struct CP {
    ll n,d;
    L p;
    CP(ll _n, ll _d, const L &p) : n(_n),d(_d),p(p) {
      if (d < 0) { n *= -1; d *= -1; }
    };
    bool operator<(const CP &rhs) const {
      if (n == INF || rhs.n == -INF) return 0;
      if (n == -INF || rhs.n == INF) return 1;      
      return n * rhs.d < rhs.n * d;
    }
  };
  set<L> S;
  set<CP> C;

  typedef set<L>::iterator It;
  
  void C_erase(It a, It b) {
    for (It it=a; it!=b; ++it)
      C.erase(cp(*it, *it_p1(it)));
  }
  CP cp(const L &p1, const L &p2) {
    if (p1.a == INF) return CP(-INF,1,p2);
    if (p2.a == -INF) return CP(INF,1,p2);
    return CP(p1.b-p2.b, p2.a-p1.a, p2);
  }
  bool check(const L &p1, const L &p2, const L &p3) {
    if (p1.a==p2.a && p1.b <= p2.b) return 1;
    if (p1.a == INF || p3.a == -INF) return 0;
    return (p2.a-p1.a)*(p3.b-p2.b) >= (p2.b-p1.b)*(p3.a-p2.a);
  }
};

int main() {
  CHT2 cht;
  cht.add(2,2);
  cht.add(-1,4);
  cht.add(3,4);
  cout << cht.query(-1) << endl; // 0
  cht.print();
}

バグってたり,実装を改善できそうだったり,条件がない場合を使う必要のある問題があったりしたら教えてください.

Technology Campの感想とサポートページ

Technology Camp

去年の9月にインターンとしてサイバーエージェント社によるTechnology Campに参加した。
Technology Campは休日含め10日間で1つのアプリを仕上げる。
開発は2人チームで行うが、何を作るかは完全にこちらに任されるので、企画から行う必要がある。
元々アクションゲームが作りたいという欲があったので、相方には半ば強引にアクションゲームを作ることにしてもらった。
それまでアクションゲームを作ったことがなく、どうやって作ればいいか分からないところからのスタートだったが、試行錯誤の末なんとか形にすることができた。
最後に審査があって、1~3位と特別賞が決められる。
自分たちの作品は同立3位に選ばれて、やっぱり結果が得られたのは嬉しかった。
ところで、副賞の豪華ランチは・・・

GO!GO! Samurai BOY!

そのTechnology Campで作ったのが「GO!GO! Samurai BOY!」。
侍のゲームにすることになったのは偶然だったが、意外と最後までうまくいった。
画像やBGMなどの素材はフリーなものをネットから引っ張ってきた。
エンジニアだけでアプリを作るときはイラストやデザインの問題が非常に厄介で、
デザイナー様の大切さが(別のインターンでもそう感じたこともあり)身にしみて分かった。


ちなみに公開までに要した時間は、

  • 何を作るかの決定、cocos2d/box2dの勉強(5日位)
  • Technology Camp(10日)
  • ブラッシュアップ、公開(5日+審査)

Objective-CによるiPhoneアプリ開発はこれを作る前に少しやったことがあった。

今後

おそらくやらないけど、

  • Twitter,Facebook連携の英語の文言を用意する
  • 溜め攻撃の実装
  • 別ステージの実装
  • チャレンジモードとしてゴールのないステージの実装
  • Android版の開発

アプリページ

是非プレイしてみてください。感想待ってます。
https://itunes.apple.com/jp/app/go!go!-samurai-boy!/id790211983?mt=8

区間のk-th smallestが求められる謎データ構造

この記事は
Competitive Programming Advent Calendar Div2013(http://partake.in/events/3a3bb090-1390-4b2a-b38b-4273bea4cc83)
の16日目の記事です。


データ構造の話です。


地区予選の過去問を解いているときに、以下のような問題を見つけました。

【問題】
素数Nの数列a(a[0],...,a[N-1])が与えられる。
以下の2種類からなるクエリがQ個与えられるので、それぞれ処理せよ。
・Query1 l r k
 a[l],...,a[r-1]のk番目に小さい数は何か (1<=k<=r-l)
・Query2 l r x
 a[l],...,a[r-1]をソートしたとき、xは何番目か (x∈{a[l], ..., a[r]})
【制約】
N<=10^5
Q<=10^5
0<=l

僕は解き方がわからなかったのですが、中国のサイトを漁っていたらこの問題を解くデータ構造を見つけました。
ということでそのデータ構造を紹介しようと思います。
そのデータ構造の名前はよくわからなかったので,今回は謎データ構造と呼ぶことにします.


この記事では,Query1について詳しく説明します.
Query2についてもQuery1と同じような考えを用いて求めることができます.
詳しくは最後に載せたソースコードをご覧ください.

例えば、aを

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]
6 12 5 17 10 2 7 3

とします。
いま,
Query1 2 7 3
が与えられたとします.
まず,[2,7)以外の部分はいらないので,わかりやすくするために値を消しておきます.

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]
5 17 10 2 7

続いて,[2,7)をソートします.

a[0] a[1] a'[2] a'[3] a'[4] a'[5] a'[6] a[7]
2 5 7 10 17

ソートされた[2,7)の中で,3番目にある7が,このクエリに対する答えとなります.
ソートを全てのクエリに対して毎回行うと,O(QN log N)となり間に合いません.

イデア

謎データ構造のアイデアは,求める値がどこにあるかを,二分探索のように狭めていくことです.
今,
[L,R)の中で[l,r)に注目しており,この中でk番目の値を探している
とします.
先程の例では,
[0,8)の中で[2,7)に注目しており,この中で3番目の値を探している
となります.
謎データ構造では,[L,R)をどんどん半分にしていくことで,探索の範囲を狭めていき,1クエリに対しO(log N)で答えを出します.
ここで必要となるのが,

  1. M=(L+R)/2としたとき,[L,M)を見るべきか,[M,R)を見るべきか
  2. 次のl,r,kはどうなるか

という処理です.
1.を行うため,[l,r)内でk番目の値が左半分にあるか右半分にあるかを高速に判断する必要があります.
この処理を元の数列のまま行うのは無理なので,次の段階に移るとき,[L,R)のうち,値の大きさが下半分になるものを[L,M),上半分になるものを[M,R)に動かします.
ただし,[L,M),[M,R)内ではもとの順番は保つようにします.


例示をわかりやすくするため,ここで,
b[i][j] = 段階iでの列におけるj番目の値
とします.
先程の例を用いると,段階0では

b[0][0] b[0][1] b[0][2] b[0][3] b[0][4] b[0][5] b[0][6] b[0][7]
6 12 5 17 10 2 7 3

となり,段階1では

b[1][0] b[1][1] b[1][2] b[1][3] b[1][4] b[1][5] b[1][6] b[1][7]
6 5 2 3 12 17 10 7

となります.
全体を図示したものが以下です.

最後のb[3]は元の列をソートしたものになります.
ここでさらに,
left[i][j] = 段階iにおけるj番目の値が所属するブロックにおいて,次の段階で左にいったものの数のjまでの累積和
を導入します.
leftを図に追加すると以下になります.

ここで,
[0,8)の中で[2,7)に注目しており,この中で3番目の値を探している
とき,次に[0,4)を見るべきか,[4,8)を見るべきかという問題に戻ります.
left[0][7-1]-left[0][2-1]=2より,[2,7)から左のブロックに進んだものは2個あることがわかります.
今3番目の値を探しているので,次に見るべきは左のブロックではなく,右のブロックであることがわかります.
「次のl,r,kはどうなるか」という問題も,leftを利用することで求まります.
この場合は,l=5,r=8,k=1となります.

以下[L,R)がだた1つの要素に対応するようになるまで繰り返すことで,Query1の答えを得ることができます.

bとleftの計算はO(N log N)で可能なので,O(N log N)の前処理をすることで,各Query1に対してO(log N)で求められるデータ構造を作ることができました.

ソースコード

今回の記事で扱った問題は,a[i]が互いに異なることを想定していましたが,その条件がなくても問題ありません.
以下の実装では,(一部自信がないですが)値が同じa[i]があっても動くようになっているはずです.

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10000;

struct KthSmallest {
  struct Seg {
    int l, r, mid;
    void set(int _l, int _r) {
      l = _l; r = _r;
      mid = l+r>>1;
    }
  } seg[N<<2];
  int b[25][N], left[25][N], sorted[N];
  void init(int *a, int n) {
    for (int i=0; i<n; ++i) b[0][i] = sorted[i] = a[i];
    sort(sorted, sorted+n);
    build(0,n,0,1);
  }
  void build(int l, int r, int d, int idx) {
    seg[idx].set(l,r);
    if (l+1 == r) return;
    int mid = seg[idx].mid;
    int lsame = mid - l;
    for (int i=l; i<r; ++i)
      if (b[d][i] < sorted[mid])
        lsame--;
    int lpos = l, rpos = mid, same = 0;

    for (int i=l; i<r; ++i) {
      left[d][i] = (i!=l ? left[d][i-1] : 0);
      if (b[d][i] < sorted[mid]) {
        left[d][i]++;
        b[d+1][lpos++] = b[d][i];
      } else if (b[d][i] > sorted[mid]) {
        b[d+1][rpos++] = b[d][i];
      } else {
        if (same < lsame) {
          same++;
          left[d][i]++;
          b[d+1][lpos++] = b[d][i];
        } else {
          b[d+1][rpos++] = b[d][i];
        }
      }
    }
    build(l,mid,d+1,idx<<1);
    build(mid,r,d+1,idx<<1|1);
  }
  /*
    [l,r)をソートしたときk番目に来る値は何か
   */
  int kth(int l, int r, int k, int d=0, int idx=1) { // k : 1-origin!!!
    if (l+1 == r) return b[d][l];
    int ltl = (l!=seg[idx].l ? left[d][l-1] : 0);
    int tl = left[d][r-1] - ltl;

    if (tl >= k) {
      int newl = seg[idx].l + ltl;
      int newr = seg[idx].l + ltl + tl;
      return kth(newl,newr,k,d+1,idx<<1);
    } else {
      int mid = seg[idx].mid;
      int tr = r - l - tl;
      int ltr = l - seg[idx].l - ltl;
      int newl = mid + ltr;
      int newr = mid + ltr + tr;
      return kth(newl,newr,k-tl,d+1,idx<<1|1);
    }
  }
  /*
    [l,r)をソートしたときxは何番目に来るか.
    xが2つ以上あるときは,最後のもののrankを返す.
    xがないときはx未満で最大なもののrankを返す.
    x未満がないときは0を返す.
  */ 
  int rank(int l, int r, int x, int d=0, int idx=1) {
    if (seg[idx].l+1 == seg[idx].r) {
      return l+1==r&&sorted[l]<=x;
    }
    int ltl = (l!=seg[idx].l ? left[d][l-1] : 0);
    int tl = left[d][r-1] - ltl;
    int mid = seg[idx].mid;
    if (x < sorted[mid]) {
      int newl = seg[idx].l + ltl;
      int newr = seg[idx].l + ltl + tl;
      return rank(newl,newr,x,d+1,idx<<1);
    } else {
      int tr = r - l - tl;
      int ltr = l - seg[idx].l - ltl;
      int newl = mid + ltr;
      int newr = mid + ltr + tr;
      return tl + rank(newl,newr,x,d+1,idx<<1|1);
    }
  }
  /*
    [l,r)にxは何個あるか
  */ 
  int freq(int l, int r, int x) {
    return rank(l,r,x)-rank(l,r,x-1);
  }
} kth;

int main() {
  int a[8] = {6,12,5,17,10,2,7,3};
  kth.init(a, 8);
  cout << kth.kth(2,7,3) << endl; // 7
  cout << kth.rank(2,7,7) << endl; // 3
}   

verify:
(地区予選問題のネタバレ注意)https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=393&page=show_problem&problem=3035
ただし,同じ値が含まれない場合のみ

まとめ

本記事では,区間のkth-smallestを求められる謎データ構造を紹介しました.
このデータ構造の名前を知っていたり,「これ,○○で出来るよ!」みたいなのがあったりしたら是非教えて下さい.