#line 1 "test/aoj_DPL_1_D.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D"
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <vector>
#line 1 "DataStructure/dynamic_bitvector.cpp"
/**
* @brief 動的ビットベクトル
* @author えびちゃん
*/
#include <cstddef>
#include <climits>
#include <array>
#include <memory>
#line 1 "utility/literals.cpp"
/**
* @brief ユーザ定義リテラル
* @author えびちゃん
*/
#line 10 "utility/literals.cpp"
#include <cstdint>
constexpr intmax_t operator ""_jd(unsigned long long n) { return n; }
constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; }
constexpr size_t operator ""_zu(unsigned long long n) { return n; }
constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; }
constexpr int8_t operator ""_i8(unsigned long long n) { return n; }
constexpr int16_t operator ""_i16(unsigned long long n) { return n; }
constexpr int32_t operator ""_i32(unsigned long long n) { return n; }
constexpr int64_t operator ""_i64(unsigned long long n) { return n; }
constexpr uint8_t operator ""_u8(unsigned long long n) { return n; }
constexpr uint16_t operator ""_u16(unsigned long long n) { return n; }
constexpr uint32_t operator ""_u32(unsigned long long n) { return n; }
constexpr uint64_t operator ""_u64(unsigned long long n) { return n; }
#line 1 "integer/bit.cpp"
/**
* @brief ビット演算
* @author えびちゃん
*/
// XXX integral promotion 関連の注意をあまりしていません
#line 12 "integer/bit.cpp"
#include <type_traits>
template <typename Tp>
constexpr auto countl_zero(Tp n)
-> typename std::enable_if<std::is_unsigned<Tp>::value, int>::type
{
using value_type = typename std::make_unsigned<Tp>::type;
int bits = (sizeof(value_type) * CHAR_BIT);
if (n == 0) return bits;
int res = 0;
for (int i = bits / 2; i > 0; i /= 2) {
value_type mask = ((static_cast<value_type>(1) << i) - 1) << i;
if (n & mask) n >>= i;
else res += i;
}
return res;
}
template <typename Tp>
constexpr auto countl_one(Tp n)
-> typename std::enable_if<std::is_unsigned<Tp>::value, int>::type
{
using value_type = typename std::make_unsigned<Tp>::type;
return countl_zero(static_cast<value_type>(~n));
}
template <typename Tp>
constexpr auto countr_zero(Tp n)
-> typename std::enable_if<std::is_unsigned<Tp>::value, int>::type
{
using value_type = typename std::make_unsigned<Tp>::type;
int bits = (sizeof(value_type) * CHAR_BIT);
if (n == 0) return bits;
int res = 0;
for (int i = bits / 2; i > 0; i /= 2) {
value_type mask = ((static_cast<value_type>(1) << i) - 1);
if (!(n & mask)) res += i, n >>= i;
}
return res;
}
template <typename Tp>
constexpr auto countr_one(Tp n)
-> typename std::enable_if<std::is_unsigned<Tp>::value, int>::type
{
using value_type = typename std::make_unsigned<Tp>::type;
return countr_zero(static_cast<value_type>(~n));
}
constexpr unsigned long long half_mask[] = {
0x5555555555555555uLL, 0x3333333333333333uLL, 0x0F0F0F0F0F0F0F0FuLL,
0x00FF00FF00FF00FFuLL, 0x0000FFFF0000FFFFuLL, 0x00000000FFFFFFFFuLL
};
template <typename Tp>
constexpr auto popcount(Tp n)
-> typename std::enable_if<std::is_unsigned<Tp>::value, int>::type
{
int bits = static_cast<int>((sizeof n) * CHAR_BIT);
for (int i = 0, j = 1; j < bits; ++i, j *= 2) {
if (j <= 8) n = (n & half_mask[i]) + ((n >> j) & half_mask[i]);
else n += n >> j;
}
return n & 0xFF;
}
template <typename Tp>
constexpr auto parity(Tp n)
-> typename std::enable_if<std::is_unsigned<Tp>::value, int>::type
{ return popcount(n) & 1; }
template <typename Tp>
int clz(Tp n) { return countl_zero(static_cast<typename std::make_unsigned<Tp>::type>(n)); }
template <typename Tp>
int ctz(Tp n) { return countr_zero(static_cast<typename std::make_unsigned<Tp>::type>(n)); }
template <typename Tp>
int ilog2(Tp n) {
return (CHAR_BIT * sizeof(Tp) - 1) - clz(static_cast<typename std::make_unsigned<Tp>::type>(n));
}
template <typename Tp>
bool is_pow2(Tp n) { return (n > 0) && ((n & (n-1)) == 0); }
template <typename Tp>
Tp floor2(Tp n) { return is_pow2(n)? n: static_cast<Tp>(1) << ilog2(n); }
template <typename Tp>
Tp ceil2(Tp n) { return is_pow2(n)? n: static_cast<Tp>(2) << ilog2(n); }
template <typename Tp>
constexpr auto reverse(Tp n)
-> typename std::enable_if<std::is_unsigned<Tp>::value, Tp>::type
{
int bits = static_cast<int>((sizeof n) * CHAR_BIT);
for (int i = 0, j = 1; j < bits; ++i, j *= 2) {
n = ((n & half_mask[i]) << j) | ((n >> j) & half_mask[i]);
}
return n;
}
#line 16 "DataStructure/dynamic_bitvector.cpp"
class dynamic_bitvector {
public:
using size_type = size_t;
private:
using underlying_type = uintmax_t;
static constexpr size_type S_ws = (CHAR_BIT * sizeof(underlying_type));
static constexpr size_type S_ws_2 = S_ws / 2;
static constexpr size_type S_ws_4 = S_ws / 4;
// なんか splay tree を書く
struct node {
using size_type = size_t;
using underlying_type = uintmax_t;
using pointer = node*; // たぶんすまーとぽいんたに変える
underlying_type M_value = 0;
size_type M_size = 0;
size_type M_count = 0;
size_type M_self_size = 0;
size_type M_self_count = 0;
pointer M_parent = nullptr;
std::array<pointer, 2> M_children{{nullptr, nullptr}};
node() = default;
node(underlying_type value, size_type size):
M_value(value), M_self_size(size), M_self_count(popcount(value)) {}
};
using pointer = node*; // たぶんすまーとぽいんたに変える
static size_type S_child_dir(pointer v, pointer p) {
return ((p->M_children[0] == v)? 0: 1);
}
static void S_reduce(pointer v) {
v->M_size = v->M_self_size;
v->M_count = v->M_self_count;
for (pointer c: v->M_children) {
if (!c) continue;
v->M_size += c->M_size;
v->M_count += c->M_count;
}
}
static void S_insert_mini(pointer v, size_type i, bool x) {
underlying_type lo = v->M_value & ((1_ju << i) - 1);
underlying_type hi = (v->M_value ^ lo) << 1;
v->M_value = lo | hi;
++v->M_self_size, ++v->M_size;
if (x) {
v->M_value |= 1_ju << i;
++v->M_self_count, ++v->M_count;
}
}
static void S_erase_mini(pointer v, size_type i) {
underlying_type lo = v->M_value & ((1_ju << i) - 1);
v->M_value ^= lo;
if (v->M_value >> i & 1) {
v->M_value ^= 1_ju << i;
--v->M_self_count, --v->M_count;
}
v->M_value >>= 1;
v->M_value |= lo;
--v->M_self_size, --v->M_size;
}
static void S_split_evenly(pointer lop, pointer hip) {
size_type lo_size = (lop->M_self_size + hip->M_self_size) / 2;
size_type hi_size = (lop->M_self_size + hip->M_self_size) - lo_size;
// lop->M_value | (hip->M_value << lop->M_self_size)
underlying_type lo, hi;
if (lop->M_self_size > lo_size) {
lo = lop->M_value & ((1_ju << lo_size) - 1);
hi = (lop->M_value >> lo_size) | (hip->M_value << (lop->M_self_size - lo_size));
} else {
lo = lop->M_value | ((hip->M_value << lop->M_self_size) & ((1_ju << lo_size) - 1));
hi = hip->M_value >> (lo_size - lop->M_self_size);
}
lop->M_value = lo;
lop->M_self_size = lo_size;
lop->M_self_count = popcount(lo);
hip->M_value = hi;
hip->M_self_size = hi_size;
hip->M_self_count = popcount(hi);
S_reduce(lop), S_reduce(hip);
}
static size_type S_select_mini(underlying_type x, size_type i) {
if (i == 0) return 0;
// TODO: speed up to O(log(ws)) time
for (size_t j = 0; j < S_ws; ++j) {
if (x >> j & 1) --i;
if (i == 0) return j+1;
}
return -1; // unreachable?
}
static void S_inspect_dfs(pointer v) {
if (!v) return;
printf("%p [%p:%p:%p] %jx (%zu, %zu)\n",
v, v->M_children[0], v->M_children[1], v->M_parent,
v->M_value, v->M_self_size, v->M_size);
S_inspect_dfs(v->M_children[0]);
S_inspect_dfs(v->M_children[1]);
}
static void S_zig(pointer v, pointer p, size_type d) {
v->M_parent = nullptr;
p->M_children[d] = v->M_children[!d];
v->M_children[!d] = p;
if (p->M_children[d]) p->M_children[d]->M_parent = p;
p->M_parent = v;
S_reduce(p);
S_reduce(v);
}
static void S_zigzig(pointer v, pointer p, pointer g, size_type d) {
v->M_parent = g->M_parent;
if (g->M_parent) g->M_parent->M_children[S_child_dir(g, g->M_parent)] = v;
g->M_children[d] = p->M_children[!d];
p->M_children[d] = v->M_children[!d];
p->M_children[!d] = g;
v->M_children[!d] = p;
if (g->M_children[d]) g->M_children[d]->M_parent = g;
if (p->M_children[d]) p->M_children[d]->M_parent = p;
g->M_parent = p;
p->M_parent = v;
S_reduce(g);
S_reduce(p);
S_reduce(v);
}
static void S_zigzag(pointer v, pointer p, pointer g, size_type d) {
v->M_parent = g->M_parent;
if (g->M_parent) g->M_parent->M_children[S_child_dir(g, g->M_parent)] = v;
p->M_children[d] = v->M_children[!d];
g->M_children[!d] = v->M_children[d];
v->M_children[d] = g;
v->M_children[!d] = p;
if (g->M_children[!d]) g->M_children[!d]->M_parent = g;
if (p->M_children[d]) p->M_children[d]->M_parent = p;
g->M_parent = p->M_parent = v;
S_reduce(g);
S_reduce(p);
S_reduce(v);
}
static void S_splay(pointer v) {
while (v->M_parent) {
pointer p = v->M_parent;
size_type pd = S_child_dir(v, p);
if (!p->M_parent) {
S_zig(v, p, pd);
continue;
}
pointer g = p->M_parent;
size_type gd = S_child_dir(p, g);
if (pd == gd) {
S_zigzig(v, p, g, pd);
} else {
S_zigzag(v, p, g, pd);
}
}
}
void M_splay(pointer v) {
S_splay(v);
M_root = v;
}
size_type M_nth_bit(size_type n) {
pointer v = M_root;
// inspect();
// fprintf(stderr, "M_nth_bit(%zu): ", n);
while (v->M_children[0] || v->M_children[1]) {
size_type left = (v->M_children[0]? v->M_children[0]->M_size: 0);
if (n < left) {
v = v->M_children[0];
} else if (n >= left + v->M_self_size) {
if (!v->M_children[1]) break; // for past-the-end one
n -= left + v->M_self_size;
v = v->M_children[1];
} else {
break;
}
}
// fprintf(stderr, "v: %p\n", v);
if (v->M_children[0])
n -= v->M_children[0]->M_size;
M_splay(v);
// fprintf(stderr, "%zu\n", n);
return n;
}
pointer M_root = nullptr;
public:
dynamic_bitvector() = default;
dynamic_bitvector(dynamic_bitvector const&); // XXX deep copy
dynamic_bitvector& operator =(dynamic_bitvector const&); // XXX deep copy
void insert(size_type i, bool x) {
if (!M_root) {
underlying_type y = (x? 1: 0);
M_root = new node(y, 1);
S_reduce(M_root);
return;
}
size_type j = M_nth_bit(i);
S_insert_mini(M_root, j, x);
if (M_root->M_self_size < S_ws) return;
// まずねー、split する。
pointer latter = M_root->M_children[1];
M_root->M_children[1] = nullptr;
if (latter) latter->M_parent = nullptr;
// 次にねー、word を二つに分けて、新しくできた word を追加する。
underlying_type lo = M_root->M_value & ((1_ju << S_ws_2) - 1);
underlying_type hi = M_root->M_value >> S_ws_2;
M_root->M_value = lo;
M_root->M_self_size = S_ws_2;
M_root->M_self_count = popcount(lo);
pointer inserted = new node(hi, S_ws_2);
// 最後に merge しておわりー。
inserted->M_children[1] = latter;
if (latter) latter->M_parent = inserted;
M_root->M_children[1] = inserted;
inserted->M_parent = M_root;
S_reduce(inserted);
S_reduce(M_root);
}
void erase(size_type i) {
size_type j = M_nth_bit(i);
S_erase_mini(M_root, j);
if (M_root->M_self_size > S_ws_4) return;
pointer left = M_root->M_children[0];
pointer right = M_root->M_children[1];
if (!left && !right && M_root->M_self_size == 0) {
delete M_root;
M_root = nullptr;
return;
}
M_root->M_children[0] = M_root->M_children[1] = nullptr;
S_reduce(M_root);
if (left) {
left->M_parent = nullptr;
while (left->M_children[1]) left = left->M_children[1];
S_splay(left);
}
if (right) {
right->M_parent = nullptr;
while (right->M_children[0]) right = right->M_children[0];
S_splay(right);
}
if (left && left->M_self_size + M_root->M_self_size < S_ws) {
// left とくっつける
left->M_value |= M_root->M_value << left->M_self_size;
left->M_self_size += M_root->M_self_size;
left->M_size += M_root->M_self_size;
left->M_self_count += M_root->M_self_count;
left->M_count += M_root->M_self_count;
delete M_root;
M_root = left;
M_root->M_children[1] = right;
if (right) right->M_parent = M_root;
} else if (right && right->M_self_size + M_root->M_self_size < S_ws) {
// right とくっつける
right->M_value <<= M_root->M_self_size;
right->M_value |= M_root->M_value;
right->M_size += M_root->M_self_size;
right->M_self_size += M_root->M_self_size;
right->M_count += M_root->M_self_count;
right->M_self_count += M_root->M_self_count;
delete M_root;
M_root = right;
M_root->M_children[0] = left;
if (left) left->M_parent = M_root;
} else if (left) {
// left->M_value と M_root->M_value を分けっこする
S_split_evenly(left, M_root);
S_reduce(left);
M_root->M_children[0] = left;
M_root->M_children[1] = right;
left->M_parent = M_root;
if (right) right->M_parent = M_root;
} else if (right) {
// right->M_value と M_root->M_value を分けっこする
S_split_evenly(M_root, right);
S_reduce(right);
M_root->M_children[0] = left;
M_root->M_children[1] = right;
if (left) left->M_parent = M_root;
right->M_parent = M_root;
}
S_reduce(M_root);
}
void set(size_type i, bool x = true);
void reset(size_type i);
// rank は簡単で、splay して、自分の count から右の子の count を引いて、
// あとはワードサイズの rank をするとよいはず。逆元あると楽だね。
// select はセグ木上のにぶたんちっくなことをする。
template <int B>
size_type rank(size_type i) {
if (M_root->M_size <= i) {
size_type res = M_root->M_count;
if (B == 0) res = i - res;
return res;
}
size_type j = M_nth_bit(i);
size_type res = popcount(M_root->M_value & ((1_ju << j) - 1));
if (M_root->M_children[0]) res += M_root->M_children[0]->M_count;
if (B == 0) res = i - res;
return res;
}
template <int B>
size_type select(size_type i) {
if (i == 0) return 0;
{
size_type rank = M_root->M_count;
if (B == 0) rank = M_root->M_size - rank;
if (rank < i) return -1;
}
pointer v = M_root;
size_type res = 0;
while (v->M_children[0] || v->M_children[1]) {
size_type left = (v->M_children[0]? v->M_children[0]->M_count: 0);
if (B == 0 && v->M_children[0]) left = v->M_children[0]->M_size - left;
size_type cur = v->M_self_count;
if (B == 0) cur = v->M_self_size - cur;
if (i <= left) {
v = v->M_children[0];
} else if (i > left + cur) {
if (!v->M_children[1]) break;
if (v->M_children[0]) res += v->M_children[0]->M_size;
res += v->M_self_size;
i -= left + cur;
v = v->M_children[1];
} else {
break;
}
}
if (v->M_children[0]) {
size_type left = v->M_children[0]->M_count;
if (B == 0) left = v->M_children[0]->M_size - left;
i -= left;
res += v->M_children[0]->M_size;
}
res += S_select_mini((B? v->M_value: ~v->M_value), i);
M_splay(v);
return res;
}
size_type rank(int x, size_type i) { return (x? rank<1>(i): rank<0>(i)); }
size_type select(int x, size_type i) { return (x? select<1>(i): select<0>(i)); }
size_type rank0(size_type i) { return rank<0>(i); }
size_type rank1(size_type i) { return rank<1>(i); }
size_type select0(size_type i) { return select<0>(i); }
size_type select1(size_type i) { return select<1>(i); }
size_type rank0(size_type s, size_type t) {
if (s == t) return 0;
return rank0(t) - rank0(s);
}
size_type rank1(size_type s, size_type t) {
if (s == t) return 0;
return rank1(t) - rank1(s);
}
bool operator [](size_type i) {
size_type j = M_nth_bit(i);
return M_root->M_value >> j & 1;
}
size_type size() const { return M_root->M_size; }
size_type count() const { return M_root->M_count; }
bool empty() const noexcept { return M_root == nullptr; }
void inspect() const {
S_inspect_dfs(M_root);
}
};
#line 1 "DataStructure/wavelet_matrix.cpp"
/**
* @brief ウェーブレット行列
* @author えびちゃん
*/
#line 13 "DataStructure/wavelet_matrix.cpp"
#line 1 "DataStructure/bit_vector.cpp"
/**
* @brief rank/select 辞書
* @author えびちゃん
*/
#line 13 "DataStructure/bit_vector.cpp"
#line 15 "DataStructure/bit_vector.cpp"
class bit_vector {
public:
using underlying_type = uintmax_t;
using size_type = size_t;
using difference_type = ptrdiff_t;
private:
static const size_type S_ws = CHAR_BIT * sizeof(underlying_type);
std::vector<underlying_type> M_c;
std::vector<size_type> M_r;
std::vector<size_type> M_s0, M_s1;
std::vector<std::vector<size_type>> M_ss0, M_ss1;
static size_type S_popcount(underlying_type n) {
return __builtin_popcountll(n);
}
static underlying_type S_least_n_bits(size_type n) {
return (1_ju << n) - 1;
}
template <int Bp>
static size_type S_rank_small(underlying_type x, size_type n) {
if (Bp == 0) x = ~x;
return S_popcount(x & S_least_n_bits(n));
}
template <int Bp>
static size_type S_select_small(underlying_type x, size_type n) {
if (n == 0) return 0;
size_type lb = 0;
size_type ub = S_ws;
while (ub-lb > 1) {
size_type mid = (lb+ub) >> 1;
((S_rank_small<Bp>(x, mid) < n)? lb: ub) = mid;
}
return ub;
}
template <int Bp>
size_type M_rank_large(size_type n) const {
// if (n == 0) return 0;
size_type res = M_r[n];
if (Bp == 0) res = n * S_ws - res;
return res;
}
template <int Bp>
void M_prepare_select(std::vector<bool> const& bv,
std::vector<size_type>& s,
std::vector<std::vector<size_type>>& ss) {
size_type z = 0;
size_type n = bv.size();
s.push_back(0);
std::vector<size_type> tmp;
for (size_type i = 0; i < n; ++i) {
if (bv[i] != Bp) continue;
tmp.push_back(i);
if (++z == S_ws) {
size_type len = i+1 - s.back();
s.push_back(i+1);
ss.emplace_back();
if (len >= S_ws * S_ws) ss.back() = std::move(tmp);
tmp.clear();
z = 0;
}
}
ss.push_back(std::move(tmp));
}
template <int Bp>
size_type M_select(size_type n,
std::vector<size_type> const& s,
std::vector<std::vector<size_type>> const& ss) const {
if (n-- == 0) return 0;
size_type j0 = n / S_ws;
size_type j1 = n % S_ws;
if (j0 >= s.size()) return -1_zu;
if (j0+1 == s.size() && j1 >= ss[j0].size()) return -1_zu;
if (!ss[j0].empty()) return ss[j0][j1] + 1;
size_type lb = s[j0] / S_ws;
size_type ub = (j0+1 < s.size())? (s[j0+1]+S_ws-1) / S_ws: M_r.size();
while (ub-lb > 1) {
size_type mid = (lb+ub) >> 1;
((M_rank_large<Bp>(mid) <= n)? lb: ub) = mid;
}
return lb * S_ws + S_select_small<Bp>(M_c[lb], n+1 - M_rank_large<Bp>(lb));
}
public:
bit_vector() = default;
bit_vector(bit_vector const&) = default;
bit_vector(bit_vector&&) = default;
template <typename InputIt>
bit_vector(InputIt first, InputIt last) { assign(first, last); }
bit_vector& operator =(bit_vector const&) = default;
bit_vector& operator =(bit_vector&&) = default;
template <typename InputIt>
void assign(InputIt first, InputIt last) {
std::vector<bool> tmp(first, last);
M_c.resize(tmp.size() / S_ws + 1);
for (size_type i = 0; i < tmp.size(); ++i) {
if (!tmp[i]) continue;
size_type j0 = i / S_ws;
size_type j1 = i % S_ws;
M_c[j0] |= 1_ju << j1;
}
// rank
M_r.assign(M_c.size(), 0);
for (size_type i = 1; i < M_c.size(); ++i)
M_r[i] += M_r[i-1] + S_popcount(M_c[i-1]);
// select
M_prepare_select<0>(tmp, M_s0, M_ss0);
M_prepare_select<1>(tmp, M_s1, M_ss1);
}
size_type rank0(size_type t) const {
return t - rank1(t);
}
size_type rank1(size_type t) const {
size_type j0 = t / S_ws;
size_type j1 = t % S_ws;
return M_r[j0] + S_popcount(S_least_n_bits(j1) & M_c[j0]);
}
size_type rank0(size_type s, size_type t) const {
return (t-s) - rank1(s, t);
}
size_type rank1(size_type s, size_type t) const {
if (s == t) return 0;
return rank1(t) - rank1(s);
}
size_type select0(size_type n) const {
return M_select<0>(n, M_s0, M_ss0);
}
size_type select1(size_type n) const {
return M_select<1>(n, M_s1, M_ss1);
}
size_type select0(size_type n, size_type s) const {
n += rank0(0, s);
return M_select<0>(n, M_s0, M_ss0);
}
size_type select1(size_type n, size_type s) const {
n += rank1(0, s);
return M_select<1>(n, M_s1, M_ss1);
}
};
#line 16 "DataStructure/wavelet_matrix.cpp"
template <size_t Nb, typename Tp = uintmax_t, typename Bv = bit_vector>
class wavelet_matrix {
public:
using value_type = Tp;
using size_type = size_t;
using difference_type = ptrdiff_t;
using bitvector_type = Bv;
private:
std::array<bitvector_type, Nb> M_a = {};
std::array<size_type, Nb> M_z = {};
std::vector<value_type> M_c;
enum S_three_way { S_less = 0, S_equal, S_greater };
static const value_type S_fail = -1; // XXX use std::optional?
size_type M_startpos(value_type x) /* const */ {
size_type s = 0;
size_type t = 0;
for (size_type i = Nb; i-- > 1;) {
size_type j = Nb-i-1;
if (x >> i & 1) {
s = M_z[j] + M_a[j].rank1(s);
t = M_z[j] + M_a[j].rank1(t);
} else {
s = M_a[j].rank0(s);
t = M_a[j].rank0(t);
}
}
return s;
}
public:
wavelet_matrix() = default;
template <typename InputIt>
wavelet_matrix(InputIt first, InputIt last) { assign(first, last); }
wavelet_matrix(std::initializer_list<value_type> il):
wavelet_matrix(il.begin(), il.end()) {}
template <typename InputIt>
void assign(InputIt first, InputIt last) {
M_c.assign(first, last);
M_z = {{}};
size_type n = M_c.size();
std::vector<value_type> whole = M_c;
for (size_type i = Nb; i--;) {
std::vector<value_type> zero, one;
std::vector<bool> vb(n);
for (size_type j = 0; j < n; ++j) {
((whole[j] >> i & 1)? one: zero).push_back(whole[j]);
vb[j] = (whole[j] >> i & 1);
}
M_z[Nb-i-1] = zero.size();
M_a[Nb-i-1] = bitvector_type(vb.begin(), vb.end());
if (i == 0) break;
whole = std::move(zero);
whole.insert(whole.end(), one.begin(), one.end());
}
}
size_type rank(value_type x, size_type s, size_type t) /* const */ {
if (s == t) return 0;
for (size_type i = Nb; i--;) {
size_type j = Nb-i-1;
if (x >> i & 1) {
s = M_z[j] + M_a[j].rank1(s);
t = M_z[j] + M_a[j].rank1(t);
} else {
s = M_a[j].rank0(s);
t = M_a[j].rank0(t);
}
}
return t - s;
}
size_type select(value_type x, size_type n) /* const */ {
if (n == 0) return 0;
if (rank(x, 0, M_c.size()) < n) return -1;
size_type si = M_startpos(x);
if (x & 1) {
n += M_a[Nb-1].rank1(si);
n = M_a[Nb-1].select1(n);
} else {
n += M_a[Nb-1].rank0(si);
n = M_a[Nb-1].select0(n);
}
for (size_type i = 1; i < Nb; ++i) {
size_type j = Nb-i-1;
if (x >> i & 1) {
n -= M_z[j];
n = M_a[j].select1(n);
} else {
n = M_a[j].select0(n);
}
}
return n;
}
size_type select(value_type x, size_type n, size_type s) /* const */ {
if (n == 0) return s;
n += rank(x, 0, s);
return select(x, n);
}
std::array<size_type, 3> rank_3way(value_type x,
size_type s, size_type t) /* const */ {
if (s == t) return {0, 0, 0};
size_type lt = 0;
size_type eq = t-s;
size_type gt = 0;
for (size_type i = Nb; i--;) {
size_type j = Nb-i-1;
size_type tmp = t-s;
if (x >> i & 1) {
s = M_z[j] + M_a[j].rank1(s);
t = M_z[j] + M_a[j].rank1(t);
} else {
s = M_a[j].rank0(s);
t = M_a[j].rank0(t);
}
size_type d = tmp - (t-s);
eq -= d;
((x >> i & 1)? lt: gt) += d;
}
return {lt, eq, gt};
}
std::array<size_type, 3> xored_rank_3way(value_type x, value_type y,
size_type s, size_type t) /* const */ {
if (s == t) return {0, 0, 0};
size_type lt = 0;
size_type eq = t-s;
size_type gt = 0;
for (size_type i = Nb; i--;) {
size_type j = Nb-i-1;
size_type tmp = t-s;
if ((x ^ y) >> i & 1) {
s = M_z[j] + M_a[j].rank1(s);
t = M_z[j] + M_a[j].rank1(t);
} else {
s = M_a[j].rank0(s);
t = M_a[j].rank0(t);
}
size_type d = tmp - (t-s);
eq -= d;
((y >> i & 1)? lt: gt) += d;
}
return {lt, eq, gt};
}
value_type quantile(size_type k, size_type s, size_type t) /* const */ {
value_type res = 0;
for (size_type i = Nb; i--;) {
size_type j = Nb-i-1;
size_type z = M_a[j].rank0(s, t);
if (k < z) {
s = M_a[j].rank0(s);
t = M_a[j].rank0(t);
} else {
res |= 1_ju << i;
s = M_z[j] + M_a[j].rank1(s);
t = M_z[j] + M_a[j].rank1(t);
k -= z;
}
}
return res;
}
value_type min_greater(value_type x, size_type s, size_type t) /* const */ {
auto r3 = rank_3way(x, s, t);
size_type k = r3[S_less] + r3[S_equal];
if (k == t-s) return S_fail;
return quantile(k, s, t);
}
value_type min_greater_equal(value_type x, size_type s, size_type t) /* const */ {
auto r3 = rank_3way(x, s, t);
size_type k = r3[S_less];
if (k == t-s) return S_fail;
return quantile(k, s, t);
}
value_type max_less(value_type x, size_type s, size_type t) /* const */ {
auto r3 = rank_3way(x, s, t);
size_type k = r3[S_less];
if (k == 0) return S_fail;
return quantile(k-1, s, t);
}
value_type max_less_equal(value_type x, size_type s, size_type t) /* const */ {
auto r3 = rank_3way(x, s, t);
size_type k = r3[S_less] + r3[S_equal];
if (k == 0) return S_fail;
return quantile(k-1, s, t);
}
size_type select_greater(value_type x, size_type n, size_type s) /* const */ {
if (n == 0) return s;
size_type lb = s;
size_type ub = M_c.size();
while (ub-lb > 1) {
size_type mid = (lb+ub) >> 1;
auto r3 = rank_3way(x, s, mid);
size_type k = r3[S_greater];
((k < n)? lb: ub) = mid;
}
return ub;
}
size_type select_greater_equal(value_type x, size_type n, size_type s) /* const */ {
if (n == 0) return s;
size_type lb = s;
size_type ub = M_c.size();
while (ub-lb > 1) {
size_type mid = (lb+ub) >> 1;
auto r3 = rank_3way(x, s, mid);
size_type k = r3[S_equal] + r3[S_greater];
((k < n)? lb: ub) = mid;
}
return ub;
}
size_type select_less(value_type x, size_type n, size_type s) /* const */ {
if (n == 0) return s;
size_type lb = s;
size_type ub = M_c.size();
while (ub-lb > 1) {
size_type mid = (lb+ub) >> 1;
auto r3 = rank_3way(x, s, mid);
size_type k = r3[S_less];
((k < n)? lb: ub) = mid;
}
return ub;
}
size_type select_less_equal(value_type x, size_type n, size_type s) /* const */ {
if (n == 0) return s;
size_type lb = s;
size_type ub = M_c.size();
while (ub-lb > 1) {
size_type mid = (lb+ub) >> 1;
auto r3 = rank_3way(x, s, mid);
size_type k = r3[S_less] + r3[S_equal];
((k < n)? lb: ub) = mid;
}
return ub;
}
// for dynamic bitvectors only
void insert(size_type t, value_type x) {
size_type s = 0;
for (size_type i = Nb; i--;) {
size_type j = Nb-i-1;
M_a[j].insert(s+t, x >> i & 1);
if (x >> i & 1) {
t = M_a[j].rank(1, s+t+1) - 1;
s = M_z[j];
} else {
t = M_a[j].rank(0, s+t+1) - 1;
s = 0;
++M_z[j];
}
}
}
void erase(size_type t) {
size_type s = 0;
for (size_type i = Nb; i--;) {
size_type j = Nb-i-1;
size_type u = s+t;
if (M_a[j][u]) {
t = M_a[j].rank(1, u+1) - 1;
s = M_z[j];
} else {
t = M_a[j].rank(0, u+1) - 1;
s = 0;
--M_z[j];
}
M_a[j].erase(u);
}
}
void set(size_type t, value_type x) {
erase(t);
insert(t, x);
}
value_type operator [](size_type s) /* const */ {
return quantile(0, s, s+1);
}
};
#line 10 "test/aoj_DPL_1_D.test.cpp"
int main() {
size_t n;
scanf("%zu", &n);
std::vector<size_t> a(n);
for (auto& ai: a) scanf("%zu", &ai);
wavelet_matrix<17, uintmax_t, dynamic_bitvector> wm;
for (size_t i = 0; i < n; ++i) wm.insert(i, 0);
std::vector<size_t> p(n);
std::iota(p.begin(), p.end(), 0);
std::sort(p.begin(), p.end(), [&](size_t i, size_t j) {
if (a[i] != a[j]) return a[i] < a[j];
return j < i;
});
for (size_t i = 0; i < n; ++i) {
size_t j = p[i];
auto cur = ((j > 0)? wm.quantile(j-1, 0, j): 0) + 1;
wm.set(j, cur);
}
printf("%ju\n", wm.quantile(n-1, 0, n));
}
test/aoj_DPL_1_D.test.cpp