結果
| 問題 |
No.925 紲星 Extra
|
| コンテスト | |
| ユーザー |
 lumc_
|
| 提出日時 | 2019-09-23 21:47:05 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 34,415 bytes |
| コンパイル時間 | 3,307 ms |
| コンパイル使用メモリ | 176,728 KB |
| 実行使用メモリ | 818,312 KB |
| 最終ジャッジ日時 | 2024-09-19 04:37:03 |
| 合計ジャッジ時間 | 31,380 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 10 MLE * 1 -- * 8 |
ソースコード
#if 0
想定解 : スケープゴート木
time : O((N + Q) lg^2 (N + Q))
space : O((N + Q) lg (N + Q))
alpha = 6/11
rebuildの計算量は O(N lg^2 N) だけど
insert/delete は O(N lg N) なきがする
#endif
#if 0
スケープゴート木
* ScapegoatTreeDriver はスケゴ以外にも乗せることを想定した名前，そう変える
* 必要ない機能は一部省略
* split, mergeなどはなし
* split_min はない
* inlcude_i, include_j もなし
* lazy なし
* union はサイズに対し線形時間 (これで十分)
#endif
#define NDEBUG
#define DEBUG_OUT std::cerr
#define ONLINE
// #undef DEBUG
// #define DEBUG
// DEBUG {{{
#include <array>
#include <deque>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <valarray>
#include <vector>
template < int n, class... T >
typename std::enable_if< (n >= sizeof...(T)) >::type __output_tuple(
std::ostream &, std::tuple< T... > const &) {}
template < int n, class... T >
typename std::enable_if< (n < sizeof...(T)) >::type __output_tuple(
std::ostream &os, std::tuple< T... > const &t) {
os << (n == 0 ? "" : ", ") << std::get< n >(t);
__output_tuple< n + 1 >(os, t);
}
template < class... T >
std::ostream &operator<<(std::ostream &os, std::tuple< T... > const &t) {
os << "(";
__output_tuple< 0 >(os, t);
os << ")";
return os;
}
template < class T, class U >
std::ostream &operator<<(std::ostream &os, std::pair< T, U > const &p) {
os << "(" << p.first << ", " << p.second << ")";
return os;
}
template < class T >
std::ostream &operator<<(std::ostream &os, const std::stack< T > &a) {
os << "{";
for(auto tmp = a; tmp.size(); tmp.pop())
os << (a.size() == tmp.size() ? "" : ", ") << tmp.top();
os << "}";
return os;
}
template < class T, class Container, class Compare >
std::ostream &operator<<(std::ostream &os,
std::priority_queue< T, Container, Compare > a) {
os << "{ (top) ";
while(a.size()) os << a.top() << (a.size() == 1 ? "" : ", "), a.pop();
os << " }";
return os;
}
template < class T, class Container >
std::ostream &operator<<(std::ostream &os, std::queue< T, Container > a) {
os << "{ ";
while(a.size()) os << a.front() << (a.size() == 1 ? "" : ", "), a.pop();
os << " }";
return os;
}
#ifdef DEBUG
#if !defined(DEBUG_OUT)
#define DEBUG_OUT std::cerr
#endif
#define dump(...) \
[&]() { \
auto __debug_tap = std::make_tuple(__VA_ARGS__); \
DEBUG_OUT << "[" << __LINE__ << "] " << #__VA_ARGS__ << " = " << __debug_tap \
<< std::endl; \
}()
template < class T >
inline void dump2D(T &d, size_t sizey, size_t sizex) {
for(size_t i = 0; i < sizey; i++) {
DEBUG_OUT << "\t";
for(size_t j = 0; j < sizex; j++)
DEBUG_OUT << d[i][j] << (j + 1 == sizex ? "" : "\t");
DEBUG_OUT << std::endl;
}
}
template < class T >
inline void dump1D(T &d, size_t sizey) {
for(size_t i = 0; i < sizey; i++) {
DEBUG_OUT << d[i] << (i + 1 == sizey ? "" : " ");
}
DEBUG_OUT << std::endl;
}
template <
class T, class = typename std::iterator_traits< decltype(begin(T())) >::value_type,
class = typename std::enable_if< !std::is_same< T, std::string >::value >::type >
std::ostream &operator<<(std::ostream &os, const T &a) {
os << "{";
for(auto ite = begin(a); ite != end(a); ++ite)
os << (ite == begin(a) ? "" : ", ") << *ite;
os << "}";
return os;
}
#else
#define dump(...) ((void) 42)
#define dump2D(...) ((void) 42)
#define dump1D(...) ((void) 42)
template <
class T, class = typename std::iterator_traits< decltype(begin(T())) >::value_type,
class = typename std::enable_if< !std::is_same< T, std::string >::value >::type >
std::ostream &operator<<(std::ostream &os, const T &a) {
for(auto ite = begin(a); ite != end(a); ++ite)
os << (ite == begin(a) ? "" : " ") << *ite;
return os;
}
#endif
// }}}
/// --- Monoid examples {{{ ///
constexpr long long inf_monoid = 1e18 + 100;
#include <algorithm>
struct Nothing {
using T = char;
using Monoid = Nothing;
using M = T;
static constexpr T op(const T &, const T &) { return T(); }
static constexpr T identity() { return T(); }
template < class X >
static constexpr X actInto(const M &, long long, const X &x) {
return x;
}
};
template < class _Monoid >
struct Nothing_M_act {
using Monoid = _Monoid;
using T = typename Monoid::T;
using M = char;
static constexpr M op(const T &, const T &) { return T(); }
static constexpr M identity() { return T(); }
template < class X >
static constexpr X actInto(const M &, long long, const X &x) {
return x;
}
};
template < class U = long long >
struct RangeMin {
using T = U;
static T op(const T &a, const T &b) { return std::min< T >(a, b); }
static constexpr T identity() { return T(inf_monoid); }
};
template < class U = long long >
struct RangeMax {
using T = U;
static T op(const T &a, const T &b) { return std::max< T >(a, b); }
static constexpr T identity() { return T(-inf_monoid); }
};
template < class U = long long >
struct RangeSum {
using T = U;
static T op(const T &a, const T &b) { return a + b; }
static constexpr T identity() { return T(0); }
};
template < class U >
struct RangeProd {
using T = U;
static T op(const T &a, const T &b) { return a * b; }
static constexpr T identity() { return T(1); }
};
template < class U = long long >
struct RangeOr {
using T = U;
static T op(const T &a, const T &b) { return a | b; }
static constexpr T identity() { return T(0); }
};
#include <bitset>
template < class U = long long >
struct RangeAnd {
using T = U;
static T op(const T &a, const T &b) { return a & b; }
static constexpr T identity() { return T(-1); }
};
template < size_t N >
struct RangeAnd< std::bitset< N > > {
using T = std::bitset< N >;
static T op(const T &a, const T &b) { return a & b; }
static constexpr T identity() { return std::bitset< N >().set(); }
};
/// }}}--- ///
/// --- M_act examples {{{ ///
template < class U = long long, class V = U >
struct RangeMinAdd {
using X = U;
using M = V;
using Monoid = RangeMin< U >;
static M op(const M &a, const M &b) { return a + b; }
static constexpr M identity() { return 0; }
static X actInto(const M &m, long long, const X &x) { return m + x; }
};
template < class U = long long, class V = U >
struct RangeMaxAdd {
using X = U;
using M = V;
using Monoid = RangeMax< U >;
static M op(const M &a, const M &b) { return a + b; }
static constexpr M identity() { return 0; }
static X actInto(const M &m, long long, const X &x) { return m + x; }
};
template < class U = long long, class V = U >
struct RangeMinSet {
using M = U;
using Monoid = RangeMin< U >;
using X = typename Monoid::T;
static M op(const M &a, const M &b) { return a == identity() ? b : a; }
static constexpr M identity() { return M(-inf_monoid); }
static X actInto(const M &m, long long, const X &x) { return m == identity() ? x : m; }
};
template < class U = long long, class V = U >
struct RangeMaxSet {
using M = U;
using Monoid = RangeMax< U >;
using X = typename Monoid::T;
static M op(const M &a, const M &b) { return a == identity() ? b : a; }
static constexpr M identity() { return M(-inf_monoid); }
static X actInto(const M &m, long long, const X &x) { return m == identity() ? x : m; }
};
template < class U = long long, class V = U >
struct RangeSumAdd {
using X = U;
using M = V;
using Monoid = RangeSum< U >;
static M op(const M &a, const M &b) { return a + b; }
static constexpr M identity() { return 0; }
static X actInto(const M &m, long long n, const X &x) { return m * n + x; }
};
template < class U = long long, class V = U >
struct RangeSumSet {
using X = U;
using M = V;
using Monoid = RangeSum< U >;
static M op(const M &a, const M &b) { return a == identity() ? a : b; }
static constexpr M identity() { return M(-inf_monoid); }
static X actInto(const M &m, long long n, const X &x) {
return m == identity() ? x : m * n;
}
};
template < class U, class V = U >
struct RangeProdMul {
using X = U;
using M = V;
using Monoid = RangeProd< U >;
static M mpow(M a, long long b) {
X r(1);
while(b) {
if(b & 1) r = r * a;
a = a * a;
b >>= 1;
}
return r;
}
static M op(const M &a, const M &b) { return a * b; }
static constexpr M identity() { return M(1); }
static X actInto(const M &m, long long n, const X &x) { return x * mpow(m, n); }
};
template < class U, class V = U >
struct RangeProdSet {
using X = U;
using M = V;
using Monoid = RangeProd< U >;
static M op(const M &a, const M &b) { return a == identity() ? b : a; }
static constexpr M identity() { return V::unused; }
static X actInto(const M &m, long long n, const X &) {
if(m == identity()) return;
return RangeProdMul< U, V >::mpow(m, n);
}
};
template < class U = long long, class V = U >
struct RangeOrSet {
using X = U;
using M = V;
using Monoid = RangeOr< U >;
static M op(const M &a, const M &b) { return a == identity() ? b : a; }
static constexpr M identity() { return M(-inf_monoid); }
static X actInto(const M &m, long long, const X &x) { return m == identity() ? x : m; }
};
template < class U = long long, class V = U >
struct RangeAndSet {
using X = U;
using M = V;
using Monoid = RangeAnd< U >;
static M op(const M &a, const M &b) { return a == identity() ? b : a; }
static constexpr M identity() { return M(-inf_monoid); }
static X actInto(const M &m, long long, const X &x) { return m == identity() ? x : m; }
};
template < class U = long long, class V = U >
struct RangeOr2 {
using X = U;
using M = V;
using Monoid = RangeOr< U >;
static M op(const M &a, const M &b) { return a | b; }
static constexpr M identity() { return M(0); }
static X actInto(const M &m, long long, const X &x) { return m | x; }
};
template < class U = long long, class V = U >
struct RangeAnd2 {
using X = U;
using M = V;
using Monoid = RangeAnd< U >;
static M op(const M &a, const M &b) { return a & b; }
static constexpr M identity() { return M(-1); }
static X actInto(const M &m, long long, const X &x) { return m & x; }
};
template < class U, size_t N >
struct RangeAnd2< U, std::bitset< N > > {
using X = U;
using M = std::bitset< N >;
using Monoid = RangeAnd< U >;
static M op(const M &a, const M &b) { return a & b; }
static constexpr M identity() { return std::bitset< N >().set(); }
static X actInto(const M &m, long long, const X &x) { return m & x; }
};
/// }}}--- ///
#define SCAPEGOAT_SAVE_SIZE 1
// scapegoat tree {{{
#include <cassert>
#include <cmath>
#include <tuple>
#include <vector>
namespace scapegoat_tree {
// node {{{
template < class Key, class M_act >
struct Node {
using size_type = std::size_t;
using pointer = Node *;
using const_pointer = const Node *;
using Monoid = typename M_act::Monoid;
using T = typename Monoid::T;
#if SCAPEGOAT_SAVE_SIZE
size_type sz = 0;
#endif
pointer ch[2] = {0, 0}; // l = 0, r = 1
Key key;
T value, accum;
template < class K, class U >
Node(K &&key, U &&value)
: key(std::forward< K >(key)), value(value), accum(std::forward< U >(value)) {
#if SCAPEGOAT_SAVE_SIZE
sz = 1;
#endif
}
template < class K >
Node(K &&key) : Node(std::forward< Key >(key), Monoid::identity()) {}
static size_type size(const_pointer p) {
if(!p) return 0;
#if SCAPEGOAT_SAVE_SIZE
return p->sz;
#else
return size(p->ch[0]) + 1 + size(p->ch[1]); // definition-base
#endif
}
static bool is_nil(const_pointer p) { return !p; }
static const T &get_accum(const_pointer p) {
static auto identity = Monoid::identity();
if(!p) return identity;
return p->accum;
}
static pointer update(pointer p, bool is_identity = 0) {
if(is_nil(p)) return p; // TODO : assert ?
#if SCAPEGOAT_SAVE_SIZE
p->sz = size(p->ch[0]) + 1 + size(p->ch[1]);
#endif
if(!is_identity) {
p->accum =
Monoid::op(Monoid::op(get_accum(p->ch[0]), p->value), get_accum(p->ch[1]));
}
return p;
}
static pointer copy(const_pointer p) {
static std::vector< const_pointer > v;
v.clear();
get_all_ptr_dfs(p, v);
std::vector< pointer > w;
for(const_pointer e : v) w.push_back(new Node(e->key, e->value));
return make_perfect(w, 0, w.size());
}
// p を根とする部分木を rebuild して新しい根のポインターを返す
static pointer rebuild(pointer p) {
static std::vector< pointer > v;
v.clear();
get_all_ptr_dfs(p, v);
return make_perfect(v, 0, v.size());
}
// make perfect balanced binary search tree
static pointer make_perfect(std::vector< pointer > &pts, size_type l, size_type r) {
if(l == r) return 0;
size_type m = (l + r) / 2;
pts[m]->ch[0] = make_perfect(pts, l, m);
pts[m]->ch[1] = make_perfect(pts, m + 1, r);
update(pts[m]);
return pts[m];
}
template < class P >
static void get_all_ptr_dfs(P p, std::vector< P > &v) {
if(!p) return;
get_all_ptr_dfs< P >(p->ch[0], v);
v.push_back(p);
get_all_ptr_dfs< P >(p->ch[1], v);
}
static std::vector< Key > get_all(const_pointer p) {
std::vector< Key > v;
get_all_dfs(p, v);
return v;
}
static void get_all_dfs(const_pointer p, std::vector< Key > &v) {
if(!p) return;
get_all_dfs(p->ch[0], v);
v.push_back(p->key);
get_all_dfs(p->ch[1], v);
}
static pointer splice(pointer p) {
if(!p->ch[0]) {
pointer q = p->ch[1];
delete p;
return q;
} else if(!p->ch[1]) {
pointer q = p->ch[0];
delete p;
return q;
} else {
pointer s, t;
std::tie(s, t) = split_max(p->ch[0]);
t->ch[0] = s;
t->ch[1] = p->ch[1];
delete p;
update(t);
return t;
}
}
static std::pair< pointer, pointer > split_max(pointer p) {
assert(p);
pointer t = p, s = 0;
static std::vector< pointer > pts;
assert(pts.empty());
while(t->ch[1]) {
pts.push_back(t);
s = t;
t = t->ch[1];
}
assert(t && !t->ch[1]);
if(s) {
s->ch[1] = t->ch[0];
update(s);
s = p;
} else
s = p->ch[0];
t->ch[0] = 0;
while(pts.size()) {
update(pts.back());
pts.pop_back();
}
update(t);
return {s, t};
}
static T fold(const_pointer p, Key keyL, Key keyR, bool include_l, bool include_r) {
while(p) {
if(p->key < keyL || (!include_l && !(keyL < p->key)))
p = p->ch[1];
else if(keyR < p->key || (!include_r && !(p->key < keyR)))
p = p->ch[0];
else
break;
}
if(!p) return Monoid::identity();
T x = p->value;
const_pointer pl = p->ch[0], pr = p->ch[1];
while(pl) {
if(pl->key < keyL) {
pl = pl->ch[1];
} else {
x = Monoid::op(get_accum(pl->ch[1]), std::move(x));
if(keyL < pl->key) {
x = Monoid::op(pl->value, std::move(x));
pl = pl->ch[0];
} else {
if(include_l) x = Monoid::op(pl->value, std::move(x));
break;
}
}
}
while(pr) {
if(keyR < pr->key) {
pr = pr->ch[0];
} else {
x = Monoid::op(std::move(x), get_accum(pr->ch[0]));
if(pr->key < keyR) {
x = Monoid::op(std::move(x), pr->value);
pr = pr->ch[1];
} else {
if(include_r) x = Monoid::op(std::move(x), pr->value);
break;
}
}
}
return x;
}
// set operations {{{
static pointer union_(pointer t1, pointer t2) {
if(is_nil(t1)) return t2;
if(is_nil(t2)) return t1;
static std::vector< pointer > v1, v2;
v1.clear(), v2.clear();
get_all_ptr_dfs(t1, v1);
get_all_ptr_dfs(t2, v2);
static std::vector< pointer > w;
w.clear();
size_type i1 = 0, i2 = 0;
while(i1 < v1.size() || i2 < v2.size()) {
if(i2 == v2.size()) {
w.push_back(v1[i1++]);
} else if(i1 == v1.size()) {
w.push_back(v2[i2++]);
} else {
if(v1[i1]->key < v2[i2]->key) {
w.push_back(v1[i1++]);
} else if(v2[i2]->key < v1[i1]->key) {
w.push_back(v2[i2++]);
} else {
w.push_back(v1[i1++]);
delete v2[i2++];
}
}
}
return make_perfect(w, 0, w.size());
}
// }}}
// order statistics operations {{{
static std::pair< Key, T > select(pointer p, size_type k) {
assert(!is_nil(p));
if(k < size(p->ch[0])) return select(p->ch[0], k);
k -= size(p->ch[0]);
if(k == 0) return {p->key, p->value};
k--;
return select(p->ch[1], k);
}
// count {{{
static size_type count(const_pointer p, const Key &keyL, const Key &keyR,
bool include_l, bool include_r) {
if(keyR < keyL) return 0;
const_pointer t = p;
while(!is_nil(t)) {
if(!(keyL < t->key)) {
// key <= keyL
if(include_l && !(t->key < keyL))
return 1 + count_lesser(t->ch[1], keyR, include_r);
t = t->ch[1];
} else if(!(t->key < keyR)) {
// keyR <= key
if(include_r && !(keyR < t->key))
return 1 + count_greater(t->ch[0], keyL, include_l);
t = t->ch[0];
} else {
// keyL < key < keyR
return count_greater(t->ch[0], keyL, include_l) + 1 +
count_lesser(t->ch[1], keyR, include_r);
}
}
return 0;
}
static size_type count_lesser(const_pointer p, const Key &keyR, bool include_bound) {
size_type res = 0;
const_pointer t = p;
while(!is_nil(t)) {
if(t->key < keyR) {
res += size(t->ch[0]) + 1;
t = t->ch[1];
} else {
// keyR <= key
if(include_bound && !(keyR < t->key)) return res + size(t->ch[0]) + 1;
t = t->ch[0];
}
}
return res;
}
static size_type count_greater(const_pointer p, const Key &keyL, bool include_bound) {
size_type res = 0;
const_pointer t = p;
while(!is_nil(t)) {
if(keyL < t->key) {
res += size(t->ch[1]) + 1;
t = t->ch[0];
} else {
// key <= keyL
if(include_bound && !(t->key < keyL)) return res + size(t->ch[1]) + 1;
t = t->ch[1];
}
}
return res;
}
// }}}
// }}}
static void delete_all(pointer p) {
if(is_nil(p)) return;
delete_all(p->ch[0]);
delete_all(p->ch[1]);
delete p;
}
};
// }}}
// scapegoat tree {{{
template < class Key, class M_act >
struct ScapegoatTree {
using node_type = Node< Key, M_act >;
using size_type = std::size_t;
using pointer = Node< Key, M_act > *;
using const_pointer = const Node< Key, M_act > *;
using Monoid = typename M_act::Monoid;
using T = typename Monoid::T;
pointer p = 0;
size_type rsz = 0; // size of real nodes including removed nodes
size_type vsz = 0; // size of valid nodes
ScapegoatTree() {}
~ScapegoatTree() { clear(); }
public:
ScapegoatTree(const ScapegoatTree &sgt) { *this = sgt; }
ScapegoatTree(ScapegoatTree &&sgt) { *this = std::move(sgt); }
ScapegoatTree &operator=(const ScapegoatTree &sgt) {
p = node_type::copy(sgt.p);
rsz = vsz = sgt.vsz;
return *this;
}
ScapegoatTree &operator=(ScapegoatTree &&sgt) {
p = sgt.p;
rsz = sgt.rsz;
vsz = sgt.vsz;
sgt.p = 0;
sgt.rsz = sgt.vsz = 0;
return *this;
}
// log_{1/alpha}(rsz) = log(rsz) / log(1/alpha)
// log_{3/2}(rsz) = log(rsz) / log(3/2)
// TODO : name
bool is_unbalance(size_type deepest) const {
// deepest > log_{1/alpha}(rsz)
constexpr double inv_log_inv_alpha = 1.0 / std::log(11.0 / 6.0);
return deepest > std::log(rsz) * inv_log_inv_alpha;
}
// a : parent
// b : child
bool is_weight_balanced(size_type a, size_type b) const {
assert(a > b);
// alpha a >= b
// alpha = 6/11
return 6 * a >= 11 * b;
}
// BST operations {{{
public:
template < class K, class = typename std::enable_if<
std::is_convertible< K &&, Key >::value >::type >
bool insert(K &&key) {
return insert(std::forward< K >(key), Monoid::identity(), 1);
}
// NOTE : (グローバルな) 親ありきの関数というのが存在する
template < class K, class U, class = typename std::enable_if<
std::is_convertible< K &&, Key >::value &&
std::is_convertible< U &&, T >::value >::type >
bool insert(K &&key, U &&x, bool is_identity = 0) {
if(!p) {
p = new node_type(std::forward< K >(key), std::forward< U >(x));
++rsz, ++vsz;
return 0;
}
static std::vector< std::pair< pointer, bool > > pts;
assert(pts.empty());
pointer t = p;
while(t) {
bool R = t->key < key;
pts.emplace_back(t, R);
if(!R && !(key < t->key)) {
// found
// TODO : replace
pts.clear();
return 1;
}
t = t->ch[R];
}
++rsz, ++vsz;
pointer u;
bool R;
std::tie(u, R) = pts.back();
assert(!u->ch[R]);
u->ch[R] = new node_type(std::forward< K >(key), std::forward< U >(x));
node_type::update(u, is_identity);
size_type is_unb = is_unbalance(pts.size()); // TODO : name
pointer w = 0, v = 0;
while(pts.size()) {
std::tie(w, std::ignore) = pts.back();
pts.pop_back();
if(pts.size()) {
std::tie(v, std::ignore) = pts.back();
node_type::update(v, is_identity);
if(is_unb) {
if(!is_weight_balanced(node_type::size(v), node_type::size(w))) {
// partial rebuild
pointer u = node_type::rebuild(v);
if(pts.size() >= 2) {
pointer z;
bool R;
std::tie(z, R) = pts[pts.size() - 2];
z->ch[R] = u;
} else {
assert(p == v);
p = u;
}
is_unb = 0;
}
}
}
}
assert(pts.empty());
return 0;
}
public:
template < class K, class = typename std::enable_if<
std::is_convertible< K &&, Key >::value >::type >
bool erase(K &&key) {
if(!p) return 0;
static std::vector< pointer > pts;
assert(pts.empty());
pointer t = p;
pointer q = 0;
bool R;
while(t) {
bool R2 = t->key < key;
if(!R2 && !(key < t->key)) break;
pts.emplace_back(t);
q = t;
R = R2;
t = t->ch[R2];
}
if(!t) {
// not found
pts.clear();
return 0;
}
// found
assert(vsz);
--vsz;
(q ? q->ch[R] : p) = node_type::splice(t);
if(2 * vsz < rsz) {
// global rebuild
p = node_type::rebuild(p);
pts.clear();
rsz = vsz;
} else {
while(pts.size()) {
node_type::update(pts.back());
pts.pop_back();
}
}
return 1;
}
public:
std::vector< Key > get_all() const { return node_type::get_all(p); }
public:
T fold(Key keyL, Key keyR) const { return node_type::fold(p, keyL, keyR, 1, 0); }
T fold(Key keyL, Key keyR, bool include_l, bool include_r) const {
return node_type::fold(p, keyL, keyR, include_l, include_r);
}
public:
size_type size() const { return vsz; }
public:
void clear() {
node_type::delete_all(p);
p = 0;
rsz = vsz = 0;
}
public:
static bool is_nil(const_pointer p) { return !p; }
// }}}
// set operations {{{
public:
ScapegoatTree &union_with(ScapegoatTree &&sgt) {
p = node_type::union_(p, sgt.p);
sgt.p = 0;
sgt.vsz = sgt.rsz = 0;
rsz = vsz = node_type::size(p);
return *this;
}
// }}}
// order statistics operations {{{
std::pair< Key, T > select(size_type k) const { return node_type::select(p, k); }
// count {{{
public:
size_type count(const Key &keyL, const Key &keyR) const {
return node_type::count(p, keyL, keyR, 1, 0);
}
size_type count(const Key &keyL, const Key &keyR, bool include_l,
bool include_r) const {
return node_type::count(p, keyL, keyR, include_l, include_r);
}
size_type count_lesser(const Key &keyR, bool include_r) const {
return node_type::count_lesser(p, keyR, include_r);
}
size_type count_greater(const Key &keyL, bool include_l) const {
return node_type::count_greater(p, keyL, include_l);
}
// }}}
// }}}
};
// }}}
}
// }}}
// TODO : name
// ScapegoatTreeDriver {{{
namespace scapegoat_tree {
template < class _T, class _Monoid, class Index >
struct ScapegoatTreeDriver {
using size_type = std::size_t;
using T = _T;
using Monoid = _Monoid;
using X = typename Monoid::T;
struct Point {
Index x;
T y;
bool minus_inf = 0;
Point() {}
Point(Index x) : x(x), minus_inf(1) {}
Point(Index x, T y) : x(x), y(y) {}
bool operator<(const Point &a) const {
if(x < a.x) return 1;
if(a.x < x) return 0;
if(a.minus_inf) return 0;
if(minus_inf) return 1;
return 0;
}
friend std::ostream &operator<<(std::ostream &os, Point a) {
if(a.minus_inf)
os << "(" << a.x << ", "
<< "-inf"
<< ")";
else
os << "(" << a.x << ", " << a.y << ")";
return os;
}
};
using T_SET = ScapegoatTree< Point, Nothing_M_act< Monoid > >;
struct Driver_Monoid {
using T = T_SET;
static T op(T a, T b) { return std::move(a.union_with(std::move(b))); }
static T identity() { return T(); }
};
struct Driver_M_act {
using Monoid = Driver_Monoid;
using X = typename Monoid::T;
using M = char;
static M op(const M &, const M &) { return 0; }
static constexpr M identity() { return 0; }
static X actInto(const M &, long long, const X &x) { return x; }
};
using BST = ScapegoatTree< T, Driver_M_act >;
using pointer = typename BST::pointer;
using const_pointer = typename BST::const_pointer;
ScapegoatTree< T, Driver_M_act > sgt;
ScapegoatTreeDriver() {}
static ScapegoatTreeDriver with2(const std::vector< std::tuple< T, X > > &v,
Index start = 0) {
std::vector< std::tuple< Index, T, X > > w;
w.reserve(v.size());
for(size_type i = 0; i < v.size(); ++i, ++start)
w.emplace_back(start, std::get< 0 >(v[i]), std::get< 1 >(v[i]));
return with3(w);
}
static ScapegoatTreeDriver with3(std::vector< std::tuple< Index, T, X > > v) {
ScapegoatTreeDriver res;
using V = std::tuple< Index, T, X >;
std::sort(v.begin(), v.end(),
[](const V &a, const V &b) { return std::get< 1 >(a) < std::get< 1 >(b); });
static std::queue< std::pair< size_type, size_type > > q;
q.emplace(0, v.size());
while(q.size()) {
Index l, r;
std::tie(l, r) = q.front();
q.pop();
if(l == r) continue;
Index m = (l + r) / 2;
res.insert(std::get< 0 >(v[m]), std::get< 1 >(v[m]), std::get< 2 >(v[m]));
q.emplace(l, m);
q.emplace(m + 1, r);
}
return res;
}
void insert(Index i, T v, X x, bool is_identity = 0) {
sgt.insert(v);
insert_path_to(sgt.p, v, Point(i, v), x, is_identity);
}
void insert(Index i, T v) { insert(i, v, Monoid::identity(), 1); }
bool erase(Index i, T v) { return erase_path_to(sgt.p, v, Point(i, v)); }
static bool insert_path_to(pointer p, T target, const Point &v, X x, bool is_identity) {
pointer t = p;
static std::vector< pointer > pts;
while(!BST::is_nil(t)) {
if(target < t->key) {
pts.push_back(t);
t = t->ch[0];
} else if(t->key < target) {
pts.push_back(t);
t = t->ch[1];
} else {
t->value.insert(v, x, is_identity);
t->accum.insert(v, x, is_identity);
while(pts.size()) {
t = pts.back();
pts.pop_back();
t->accum.insert(v, x, is_identity);
}
return 1;
}
}
pts.clear();
return 0;
}
static bool erase_path_to(pointer p, T target, const Point &v) {
pointer t = p;
static std::vector< pointer > pts;
while(!BST::is_nil(t)) {
if(target < t->key) {
pts.push_back(t);
t = t->ch[0];
} else if(t->key < target) {
pts.push_back(t);
t = t->ch[1];
} else {
t->value.erase(v);
t->accum.erase(v);
while(pts.size()) {
t = pts.back();
pts.pop_back();
t->accum.erase(v);
}
return 1;
}
}
pts.clear();
return 0;
}
X rect_fold(Index i, Index j, T l, T r) { return rect_fold(i, j, l, r, 1, 0, 1, 0); }
X rect_fold(Index i, Index j, T l, T r, bool include_i, bool include_j, bool include_l,
bool include_r) const {
const_pointer p = sgt.p;
while(!BST::is_nil(p)) {
if(p->key < l || (!include_l && !(l < p->key)))
p = p->ch[1];
else if(r < p->key || (!include_r && !(p->key < r)))
p = p->ch[0];
else
break;
}
if(BST::is_nil(p)) return Monoid::identity();
X x = p->value.fold(i, j);
const_pointer pl = p->ch[0], pr = p->ch[1];
while(!BST::is_nil(pl)) {
if(pl->key < l) {
pl = pl->ch[1];
} else {
x = Monoid::op(BST::node_type::get_accum(pl->ch[1]).fold(i, j), std::move(x));
if(l < pl->key) {
x = Monoid::op(pl->value.fold(i, j), std::move(x));
pl = pl->ch[0];
} else {
if(include_l) x = Monoid::op(pl->value.fold(i, j), std::move(x));
break;
}
}
}
while(!BST::is_nil(pr)) {
if(r < pr->key) {
pr = pr->ch[0];
} else {
x = Monoid::op(std::move(x), BST::node_type::get_accum(pr->ch[0]).fold(i, j));
if(pr->key < r) {
x = Monoid::op(std::move(x), pr->value.fold(i, j));
pr = pr->ch[1];
} else {
if(include_r) x = Monoid::op(std::move(x), pr->value.fold(i, j));
break;
}
}
}
return x;
}
Point range_select(Index i, Index j, size_type k) const {
return range_select_dfs(sgt.p, i, j, k);
}
size_type range_count_smaller(Index i, Index j, T x, bool include_bound) const {
return range_count_smaller_dfs(sgt.p, i, j, x, include_bound);
}
private:
Point range_select_dfs(const_pointer p, Index i, Index j, size_type k) const {
assert(!BST::is_nil(p));
assert(k < BST::node_type::get_accum(p).count(i, j));
size_type lsz = BST::node_type::get_accum(p->ch[0]).count(i, j);
if(k < lsz) {
return range_select_dfs(p->ch[0], i, j, k);
}
k -= lsz;
size_type hsz = p->value.count(i, j);
if(k < hsz) {
return p->value.select(p->value.count_lesser(i, 0) + k).first;
}
k -= hsz;
return range_select_dfs(p->ch[1], i, j, k);
}
size_type range_count_smaller_dfs(const_pointer p, Index i, Index j, T x,
bool include_bound) const {
if(BST::is_nil(p)) return 0;
if(x < p->key) return range_count_smaller_dfs(p->ch[0], i, j, x, include_bound);
// p->key <= x
size_type lsz = BST::node_type::get_accum(p->ch[0]).count(i, j);
size_type hsz = p->value.count(i, j);
if(!(p->key < x)) {
if(include_bound) return lsz + hsz;
return lsz;
}
return lsz + hsz + range_count_smaller_dfs(p->ch[1], i, j, x, include_bound);
}
public:
Point range_median(Index i, Index j, bool choose_greater = 0) const {
return range_select(i, j, (count(i, j) - 1 + choose_greater) / 2);
}
size_type count(Index i, Index j) const {
return BST::node_type::get_accum(sgt.p).count(i, j);
}
size_type size() const { return BST::node_type::get_accum(sgt.p).size(); }
};
}
// }}}
template < class T, class Monoid, class Index = long long >
using ScapegoatTreeDriver = scapegoat_tree::ScapegoatTreeDriver< T, Monoid, Index >;
// includes {{{
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
// #include<deque>
// #include<multiset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;
constexpr int N = 1 << 16;
constexpr ll inf = 1ll << 40; // 1e12
int n, q;
ll t[N], l[N], r[N];
ll med[N], smaller[N], bigger[N];
int main() {
std::ios::sync_with_stdio(false), std::cin.tie(0);
cin >> n >> q;
assert(0 <= n && n < N);
assert(0 <= q && q < N);
vector< ll > v(n + 1);
dump(1);
vector< tuple< ll, ll, ll > > ini;
// ScapegoatTreeDriver< ll, RangeSum< ll > > rm;
for(int i = 1; i <= n; i++) {
cin >> v[i];
ini.emplace_back(i, v[i], v[i]);
// rm.insert(i, v[i], v[i]);
assert(0 <= v[i] && v[i] < inf);
}
auto rm = ScapegoatTreeDriver< ll, RangeSum< ll > >::with3(ini);
dump(2);
for(int i = 0; i < q; i++) cin >> t[i] >> l[i] >> r[i];
dump(3);
auto w = v;
ll sum16 = 0, sum40 = 0;
for(int i = 0; i < q; i++) {
if(t[i] == 1) { // update
#ifdef ONLINE
l[i] ^= sum16;
r[i] ^= sum40;
#endif
assert(1 <= l[i] && l[i] <= n);
// cout << "1 " << l[i] << " " << r[i] << "\n";
rm.erase(l[i], w[l[i]]);
rm.insert(l[i], r[i], r[i]);
w[l[i]] = r[i];
} else { // query
#ifdef ONLINE
l[i] ^= sum16;
r[i] ^= sum16;
#endif
if(l[i] > r[i]) swap(l[i], r[i]);
// cout << "2 " << l[i] << " " << r[i] << "\n";
assert(1 <= l[i] && l[i] <= n);
assert(1 <= r[i] && r[i] <= n);
r[i]++;
int len = r[i] - l[i];
med[i] = rm.range_median(l[i], r[i]).y;
smaller[i] = rm.range_count_smaller(l[i], r[i], med[i], 0);
bigger[i] = len - rm.range_count_smaller(l[i], r[i], med[i], 1);
ll z = 0;
z -= rm.rect_fold(l[i], r[i], 0, med[i]);
z += rm.rect_fold(l[i], r[i], med[i] + 1, inf);
z -= ll(len / 2 - smaller[i]) * med[i];
z += ll((len - len / 2) - bigger[i]) * med[i];
if(len % 2 == 1) z -= med[i];
sum16 ^= z % N;
sum40 ^= z % (1ll << 40);
cout << z << "\n";
}
// if(i % 1000 == 0) dump(i);
}
return 0;
}