This documentation is automatically generated by online-judge-tools/verification-helper
#include "ds/sortable_array.hpp"// Source: https://github.com/maspypy/library/blob/main/ds/sortable_array.hpp
#include "ds/fastset.hpp"
#include "ds/node_pool.hpp"
// int 列を扱う. key の重複可.
struct Sortable_Array {
const int N, KEY_MAX;
struct Node {
int size;
Node *l, *r;
};
Node_Pool<Node> pool;
using np = Node*;
FastSet ss; // 区間の左端全体を表す fastset
vector<np> root; // 区間の左端に、dynamic segtree の node を乗せる
vector<bool> rev;
Sortable_Array(int NODES, int KEY_MAX, vector<int> key)
: N(key.size()), KEY_MAX(KEY_MAX), ss(key.size()) {
init(key);
}
void set(int i, int key) {
assert(0 <= key && key < KEY_MAX);
split_at(i), split_at(i + 1);
rev[i] = 0, root[i] = new_node(0);
set_rec(root[i], 0, KEY_MAX, key);
}
void sort_inc(int l, int r) {
if (l == r) return;
split_at(l), split_at(r);
while (1) {
np c = root[l];
int i = ss.next(l + 1);
if (i == r) break;
root[l] = merge(0, KEY_MAX, c, root[i]);
ss.erase(i);
}
rev[l] = 0;
};
void sort_dec(int l, int r) {
if (l == r) return;
sort_inc(l, r), rev[l] = 1;
};
vc<int> get_all() {
vector<int> key;
key.reserve(N);
auto dfs = [&](auto& dfs, np n, int l, int r, bool rev) -> void {
if (!n || !n->size) return;
if (r == l + 1) {
FOR(n->size) key.eb(l);
return;
}
int m = (l + r) / 2;
if (!rev) {
dfs(dfs, n->l, l, m, rev), dfs(dfs, n->r, m, r, rev);
}
if (rev) {
dfs(dfs, n->r, m, r, rev), dfs(dfs, n->l, l, m, rev);
}
};
for (int i = 0; i < N; ++i) {
if (ss[i]) dfs(dfs, root[i], 0, KEY_MAX, rev[i]);
}
return key;
}
int get(int idx) {
auto dfs = [&](auto& dfs, np n, int l, int r, int k) -> int {
if (r == l + 1) {
return l;
}
int m = (l + r) / 2;
int s = (n->l ? n->l->size : 0);
if (k < s) return dfs(dfs, n->l, l, m, k);
return dfs(dfs, n->r, m, r, k - s);
};
int i = ss.prev(idx);
int k = idx - i;
int s = root[i]->size;
if (rev[i]) k = s - 1 - k;
return dfs(dfs, root[i], 0, KEY_MAX, k);
}
private:
void init(vector<int>& key) {
rev.assign(N, 0), root.clear(), root.reserve(N);
ss.build(N, [&](int i) -> int { return 1; });
for (int i = 0; i < N; ++i) {
root.eb(new_node(0));
assert(key[i] < KEY_MAX);
set_rec(root[i], 0, KEY_MAX, key[i]);
}
}
// x が左端になるようにする
void split_at(int x) {
if (x == N || ss[x]) return;
int a = ss.prev(x), b = ss.next(a + 1);
ss.insert(x);
if (!rev[a]) {
auto [nl, nr] = split(root[a], 0, KEY_MAX, x - a);
root[a] = nl, root[x] = nr;
rev[a] = rev[x] = 0;
} else {
auto [nl, nr] = split(root[a], 0, KEY_MAX, b - x);
root[a] = nr, root[x] = nl;
rev[a] = rev[x] = 1;
}
}
void rebuild() {
auto key = get_all();
pool.reset();
init(key);
}
np new_node(int size) {
np c = pool.create();
c->l = c->r = nullptr, c->size = size;
return c;
}
pair<np, np> split(np n, int l, int r, int k) {
if (k == 0) {
return {nullptr, n};
}
if (k == n->size) {
return {n, nullptr};
}
if (r == l + 1) {
int s = n->size;
n->size = k;
Node* b = new_node(s - k);
return {n, b};
}
int s = (n->l ? n->l->size : 0);
Node* b = new_node(0);
int m = (l + r) / 2;
if (k <= s) {
auto [nl, nr] = split(n->l, l, m, k);
b->l = nr, b->r = n->r, n->l = nl, n->r = nullptr;
}
if (k > s) {
auto [nl, nr] = split(n->r, m, r, k - s);
n->l = n->l, n->r = nl, b->l = nullptr, b->r = nr;
}
update(n), update(b);
return {n, b};
}
np merge(int l, int r, np a, np b) {
if (!a) return b;
if (!b) return a;
if (r == l + 1) {
a->size += b->size;
return a;
}
int m = (l + r) / 2;
a->l = merge(l, m, a->l, b->l), a->r = merge(m, r, a->r, b->r);
update(a);
return a;
}
void update(np n) {
if (!(n->l) && !(n->r)) {
return;
}
if (!(n->l)) {
n->size = n->r->size;
return;
}
if (!(n->r)) {
n->size = n->l->size;
return;
}
n->size = n->l->size + n->r->size;
}
void set_rec(np n, int l, int r, int k) {
if (r == l + 1) {
n->size = 1;
return;
}
int m = (l + r) / 2;
if (k < m) {
if (!(n->l)) n->l = new_node(0);
set_rec(n->l, l, m, k);
}
if (m <= k) {
if (!(n->r)) n->r = new_node(0);
set_rec(n->r, m, r, k);
}
update(n);
}
};#line 1 "ds/sortable_array.hpp"
// Source: https://github.com/maspypy/library/blob/main/ds/sortable_array.hpp
#line 1 "ds/fastset.hpp"
// Source: https://github.com/maspypy/library/blob/main/ds/fastset.hpp
// 64-ary tree
// space: (N/63) * u64
struct FastSet {
static constexpr u32 B = 64;
int n = 0, log = 0;
vvc<u64> seg;
FastSet() {}
FastSet(int n) { build(n); }
int size() { return n; }
void fill_one() {
int cur = n;
for (auto& vs : seg) {
int p = cur / B, q = cur % B;
FOR(i, p) vs[i] = -1ull;
if (q) vs[p] = full_mask(q);
cur = (cur + B - 1) / B;
}
}
template <typename F>
FastSet(int n, F f) {
build(n, f);
}
void build(int m) {
seg.clear();
n = m;
do {
seg.push_back(vc<u64>((m + B - 1) / B));
m = (m + B - 1) / B;
} while (m > 1);
log = len(seg);
}
template <typename F>
void build(int n, F f) {
build(n);
FOR(i, n) { seg[0][i / B] |= u64(bool(f(i))) << (i % B); }
FOR(h, log - 1) {
FOR(i, len(seg[h])) {
seg[h + 1][i / B] |= u64(bool(seg[h][i])) << (i % B);
}
}
}
bool operator[](int i) const {
assert(0 <= i && i < n);
return seg[0][i / B] >> (i % B) & 1;
}
void insert(int i) {
assert(0 <= i && i < n);
for (int h = 0; h < log; h++) {
u64& x = seg[h][i / B];
u64 mask = u64(1) << (i % B);
if (x & mask) return;
x |= mask;
i /= B;
}
}
void add(int i) { insert(i); }
void erase(int i) {
assert(0 <= i && i < n);
for (int h = 0; h < log; h++) {
u64& x = seg[h][i / B];
u64 mask = u64(1) << (i % B);
if (!(x & mask)) return;
x ^= mask;
if (x) return;
i /= B;
}
}
void remove(int i) { erase(i); }
// min[x,n) or n
int next(int i) {
assert(i <= n);
chmax(i, 0);
for (int h = 0; h < log; h++) {
if (i / B == seg[h].size()) break;
u64 d = seg[h][i / B] >> (i % B);
if (!d) {
i = i / B + 1;
continue;
}
i += lowbit(d);
for (int g = h - 1; g >= 0; g--) {
i *= B;
i += lowbit(seg[g][i / B]);
}
return i;
}
return n;
}
// max [0,x], or -1
int prev(int i) {
assert(i >= -1);
if (i >= n) i = n - 1;
for (int h = 0; h < log; h++) {
if (i == -1) break;
u64 d = seg[h][i / B] << (63 - i % B);
if (!d) {
i = i / B - 1;
continue;
}
i -= __builtin_clzll(d);
for (int g = h - 1; g >= 0; g--) {
i *= B;
i += topbit(seg[g][i / B]);
}
return i;
}
return -1;
}
bool any(int l, int r) {
assert(0 <= l && l <= r && r <= n);
return next(l) < r;
}
// [l, r). erase=true のとき、callback 内から this を変更してはいけない。
template <typename F>
void enumerate(int l, int r, F f, bool erase = false) {
bool end = false;
assert(0 <= l && l <= r && r <= n);
if (!erase) {
for (int x = next(l); x < r; x = next(x + 1)) {
f(x, end);
if (end) return;
}
return;
}
for (int x = next(l); x < r;) {
int w = x / B;
int lo = max(l, w * int(B)) - w * int(B);
int hi = min(r, (w + 1) * int(B)) - w * int(B);
u64 erase_bits = seg[0][w] & (full_mask(hi) & ~full_mask(lo));
u64 bits = erase_bits;
while (bits) {
int k = lowbit(bits);
f(w * int(B) + k, end);
bits ^= u64(1) << k;
assert(!end); // 未対応
}
seg[0][w] ^= erase_bits;
if (!seg[0][w]) propagate_empty_word(w);
x = next(min(r, (w + 1) * int(B)));
}
}
void reset() {
int x = next(0);
while (x < n) {
int w = x / B;
seg[0][w] = 0;
propagate_empty_word(w);
x = next(min(n, (w + 1) * int(B)));
}
}
string to_string() {
string s(n, '?');
for (int i = 0; i < n; ++i) s[i] = ((*this)[i] ? '1' : '0');
return s;
}
private:
// seg[0][w] が 0 になった後に呼ぶ。
void propagate_empty_word(int i) {
for (int h = 1; h < log; ++h) {
u64& y = seg[h][i / B];
u64 mask = u64(1) << (i % B);
y ^= mask;
if (y) break;
i /= B;
}
}
};
#line 1 "ds/node_pool.hpp"
// Source: https://github.com/maspypy/library/blob/main/ds/node_pool.hpp
// マルチテストケースでも確保済み chunk を再利用する
template <class Node>
struct Node_Pool {
union Slot {
Node node;
Slot* next;
Slot() {}
~Slot() {}
};
using np = Node*;
static constexpr int CHUNK_SIZE = 1 << 12;
vc<unique_ptr<Slot[]>> chunks;
int chunk_id = 0;
int pos = 0;
Slot* free_head = nullptr;
~Node_Pool() {
auto& cache = chunk_cache();
for (auto& p : chunks) cache.eb(std::move(p));
}
template <class... Args>
np create(Args&&... args) {
Slot* s = new_slot();
return ::new (&s->node) Node(forward<Args>(args)...);
}
np clone(const np x) {
assert(x);
Slot* s = new_slot();
return ::new (&s->node) Node(*x);
}
void destroy(np x) {
if (!x) return;
x->~Node();
Slot* s = reinterpret_cast<Slot*>(x);
s->next = free_head;
free_head = s;
}
// 全 node を無効化する。
// 確保済み chunk は解放せず、次回以降に再利用する。
void reset() {
free_head = nullptr;
chunk_id = 0;
pos = 0;
}
int used() const { return chunk_id * CHUNK_SIZE + pos; }
private:
static vc<unique_ptr<Slot[]>>& chunk_cache() {
// static Node_Pool の destructor より先に破棄されないようにする。
static auto* cache = new vc<unique_ptr<Slot[]>>();
return *cache;
}
void alloc_chunk() {
auto& cache = chunk_cache();
if (cache.empty()) {
chunks.eb(make_unique<Slot[]>(CHUNK_SIZE));
} else {
chunks.eb(std::move(cache.back()));
cache.pop_back();
}
}
Slot* new_slot() {
if (free_head) {
Slot* s = free_head;
free_head = free_head->next;
return s;
}
if (chunk_id == len(chunks)) alloc_chunk();
Slot* s = &chunks[chunk_id][pos++];
if (pos == CHUNK_SIZE) {
++chunk_id;
pos = 0;
}
return s;
}
};
#line 4 "ds/sortable_array.hpp"
// int 列を扱う. key の重複可.
struct Sortable_Array {
const int N, KEY_MAX;
struct Node {
int size;
Node *l, *r;
};
Node_Pool<Node> pool;
using np = Node*;
FastSet ss; // 区間の左端全体を表す fastset
vector<np> root; // 区間の左端に、dynamic segtree の node を乗せる
vector<bool> rev;
Sortable_Array(int NODES, int KEY_MAX, vector<int> key)
: N(key.size()), KEY_MAX(KEY_MAX), ss(key.size()) {
init(key);
}
void set(int i, int key) {
assert(0 <= key && key < KEY_MAX);
split_at(i), split_at(i + 1);
rev[i] = 0, root[i] = new_node(0);
set_rec(root[i], 0, KEY_MAX, key);
}
void sort_inc(int l, int r) {
if (l == r) return;
split_at(l), split_at(r);
while (1) {
np c = root[l];
int i = ss.next(l + 1);
if (i == r) break;
root[l] = merge(0, KEY_MAX, c, root[i]);
ss.erase(i);
}
rev[l] = 0;
};
void sort_dec(int l, int r) {
if (l == r) return;
sort_inc(l, r), rev[l] = 1;
};
vc<int> get_all() {
vector<int> key;
key.reserve(N);
auto dfs = [&](auto& dfs, np n, int l, int r, bool rev) -> void {
if (!n || !n->size) return;
if (r == l + 1) {
FOR(n->size) key.eb(l);
return;
}
int m = (l + r) / 2;
if (!rev) {
dfs(dfs, n->l, l, m, rev), dfs(dfs, n->r, m, r, rev);
}
if (rev) {
dfs(dfs, n->r, m, r, rev), dfs(dfs, n->l, l, m, rev);
}
};
for (int i = 0; i < N; ++i) {
if (ss[i]) dfs(dfs, root[i], 0, KEY_MAX, rev[i]);
}
return key;
}
int get(int idx) {
auto dfs = [&](auto& dfs, np n, int l, int r, int k) -> int {
if (r == l + 1) {
return l;
}
int m = (l + r) / 2;
int s = (n->l ? n->l->size : 0);
if (k < s) return dfs(dfs, n->l, l, m, k);
return dfs(dfs, n->r, m, r, k - s);
};
int i = ss.prev(idx);
int k = idx - i;
int s = root[i]->size;
if (rev[i]) k = s - 1 - k;
return dfs(dfs, root[i], 0, KEY_MAX, k);
}
private:
void init(vector<int>& key) {
rev.assign(N, 0), root.clear(), root.reserve(N);
ss.build(N, [&](int i) -> int { return 1; });
for (int i = 0; i < N; ++i) {
root.eb(new_node(0));
assert(key[i] < KEY_MAX);
set_rec(root[i], 0, KEY_MAX, key[i]);
}
}
// x が左端になるようにする
void split_at(int x) {
if (x == N || ss[x]) return;
int a = ss.prev(x), b = ss.next(a + 1);
ss.insert(x);
if (!rev[a]) {
auto [nl, nr] = split(root[a], 0, KEY_MAX, x - a);
root[a] = nl, root[x] = nr;
rev[a] = rev[x] = 0;
} else {
auto [nl, nr] = split(root[a], 0, KEY_MAX, b - x);
root[a] = nr, root[x] = nl;
rev[a] = rev[x] = 1;
}
}
void rebuild() {
auto key = get_all();
pool.reset();
init(key);
}
np new_node(int size) {
np c = pool.create();
c->l = c->r = nullptr, c->size = size;
return c;
}
pair<np, np> split(np n, int l, int r, int k) {
if (k == 0) {
return {nullptr, n};
}
if (k == n->size) {
return {n, nullptr};
}
if (r == l + 1) {
int s = n->size;
n->size = k;
Node* b = new_node(s - k);
return {n, b};
}
int s = (n->l ? n->l->size : 0);
Node* b = new_node(0);
int m = (l + r) / 2;
if (k <= s) {
auto [nl, nr] = split(n->l, l, m, k);
b->l = nr, b->r = n->r, n->l = nl, n->r = nullptr;
}
if (k > s) {
auto [nl, nr] = split(n->r, m, r, k - s);
n->l = n->l, n->r = nl, b->l = nullptr, b->r = nr;
}
update(n), update(b);
return {n, b};
}
np merge(int l, int r, np a, np b) {
if (!a) return b;
if (!b) return a;
if (r == l + 1) {
a->size += b->size;
return a;
}
int m = (l + r) / 2;
a->l = merge(l, m, a->l, b->l), a->r = merge(m, r, a->r, b->r);
update(a);
return a;
}
void update(np n) {
if (!(n->l) && !(n->r)) {
return;
}
if (!(n->l)) {
n->size = n->r->size;
return;
}
if (!(n->r)) {
n->size = n->l->size;
return;
}
n->size = n->l->size + n->r->size;
}
void set_rec(np n, int l, int r, int k) {
if (r == l + 1) {
n->size = 1;
return;
}
int m = (l + r) / 2;
if (k < m) {
if (!(n->l)) n->l = new_node(0);
set_rec(n->l, l, m, k);
}
if (m <= k) {
if (!(n->r)) n->r = new_node(0);
set_rec(n->r, m, r, k);
}
update(n);
}
};