結果
| 問題 |
No.925 紲星 Extra
|
| コンテスト | |
| ユーザー |
 lumc_
|
| 提出日時 | 2019-09-17 17:15:17 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 4,382 ms / 10,000 ms |
| コード長 | 39,084 bytes |
| コンパイル時間 | 4,030 ms |
| コンパイル使用メモリ | 174,936 KB |
| 実行使用メモリ | 109,676 KB |
| 最終ジャッジ日時 | 2024-09-19 05:02:05 |
| 合計ジャッジ時間 | 55,376 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 19 |
ソースコード
#if 0
想定解
time : O((N + Q) lg^2 (Q + N))
space : O((Q + N) lg (Q + N))
#endif
// 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;
#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; }
};
/// }}}--- ///
#include <cassert>
#include <cstddef>
#include <functional>
#include <tuple>
#include <utility>
#include <vector>
namespace wbt {
// WeightBalancedTreeNode {{{
template < class Key, class M_act >
struct WeightBalancedTreeNode {
using size_type = std::size_t;
using node_type = WeightBalancedTreeNode;
using pointer = WeightBalancedTreeNode *;
using const_pointer = const WeightBalancedTreeNode *;
using Monoid = typename M_act::Monoid;
using T = typename Monoid::T;
using M = typename M_act::M;
size_type sz;
Key key;
T value = Monoid::identity(), accum = Monoid::identity();
pointer l, r;
size_type weight() const { return sz + 1; }
bool bounded_balanced() const {
if(this == get_NIL()) return 1;
return is_balanced(l, r) && is_balanced(r, l) && l->bounded_balanced() &&
r->bounded_balanced();
}
static long long sq(long long a) { return a * a; };
static bool is_balanced(const_pointer a, const_pointer b) {
// return delta * a->weight() >= b->weight();
// delta = 3
return 3 * a->weight() >= b->weight();
}
static bool is_single(const_pointer a, const_pointer b) {
// return a->weight() < gamma * b->weight();
// gamma = 2
return a->weight() < 2 * b->weight();
}
static std::pair< T, bool > lookup(const_pointer p, Key key) {
const_pointer t = p;
while(t != get_NIL()) {
if(key < t->key) {
t = t->l;
} else if(t->key < key) {
t = t->r;
} else {
return std::pair< T, bool >(t->value, 1);
}
}
return std::pair< T, bool >();
}
static pointer copy(const_pointer a) {
if(a == get_NIL()) return get_NIL();
return make(a->key, a->value, a->accum, copy(a->l), copy(a->r));
}
static T fold(const_pointer p, Key keyL, Key keyR, bool include_left,
bool include_right) {
while(p != get_NIL()) {
if(p->key < keyL || (!include_left && !(keyL < p->key))) p = p->r;
else if(keyR < p->key || (!include_right && !(p->key < keyR))) p = p->l;
else break;
}
if(p == get_NIL()) return Monoid::identity();
T x = p->value;
const_pointer pl = p->l, pr = p->r;
while(pl != get_NIL()) {
if(pl->key < keyL) {
pl = pl->r;
} else {
x = Monoid::op(pl->r->accum, x);
if(keyL < pl->key) {
x = Monoid::op(pl->value, x);
pl = pl->l;
} else {
if(include_left) x = Monoid::op(pl->value, x);
break;
}
}
}
while(pr != get_NIL()) {
if(keyR < pr->key) {
pr = pr->l;
} else {
x = Monoid::op(x, pr->l->accum);
if(pr->key < keyR) {
x = Monoid::op(x, pr->value);
pr = pr->r;
} else {
if(include_right) x = Monoid::op(x, pr->value);
break;
}
}
}
return x;
}
static size_type count(const_pointer p, const Key &keyL, const Key &keyR,
bool include_left, bool include_right) {
if(keyR < keyL) return 0;
const_pointer t = p;
while(t != get_NIL()) {
if(!(keyL < t->key)) {
// key <= keyL
if(include_left && !(t->key < keyL))
return 1 + count_lesser(t->r, keyR, include_right);
t = t->r;
} else if(!(t->key < keyR)) {
// keyR <= key
if(include_right && !(keyR < t->key))
return 1 + count_greater(t->l, keyL, include_left);
t = t->l;
} else {
// keyL < key < keyR
return count_greater(t->l, keyL, include_left) + 1 +
count_lesser(t->r, keyR, include_right);
}
}
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(t != get_NIL()) {
if(t->key < keyR) {
res += t->l->sz + 1;
t = t->r;
} else {
// keyR <= key
if(include_bound && !(keyR < t->key)) return res + t->l->sz + 1;
t = t->l;
}
}
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(t != get_NIL()) {
if(keyL < t->key) {
res += t->r->sz + 1;
t = t->l;
} else {
// key <= keyL
if(include_bound && !(t->key < keyL)) return res + t->r->sz + 1;
t = t->r;
}
}
return res;
}
static pointer insert(pointer p, Key key, T value, bool is_identity) {
if(p == get_NIL()) return make_singleton(key, value);
static std::vector< std::pair< pointer, bool > > pts;
pointer t = p;
while(t != get_NIL()) {
if(key < t->key) {
pts.emplace_back(t, 1);
t = t->l;
} else if(t->key < key) {
pts.emplace_back(t, 0);
t = t->r;
} else {
pts.clear();
return p;
}
}
pointer q;
bool is_left;
std::tie(q, is_left) = pts.back();
(is_left ? q->l : q->r) = make_singleton(key, value);
while(pts.size()) {
std::tie(q, is_left) = pts.back();
pts.pop_back();
update(q, is_identity);
if(is_left) {
balanceR(q);
} else {
balanceL(q);
}
}
return p;
}
static pointer insert_min(pointer p, Key key, T value, bool is_identity) {
if(p == get_NIL()) return make_singleton(key, value);
static std::vector< pointer > pts;
pointer t = p;
while(t != get_NIL()) {
pts.emplace_back(t);
t = t->l;
}
pointer q = pts.back();
q->l = make_singleton(key, value);
while(pts.size()) {
q = pts.back();
pts.pop_back();
update(q, is_identity);
balanceR(q);
}
return p;
}
static pointer insert_max(pointer p, Key key, T value, bool is_identity) {
if(p == get_NIL()) return make_singleton(key, value);
static std::vector< pointer > pts;
pointer t = p;
while(t != get_NIL()) {
pts.emplace_back(t);
t = t->r;
}
pointer q = pts.back();
q->r = make_singleton(key, value);
while(pts.size()) {
q = pts.back();
pts.pop_back();
update(q, is_identity);
balanceR(q);
}
return p;
}
static pointer erase(pointer p, Key key) {
static std::vector< std::pair< pointer, bool > > pts;
pointer t = p;
while(t != get_NIL()) {
if(key < t->key) {
pts.emplace_back(t, 1);
t = t->l;
} else if(t->key < key) {
pts.emplace_back(t, 0);
t = t->r;
} else {
pointer s = glue(t->l, t->r);
delete t;
if(pts.empty()) return s;
pointer q;
bool is_left;
std::tie(q, is_left) = pts.back();
(is_left ? q->l : q->r) = s;
while(pts.size()) {
std::tie(q, is_left) = pts.back();
pts.pop_back();
update(q);
if(is_left) {
balanceL(q);
} else {
balanceR(q);
}
}
break;
}
}
pts.clear();
return p;
}
Key select(size_type k) const {
assert(this != get_NIL());
if(k < l->sz) return l->select(k);
k -= l->sz;
if(k == 0) return key;
k--;
return r->select(k);
}
static pointer balance(Key k, T v, pointer l, pointer r) {
if(is_balanced(l, r) && is_balanced(r, l)) return make(k, v, l, r);
if(l->sz > r->sz) return rotateR(k, v, l, r);
return rotateL(k, v, l, r);
}
static pointer glue(pointer l, pointer r) {
if(l == get_NIL()) return r;
if(r == get_NIL()) return l;
if(l->sz > r->sz) {
pointer l2, p;
std::tie(l2, p) = delete_find_max(l);
p->l = l2;
p->r = r;
update(p);
balanceL(p);
return p;
} else {
pointer r2, p;
std::tie(r2, p) = delete_find_min(r);
p->l = l;
p->r = r2;
update(p);
balanceR(p);
return p;
}
}
// BST basic operations {{{
static pointer merge(pointer l, Key k, T v, pointer r) {
static std::vector< std::pair< pointer, bool > > pts;
pointer q;
while(1) {
if(l == get_NIL()) {
q = insert_min(r, k, v, 0);
break;
}
if(r == get_NIL()) {
q = insert_max(l, k, v, 0);
break;
}
bool bal1 = is_balanced(l, r);
bool bal2 = is_balanced(r, l);
if(bal1 && bal2) {
q = make(k, v, l, r);
break;
} else if(bal1) {
pts.emplace_back(l, 1);
l = l->r;
} else {
pts.emplace_back(r, 0);
r = r->l;
}
}
while(pts.size()) {
pointer p;
bool is_left;
std::tie(p, is_left) = pts.back();
pts.pop_back();
(is_left ? p->r : p->l) = q;
q = p;
update(q);
if(is_left) {
balanceL(q);
} else {
balanceR(q);
}
}
return q;
}
static std::tuple< pointer, bool, pointer > split(pointer a, const Key &k) {
static std::vector< std::pair< pointer, int > > pts;
bool erased = 0;
while(1) {
if(a == get_NIL()) break;
if(k < a->key) {
pts.emplace_back(a, 1);
a = a->l;
} else if(a->key < k) {
pts.emplace_back(a, 0);
a = a->r;
} else {
erased = 1;
break;
}
}
pointer l = a->l, r = a->r;
if(a != get_NIL()) delete a;
while(pts.size()) {
pointer p;
bool is_left;
std::tie(p, is_left) = pts.back();
pts.pop_back();
if(is_left) {
r = merge(r, std::move(p->key), std::move(p->value), p->r);
} else {
l = merge(p->l, std::move(p->key), std::move(p->value), l);
}
delete p;
}
return std::tuple< pointer, bool, pointer >(l, erased, r);
}
// }}}
// set operations {{{
static pointer unionL(pointer t1, pointer t2) {
if(t1 == get_NIL()) return t2;
if(t2 == get_NIL()) return t1;
// if(t1->sz < t2->sz) swap(t1, t2);
pointer t_lesser, t_greater;
std::tie(t_lesser, std::ignore, t_greater) = split(t2, t1->key);
pointer q = merge(unionL(t1->l, t_lesser), std::move(t1->key), std::move(t1->value),
unionL(t1->r, t_greater));
delete t1;
return q;
}
// }}}
using PP = std::tuple< pointer, pointer >;
static PP delete_find_max(pointer p) {
assert(p != get_NIL());
if(p->r == get_NIL()) {
pointer q = p->l;
p->l = get_NIL();
update(p);
return PP(q, p);
}
pointer t = p;
static std::vector<pointer> pts;
while(1) {
pts.push_back(t);
if(t->r->r == get_NIL()) {
pointer q = t->r;
t->r = q->l;
q->l = get_NIL();
update(q);
while(pts.size()) {
pointer s = pts.back();
pts.pop_back();
update(s);
}
return PP(p, q);
} else {
t = t->r;
}
}
}
static PP delete_find_min(pointer p) {
assert(p != get_NIL());
if(p->l == get_NIL()) {
pointer q = p->r;
p->r = get_NIL();
update(p);
return PP(q, p);
}
pointer t = p;
static std::vector<pointer> pts;
while(1) {
pts.push_back(t);
if(t->l->l == get_NIL()) {
pointer q = t->l;
t->l = q->r;
q->r = get_NIL();
update(q);
while(pts.size()) {
pointer s = pts.back();
pts.pop_back();
update(s);
}
return PP(p, q);
} else {
t = t->l;
}
}
}
// rotate {{{
static void balanceL(pointer p) {
if(is_balanced(p->l, p->r)) return;
rotateL(p);
}
static void balanceR(pointer p) {
if(is_balanced(p->r, p->l)) return;
rotateR(p);
}
static void rotateL(pointer p) {
const pointer rl = p->r->l, rr = p->r->r;
if(is_single(rl, rr)) {
singleL(p);
} else {
doubleL(p);
}
}
static void rotateR(pointer p) {
const pointer ll = p->l->l, lr = p->l->r;
if(is_single(lr, ll)) {
singleR(p);
} else {
doubleR(p);
}
}
static void singleL(pointer p) {
pointer q = p->r;
assert(q != get_NIL());
p->r = q->r;
q->r = q->l;
q->l = p->l;
p->l = q;
std::swap(p->key, q->key);
std::swap(p->value, q->value);
update(q);
update(p);
}
static void singleR(pointer p) {
pointer q = p->l;
assert(q != get_NIL());
p->l = q->l;
q->l = q->r;
q->r = p->r;
p->r = q;
std::swap(p->key, q->key);
std::swap(p->value, q->value);
update(q);
update(p);
}
static void doubleL(pointer p) {
pointer s = p->r->l;
assert(s != get_NIL());
p->r->l = s->r;
s->r = s->l;
s->l = p->l;
p->l = s;
std::swap(p->key, s->key);
std::swap(p->value, s->value);
update(p->l);
update(p->r);
update(p);
}
static void doubleR(pointer p) {
pointer s = p->l->r;
assert(s != get_NIL());
p->l->r = s->l;
s->l = s->r;
s->r = p->r;
p->r = s;
std::swap(p->key, s->key);
std::swap(p->value, s->value);
update(p->l);
update(p->r);
update(p);
}
// }}}
static pointer get_NIL() {
static pointer NIL = make_NIL();
return NIL;
}
static pointer make_NIL() {
pointer p = new WeightBalancedTreeNode;
p->sz = 0;
p->value = p->accum = Monoid::identity();
p->l = p;
p->r = p;
return p;
}
static pointer make_singleton(Key key, T value) {
pointer p = new WeightBalancedTreeNode;
p->sz = 1;
p->key = std::move(key);
p->value = p->accum = std::move(value);
p->l = get_NIL();
p->r = get_NIL();
return p;
}
static pointer make(Key key, T value, pointer l, pointer r) {
pointer p = new WeightBalancedTreeNode;
p->sz = l->sz + r->sz + 1;
p->key = std::move(key);
p->value = value;
p->accum = Monoid::op(Monoid::op(l->accum, std::move(value)), r->accum);
p->l = l;
p->r = r;
return p;
}
static void update(pointer p, bool is_identity = 0) {
p->sz = p->l->sz + p->r->sz + 1;
if(!is_identity)
p->accum = Monoid::op(Monoid::op(p->l->accum, p->value), p->r->accum);
}
static pointer make(Key key, T value, T accum, pointer l, pointer r) {
pointer p = new WeightBalancedTreeNode;
p->sz = l->sz + r->sz + 1;
p->key = std::move(key);
p->value = std::move(value);
p->accum = std::move(accum);
p->l = l;
p->r = r;
return p;
}
static std::pair< Key, T > get_min(const_pointer p) {
assert(p != get_NIL());
while(p->l != get_NIL()) p = p->l;
return std::pair< Key, T >(p->key, p->value);
}
static std::pair< Key, T > get_max(const_pointer p) {
assert(p != get_NIL());
while(p->r != get_NIL()) p = p->r;
return std::pair< Key, T >(p->key, p->value);
}
void get_all_dfs(std::vector< std::pair< Key, T > > &res) const {
if(this == get_NIL()) return;
l->get_all_dfs(res);
res.emplace_back(key, value);
r->get_all_dfs(res);
}
static void delete_all(pointer p) {
if(p == get_NIL()) return;
delete_all(p->l);
delete_all(p->r);
delete p;
}
using touch_func = std::function< void(Key key, T &v, T &accum, bool eq) >;
static bool touch_path_to(pointer p, const Key &target, const touch_func &touch) {
pointer t = p;
static std::vector< pointer > pts;
while(t != get_NIL()) {
if(target < t->key) {
pts.push_back(t);
t = t->l;
} else if(t->key < target) {
pts.push_back(t);
t = t->r;
} else {
touch(t->key, t->value, t->accum, 1);
while(pts.size()) {
t = pts.back();
pts.pop_back();
touch(t->key, t->value, t->accum, 0);
}
return 1;
}
}
pts.clear();
return 0;
}
};
// }}}
// WeightBalancedTree {{{
template < class Key, class M_act >
struct WeightBalancedTree {
using size_type = std::size_t;
using node_type = WeightBalancedTreeNode< Key, M_act >;
using pointer = WeightBalancedTreeNode< Key, M_act > *;
using const_pointer = const WeightBalancedTreeNode< Key, M_act > *;
using Monoid = typename M_act::Monoid;
using T = typename Monoid::T;
using M = typename M_act::M;
bool active = 1;
pointer p = node_type::get_NIL();
WeightBalancedTree() {}
WeightBalancedTree(pointer p) : p(p) {}
WeightBalancedTree(const WeightBalancedTree &wbt) { *this = wbt; }
WeightBalancedTree(WeightBalancedTree &&wbt) { *this = std::move(wbt); }
WeightBalancedTree &operator=(const WeightBalancedTree &wbt) {
assert(wbt.active);
if(active) node_type::delete_all(p);
active = 1;
p = node_type::copy(wbt.p);
return *this;
}
WeightBalancedTree &operator=(WeightBalancedTree &&wbt) {
assert(wbt.active);
if(active) node_type::delete_all(p);
active = 1;
wbt.active = 0;
p = wbt.p;
return *this;
}
~WeightBalancedTree() {
if(active) {
node_type::delete_all(p);
}
}
void insert(Key key, T value, bool is_identity = 0) {
assert(active);
p = node_type::insert(p, key, value, is_identity);
}
void insert(Key key) {
insert(key, Monoid::identity(), 1);
}
bool erase(Key key) {
assert(active);
p = node_type::erase(p, key);
// TODO
return 1;
}
std::pair< T, bool > lookup(Key key) const {
assert(active);
return node_type::lookup(p, key);
}
T get(Key key) const {
assert(active);
return lookup(key).first;
}
size_type count(Key key) const {
assert(active);
return lookup(key).second;
}
void clear() {
if(p == node_type::get_NIL()) {
active = 1;
return;
}
if(active) node_type::delete_all(p);
active = 1;
p = node_type::get_NIL();
}
std::vector< std::pair< Key, T > > get_all() const {
assert(active);
std::vector< std::pair< Key, T > > res;
res.reserve(size());
p->get_all_dfs(res);
return res;
}
T fold(Key keyL, Key keyR) const {
assert(active);
return node_type::fold(p, keyL, keyR, 1, 0);
}
T fold(Key keyL, Key keyR, bool include_left, bool include_right) const {
assert(active);
return node_type::fold(p, keyL, keyR, include_left, include_right);
}
std::pair< Key, T > get_min() const {
assert(active);
return p->get_min();
}
std::pair< Key, T > get_max() const {
assert(active);
return p->get_max();
}
size_type count(Key l, Key r) const {
assert(active);
return node_type::count(p, l, r, 1, 0);
}
size_type count(Key l, Key r, bool include_left, bool include_right) const {
assert(active);
return node_type::count(p, l, r, include_left, include_right);
}
size_type count_lesser(Key key, bool include_bound) const {
assert(active);
return node_type::count_lesser(p, key, include_bound);
}
size_type count_greater(Key key, bool include_bound) const {
assert(active);
return node_type::count_greater(p, key, include_bound);
}
Key select(size_type k) const {
assert(active);
assert(k < size());
return p->select(k);
}
WeightBalancedTree &union_with(WeightBalancedTree &&a) {
assert(active && a.active);
a.active = 0;
p = node_type::unionL(p, a.p);
return *this;
}
using touch_func = std::function< void(Key key, T &v, T &accum, bool eq) >;
static touch_func touch_default;
void touch_path_to(const Key &target, const touch_func &touch) {
assert(active);
node_type::touch_path_to(p, target, touch);
}
size_type size() const {
assert(active);
return p->sz;
}
bool empty() const {
assert(active);
return p == node_type::get_NIL();
}
};
template < class Key, class M_act >
typename WeightBalancedTree< Key, M_act >::touch_func
WeightBalancedTree< Key, M_act >::touch_default = [](...) {};
// }}}
}
template < class Key, class M_act >
using WBT = wbt::WeightBalancedTree< Key, M_act >;
/// --- RangeMedianWithUpdate {{{ ///
#include <ostream>
namespace wbt {
template < class _T, class _Monoid, class Index = long long >
struct RangeMedianWithUpdate {
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;
}
};
struct RMWU_Monoid {
using T = WeightBalancedTree< Point, Nothing_M_act<Monoid> >;
static T op(T a, T b) { return a.union_with(std::move(b)); }
static T identity() { return T(); }
};
struct RMWU_M_act {
using Monoid = RMWU_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 T_SET = typename RMWU_Monoid::T;
using WBT = WeightBalancedTree< T, RMWU_M_act >;
using pointer = typename WBT::pointer;
using const_pointer = typename WBT::const_pointer;
WeightBalancedTree< T, RMWU_M_act > wbt;
RangeMedianWithUpdate() {}
template < class InputIter,
class = typename std::iterator_traits< InputIter >::value_type >
RangeMedianWithUpdate(InputIter first, InputIter last) {
auto ite = first;
for(size_type i = 0; ite != last; ++ite, ++i) {
wbt.insert(*ite);
}
for(size_type i = 0; first != last; ++first, ++i) {
auto v = *first;
insert_path_to(wbt.p, v, Point(i, v), Monoid::identity(), 1);
}
}
RangeMedianWithUpdate(std::initializer_list< std::pair< Index, T > > il)
: RangeMedianWithUpdate(il.begin(), il.end()) {}
void insert(Index i, T v, X x, bool is_identity = 0) {
wbt.insert(v);
insert_path_to(wbt.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(wbt.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(t != WBT::node_type::get_NIL()) {
if(target < t->key) {
pts.push_back(t);
t = t->l;
} else if(t->key < target) {
pts.push_back(t);
t = t->r;
} 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(t != WBT::node_type::get_NIL()) {
if(target < t->key) {
pts.push_back(t);
t = t->l;
} else if(t->key < target) {
pts.push_back(t);
t = t->r;
} 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 = wbt.p;
while(p != WBT::node_type::get_NIL()) {
if(p->key < l || (!include_l && !(l < p->key))) p = p->r;
else if(r < p->key || (!include_r && !(p->key < r))) p = p->l;
else break;
}
if(p == WBT::node_type::get_NIL()) return Monoid::identity();
X x = p->value.fold(i, j);
const_pointer pl = p->l, pr = p->r;
while(pl != WBT::node_type::get_NIL()) {
if(pl->key < l) {
pl = pl->r;
} else {
x = Monoid::op(pl->r->accum.fold(i, j), x);
if(l < pl->key) {
x = Monoid::op(pl->value.fold(i, j), x);
pl = pl->l;
} else {
if(include_l) x = Monoid::op(pl->value.fold(i, j), x);
break;
}
}
}
while(pr != WBT::node_type::get_NIL()) {
if(r < pr->key) {
pr = pr->l;
} else {
x = Monoid::op(x, pr->l->accum.fold(i, j));
if(pr->key < r) {
x = Monoid::op(x, pr->value.fold(i, j));
pr = pr->r;
} else {
if(include_r) x = Monoid::op(x, pr->value.fold(i, j));
break;
}
}
}
return x;
}
Point range_select(Index i, Index j, size_type k) const {
return range_select_dfs(wbt.p, i, j, k);
}
size_type range_count_smaller(Index i, Index j, T x, bool include_bound) const {
return range_count_smaller_dfs(wbt.p, i, j, x, include_bound);
}
private:
Point range_select_dfs(const_pointer p, Index i, Index j, size_type k) const {
assert(p != WBT::node_type::get_NIL());
assert(k < p->accum.count(i, j));
size_type lsz = p->l->accum.count(i, j);
if(k < lsz) {
return range_select_dfs(p->l, 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);
}
k -= hsz;
return range_select_dfs(p->r, i, j, k);
}
size_type range_count_smaller_dfs(const_pointer p, Index i, Index j, T x,
bool include_bound) const {
if(p == WBT::node_type::get_NIL()) return 0;
if(x < p->key) return range_count_smaller_dfs(p->l, i, j, x, include_bound);
// p->key <= x
size_type lsz = p->l->accum.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->r, 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 wbt.p->accum.count(i, j); }
size_type size() const { return wbt.p->accum.size(); }
};
}
/// }}}--- ///
template < class T, class Monoid, class Index = long long >
using RangeMedianWithUpdate = wbt::RangeMedianWithUpdate< T, Monoid, Index >;
constexpr int N = 1 << 16;
constexpr int Q = 1 << 16;
constexpr ll inf = 1ll << 40; // 1e12
int n, q;
ll t[Q], l[Q], r[Q];
ll med[Q], smaller[Q], bigger[Q];
int main() {
std::ios::sync_with_stdio(false), std::cin.tie(0);
cin >> n >> q;
assert(0 <= n && n < N);
assert(0 <= q && q < Q);
vector< ll > v(n + 1);
RangeMedianWithUpdate< ll, RangeSum<ll> > rm;
for(int i = 1; i <= n; i++) {
cin >> v[i];
rm.insert(i, v[i], v[i]);
assert(0 <= v[i] && v[i] < inf);
}
for(int i = 0; i < q; i++) cin >> t[i] >> l[i] >> r[i];
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);
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]);
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 % (1 << 16);
sum40 ^= z % (1ll << 40);
cout << z << "\n";
cout << flush;
}
}
return 0;
}