結果
| 問題 |
No.925 紲星 Extra
|
| コンテスト | |
| ユーザー |
 lumc_
|
| 提出日時 | 2019-09-15 10:23:26 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
RE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 39,844 bytes |
| コンパイル時間 | 3,778 ms |
| コンパイル使用メモリ | 198,180 KB |
| 実行使用メモリ | 106,856 KB |
| 最終ジャッジ日時 | 2024-09-15 05:39:18 |
| 合計ジャッジ時間 | 15,112 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | RE * 3 |
| other | RE * 19 |
ソースコード
// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
#include<bitset>
#include<cstdlib>
// #include<deque>
// #include<multiset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;
#define DEBUG_OUT std::cerr
// #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 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 size_type count(const_pointer p, const Key &keyL, const Key &keyR,
bool include_left, bool include_right) {
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, const T &value, bool weak_update) {
if(p == get_NIL()) return make_singleton(key, value);
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 {
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, weak_update);
if(is_left) {
balanceR(q);
} else {
balanceL(q);
}
}
return p;
}
static pointer erase(pointer p, Key key) {
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;
}
}
return p;
}
Key select(size_type k) const {
assert(this != get_NIL());
if(l->sz) return l->select(k);
k -= l->sz;
if(k == 0) return key;
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) {
if(l == get_NIL()) return insert(r, k, v, 0); // TODO : optimize
if(r == get_NIL()) return insert(l, k, v, 0); // TODO : optimize
bool bal1 = is_balanced(l, r);
bool bal2 = is_balanced(r, l);
if(bal1 && bal2) {
return make(k, v, l, r);
} else if(bal1) {
l->r = merge(l->r, k, v, r);
balanceL(l);
return l;
} else {
r->l = merge(l, k, v, r->l);
balanceR(r);
return r;
}
}
static std::tuple< pointer, bool, pointer > split(pointer a, Key k, bool right) {
if(a == get_NIL())
return std::tuple< pointer, bool, pointer >(get_NIL(), 0, get_NIL());
pointer l2, r2;
bool erased;
if(k < a->key) {
std::tie(l2, erased, r2) = split(a->l, k, right);
auto res = std::tuple< pointer, bool, pointer >(
l2, erased, merge(r2, a->key, a->value, a->r));
delete a;
return res;
// TODO : make it faster
} else if(a->key < k) {
std::tie(l2, erased, r2) = split(a->r, k, right);
auto res = std::tuple< pointer, bool, pointer >(
merge(a->l, a->key, a->value, l2), erased, r2);
delete a;
return res;
// TODO : make it faster
}
auto res = std::tuple< pointer, bool, pointer >(
!right ? insert(a->l, a->key, a->value, 0) : a->l, 1,
right ? insert(a->r, a->key, a->value, 0) : a->r);
delete a;
return res;
}
// }}}
// set operations {{{
static pointer unionL(pointer t1, pointer t2) {
if(t1 == get_NIL()) return t2;
if(t2 == get_NIL()) return t1;
pointer t_lesser, t_greater;
std::tie(t_lesser, std::ignore, t_greater) = split(t2, t1->key, 0);
pointer q =
merge(unionL(t1->l, t_lesser), t1->key, 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();
p->sz = 1;
return PP(q, p);
}
pointer t = p;
while(1) {
if(t->r->r == get_NIL()) {
pointer q = t->r;
t->r = q->l;
q->l = get_NIL();
--t->sz;
q->sz = 1;
return PP(p, q);
} else {
--t->sz;
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();
p->sz = 1;
return PP(q, p);
}
pointer t = p;
while(1) {
if(t->l->l == get_NIL()) {
pointer q = t->l;
t->l = q->r;
q->r = get_NIL();
--t->sz;
q->sz = 1;
return PP(p, q);
} else {
--t->sz;
t = t->l;
}
}
}
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 = Monoid::identity();
p->l = p;
p->r = p;
return p;
}
static pointer make_singleton(Key key, const T &value) {
pointer p = new WeightBalancedTreeNode;
p->sz = 1;
p->key = key;
p->accum = p->value = value;
p->l = get_NIL();
p->r = get_NIL();
return p;
}
static pointer make(Key key, const T &value, pointer l, pointer r) {
pointer p = new WeightBalancedTreeNode;
p->sz = l->sz + r->sz + 1;
p->key = key;
p->value = value;
p->accum = Monoid::op(Monoid::op(l->accum, value), r->accum);
p->l = l;
p->r = r;
return p;
}
static void update(pointer p, bool weak_update = 0) {
p->sz = p->l->sz + p->r->sz + 1;
if(!weak_update)
p->accum = Monoid::op(Monoid::op(p->l->accum, p->value), p->r->accum);
}
static pointer make(Key key, const T &value, const T &accum, pointer l, pointer r) {
pointer p = new WeightBalancedTreeNode;
p->sz = l->sz + r->sz + 1;
p->key = key;
p->value = value;
p->accum = 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;
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;
}
}
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, const T &value) {
assert(active);
p = node_type::insert(p, key, value, 0);
}
void insert(Key key) {
assert(active);
p = node_type::insert(p, 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;
}
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, bool include_left = 1, bool include_right = 0) 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;
active = 0;
return WeightBalancedTree(node_type::unionL(p, a.p));
}
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 Index = long long >
struct RangeMedianWithUpdate {
using size_type = std::size_t;
using T = _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 y < a.y;
}
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 >;
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 >;
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;
wbt.touch_path_to(v, [i, v](T, T_SET &x, T_SET &accum, bool eq) -> void {
if(eq) x.insert(Point(i, v));
accum.insert(Point(i, v));
});
}
}
void insert(Index i, T v) {
wbt.insert(v);
wbt.touch_path_to(v, [i, v](T, T_SET &x, T_SET &accum, bool eq) -> void {
if(eq) x.insert(Point(i, v));
accum.insert(Point(i, v));
});
}
bool erase(Index i, T v) {
bool erased = 0;
wbt.touch_path_to(v, [&erased, i, v](T, T_SET &x, T_SET &accum, bool eq) {
if(eq) erased = x.erase(Point(i, v));
accum.erase(Point(i, v));
});
return erased;
}
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(typename WBT::const_pointer p, Index i, Index j,
size_type k) const {
assert(p != WBT::node_type::get_NIL());
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(typename WBT::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 Index = long long >
using RangeMedianWithUpdate = wbt::RangeMedianWithUpdate< T, Index >;
// .add(i, v) : bit[i] += v
// .get(i) : bit[i]
// .sum(i) : bit[0] + ... + bit[i]
// .range(l, r) : bit[l] + ... + bit[r]
// .lower_bound(T v) : min i that satisfies .sum(i) >= v
// - use only when bit[i] >= 0 for all i > 0
/// --- Binary Indexed Tree {{{ ///
#include <cassert>
#include <vector>
template < class T = long long >
struct BinaryIndexedTree {
using size_type = std::size_t;
size_type n, m;
T identity;
std::vector< T > data;
BinaryIndexedTree() : n(0) {}
BinaryIndexedTree(size_type n, T identity = T())
: n(n), identity(identity), data(n, identity) {
m = 1;
while(m < n) m <<= 1;
}
void add(size_type i, T x) {
assert(i < n);
i++;
while(i <= n) {
data[i - 1] = data[i - 1] + x;
i += i & -i;
}
}
T sum(int i) {
if(i < 0) return identity;
if(i >= static_cast<int>(n)) i = n - 1;
i++;
T s = identity;
while(i > 0) {
s = s + data[i - 1];
i -= i & -i;
}
return s;
}
T get(int i) { return sum(i) - sum(i - 1); }
T range(int a, int b) { return sum(b) - sum(a - 1); }
size_type lower_bound(T w) {
size_type i = 0;
for(size_type k = m; k > 0; k >>= 1) {
if(i + k <= n && data[i + k - 1] < w) w -= data[(i += k) - 1];
}
return i;
}
};
/// }}}--- ///
template < class T = long long >
using BIT = BinaryIndexedTree< T >;
// FractionalCascadingSegmentTree
// < Under, Data [, yCompress = 1 [, Index] ] >(H, ...)
// .index(y, x)
// === init(doUnique) ===
// .set(y, x, val) // index(y, x) must be done
// .fold(yl, yr, xl, xr)
// .fold(y, x)
// === --- ===
// only offline
/// --- Fractional Cascading SegmentTree {{{ ///
#include <algorithm>
#include <cassert>
#include <functional>
#include <map>
#include <vector>
template < class T, class U, bool yCompress = true, class Index = ll >
struct FractionalCascadingSegmentTree {
size_t h;
vector< T > dat;
vector< vector< Index > > indices;
vector< vector< size_t > > L, R;
U identity;
function< void(T &, int x, const U &) > setX;
function< void(T &, vector< Index > &) > initX;
function< U(T &, int x1, int x2) > foldX;
function< U(const U &, const U &) > mergeY;
FractionalCascadingSegmentTree() {}
FractionalCascadingSegmentTree(size_t tempH, //
const function< void(T &, int, const U &) > &setX,
const function< void(T &, vector< Index > &) > &initX,
const function< U(T &, int, int) > &foldX,
const function< U(const U &, const U &) > &mergeY,
U identity = U(), T initial = T())
: identity(identity), setX(setX), initX(initX), foldX(foldX), mergeY(mergeY) {
h = 1;
while(h < tempH) h <<= 1;
dat = vector< T >(2 * h, initial);
indices = vector< vector< Index > >(2 * h);
L = R = vector< vector< size_t > >(2 * h);
}
vector< Index > ys;
map< Index, int > ymap;
vector< pair< Index, Index > > pre_indecies;
void index(Index i, Index j) {
if(yCompress) {
ys.push_back(i);
pre_indecies.emplace_back(i, j);
} else {
size_t i2 = i;
assert(i2 < h);
indices[i2 + h].push_back(j);
}
}
void init(bool doUnique) {
if(yCompress) {
sort(begin(ys), end(ys));
ys.erase(unique(begin(ys), end(ys)), end(ys));
{
size_t i = 0;
for(Index &y : ys) ymap[y] = i++;
}
for(pair< Index, Index > idx : pre_indecies) {
indices[ymap[idx.first] + h].push_back(idx.second);
}
}
for(size_t i = h; i < h * 2; i++) {
sort(begin(indices[i]), end(indices[i]));
if(doUnique)
indices[i].erase(unique(begin(indices[i]), end(indices[i])), end(indices[i]));
initX(dat[i], indices[i]);
}
for(size_t i = h - 1; i >= 1; i--) {
size_t lsz = indices[i * 2].size();
size_t rsz = indices[i * 2 + 1].size();
size_t nsz = lsz + rsz;
indices[i].resize(nsz);
L[i].resize(nsz + 1, lsz);
R[i].resize(nsz + 1, rsz);
size_t p1 = 0, p2 = 0;
while(p1 < lsz || p2 < rsz) {
L[i][p1 + p2] = p1;
R[i][p1 + p2] = p2;
if(p1 < lsz && (p2 == rsz || indices[i * 2][p1] <= indices[i * 2 + 1][p2])) {
indices[i][p1 + p2] = indices[i * 2][p1];
p1++;
} else {
indices[i][p1 + p2] = indices[i * 2 + 1][p2];
p2++;
}
}
initX(dat[i], indices[i]);
}
}
public:
void set(Index y, Index x, const U &val) {
if(yCompress) {
assert(ymap.count(y));
_set(ymap[y], x, val);
} else {
size_t y2 = y;
assert(y2 < h);
_set(y2, x, val);
}
}
private:
void _set(size_t y, Index x, const U &val) {
size_t lower = lower_bound(begin(indices[1]), end(indices[1]), x) - begin(indices[1]);
assert(lower < indices.size());
size_t k = 1, l = 0, r = h;
while(k != y + h) {
setX(dat[k], lower, val);
size_t mid = (l + r) >> 1;
if(y < mid) {
lower = L[k][lower];
k = k * 2;
r = mid;
} else {
lower = R[k][lower];
k = k * 2 + 1;
l = mid;
}
}
setX(dat[k], lower, val);
assert(indices[k][lower] == x);
}
public:
U fold(Index y, Index x) { return fold(y, y + Index(1), x, x + Index(1)); }
U fold(Index a, Index b, Index l, Index r) {
if(a >= b || l >= r) return identity;
size_t lower = lower_bound(begin(indices[1]), end(indices[1]), l) - begin(indices[1]);
size_t upper = lower_bound(begin(indices[1]), end(indices[1]), r) - begin(indices[1]);
size_t a2, b2;
if(yCompress) {
a2 = lower_bound(begin(ys), end(ys), a) - begin(ys);
b2 = lower_bound(begin(ys), end(ys), b) - begin(ys);
} else {
a2 = a, b2 = b;
assert(a2 < h && b2 <= h);
}
return fold(a2, b2, lower, upper, 0, h, 1);
}
private:
U fold(size_t a, size_t b, size_t lower, size_t upper, size_t l, size_t r, size_t k) {
if(lower == upper) return identity;
if(b <= l || r <= a) return identity;
if(a <= l && r <= b) return foldX(dat[k], lower, upper);
return mergeY(fold(a, b, L[k][lower], L[k][upper], l, (l + r) >> 1, k * 2),
fold(a, b, R[k][lower], R[k][upper], (l + r) >> 1, r, k * 2 + 1));
}
};
/// }}}--- ///
constexpr int N = 4e5;
constexpr int Q = 4e5;
using Under = BIT<>;
using Value = ll;
using Data = ll;
constexpr int inf = 1e9;
int n, q;
int t[Q], l[Q], r[Q];
int med[Q], smaller[Q], bigger[Q];
int main() {
std::ios::sync_with_stdio(false), std::cin.tie(0);
cin >> n >> q;
vector<int> v(n);
FractionalCascadingSegmentTree< Under, Data, 1 > ecas(
n + q + 1,
// set x
[](Under &dat, int x, const Data &val) -> void {
// dat.add(x, -dat.get(x) + val);
dat.add(x, val);
},
// init x
[](Under &dat, const vector< ll > &indices) -> void {
dat = Under(indices.size()); // serve initial?
},
// fold [l, r) // l < r
[](Under &dat, int l, int r) -> Data { return dat.range(l, r - 1); },
// merge y-direction
[](Data a, Data b) -> Data { return a + b; }
// optional identity
// , identity
);
for(auto &e: v) cin >> e;
for(int i = 0; i < q; i++) cin >> t[i] >> l[i] >> r[i], l[i]--;
for(int i = 0; i < n; i++) ecas.index(v[i], i);
auto w = v;
dump(1);
RangeMedianWithUpdate<int> rm(begin(v), end(v));
dump(2);
for(int i = 0; i < q; i++) {
if(t[i] == 1) { // update
rm.erase(l[i], w[l[i]]);
rm.insert(l[i], r[i]);
w[l[i]] = r[i];
ecas.index(r[i], l[i]);
} else { // query
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] = r[i] - l[i] - rm.range_count_smaller(l[i], r[i], med[i], 1);
}
}
dump(3);
ecas.init(1);
dump(4);
for(int i = 0; i < n; i++) ecas.set(v[i], i, v[i]);
dump(5);
for(int i = 0; i < q; i++) {
if(t[i] == 1) { // update
ecas.set(v[l[i]], l[i], -v[l[i]]);
ecas.set(r[i], l[i], r[i]);
v[l[i]] = r[i];
} else { // query
ll z = -ecas.fold(-inf, med[i], l[i], r[i]) + ecas.fold(med[i] + 1, inf, l[i], r[i]);
// dump(ecas.fold(-inf, med[i], l[i], r[i]));
int len = r[i] - l[i];
// dump(len);
// dump(len / 2, smaller[i], len / 2 - smaller[i]);
// dump(len - len / 2, bigger[i], len - len / 2 - bigger[i]);
// dump(med[i]);
// dump(v[l[i]], v[l[i] + 1], v[l[i] + 2]);
z -= ll(len / 2 - smaller[i]) * med[i];
z += ll((len - len / 2) - bigger[i]) * med[i];
// dump(smaller[i], bigger[i]);
if(len % 2 == 0) {
} else {
z -= med[i];
}
// if(i % 100 == 0) {
// ll z2 = 0;
// for(int j = l[i]; j < r[i]; j++) z2 += abs(v[j] - med[i]);
// assert(z2 == z);
// }
cout << z << "\n";
}
}
return 0;
}