をあ ぷろぶれむ [いろはちゃんコンテスト Day1 L]

https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_l

前提知識

• 二分探索
• SparseTable

解説

https://atcoder.jp/contests/iroha2019-day1/submissions/5197060

ソートしてK番目の数がなんであるかという問題なので、いつもの二分探索をやる。
全体ソートでO(log10^18)、評価関数でO(NlogN)なので、計算量が心配だが、
区間orの計算をSparseTableでO(1)にすれば間に合う。
左端を固定したときに区間orは単調増加となるので、
左端を全探索して、その中の二分探索で区間orが基準以上となるポイントを探すことで、
基準以上の区間xorの数を数え上げることができる。
　
SparseTableを使わない方法として、
nxt[i][bit] := i番目の要素以降でbit目が1となる最近の要素
を使って、orが増える境目を探す方が定数倍高速かもしれない。
これはorは片方を伸ばしていくと、高々60回くらいしか値が変化せず、
しかもそれはあるbitが0→1となるポイントであることを利用している。

ll N, K, A[101010];
SparseTable<ll> st;
//---------------------------------------------------------------------------------------------------
bool check(ll x) {
	ll cnt = 0;
	rep(i, 0, N) {
		if (x <= A[i]) {
			cnt += N - i;
			continue;
		}
 
		int ng = i, ok = N;
		while (ng + 1 != ok) {
			int md = (ng + ok) / 2;
			if (x <= st.get(i, md + 1)) ok = md;
			else ng = md;
		}
		cnt += N - ok;
	}
 
	return K <= cnt;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> K;
	rep(i, 0, N) cin >> A[i];
 
	vector<ll> v;
	rep(i, 0, N) v.push_back(A[i]);
	st.init(v);
 
	ll ok = 0, ng = infl;
	while (ok + 1 != ng) {
		ll md = (ng + ok) / 2;
		if (check(md)) ok = md;
		else ng = md;
	}
	cout << ok << endl;
}