結果
| 問題 | No.925 紲星 Extra |
| ユーザー |
 lumc_
|
| 提出日時 | 2019-09-15 03:09:52 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 42,338 bytes |
| コンパイル時間 | 5,843 ms |
| コンパイル使用メモリ | 191,404 KB |
| 実行使用メモリ | 816,480 KB |
| 最終ジャッジ日時 | 2024-09-15 05:37:00 |
| 合計ジャッジ時間 | 77,085 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | RE | - |
| testcase_01 | RE | - |
| testcase_02 | RE | - |
| testcase_03 | RE | - |
| testcase_04 | RE | - |
| testcase_05 | MLE | - |
| testcase_06 | MLE | - |
| testcase_07 | MLE | - |
| testcase_08 | MLE | - |
| testcase_09 | MLE | - |
| testcase_10 | MLE | - |
| testcase_11 | MLE | - |
| testcase_12 | MLE | - |
| testcase_13 | MLE | - |
| testcase_14 | MLE | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
ソースコード
// 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();
}
std::pair< T, bool > lookup(Key key) const {
if(this == get_NIL()) return std::pair< T, bool >(Monoid::identity(), 0);
if(key < this->key) {
// delete p ?
return l->lookup(key);
} else if(this->key < key) {
return r->lookup(key);
} else {
return std::pair< T, bool >(value, 1);
}
}
static pointer copy(pointer a) {
if(a == get_NIL()) return get_NIL();
return make(a->key, a->value, copy(a->l), copy(a->r));
}
size_type count(const Key &keyL, const Key &keyR, bool include_left,
bool include_right) {
if(this == get_NIL()) return 0;
if(!(keyL < key)) {
// key <= keyL
if(include_left && !(key < keyL)) return 1 + r->count_lesser(keyR, include_right);
return r->count(keyL, keyR, include_left, include_right);
}
if(!(key < keyR)) {
// keyR <= key
if(include_right && !(keyR < key)) return 1 + l->count_greater(keyL, include_left);
return l->count(keyL, keyR, include_left, include_right);
}
// keyL < key < keyR
return l->count_greater(keyL, include_left) + 1 +
r->count_lesser(keyR, include_right);
}
size_type count_lesser(const Key &keyR, bool include_bound) {
if(this == get_NIL()) return 0;
if(key < keyR) return l->sz + 1 + r->count_lesser(keyR, include_bound);
// keyR <= key
if(include_bound && !(keyR < key)) return l->sz + 1;
return l->count_lesser(keyR, include_bound);
}
size_type count_greater(const Key &keyL, bool include_bound) {
if(this == get_NIL()) return 0;
if(keyL < key) return l->count_greater(keyL, include_bound) + 1 + r->sz;
// key <= keyL
if(include_bound && !(key < keyL)) return 1 + r->sz;
return r->count_greater(keyL, include_bound);
}
static pointer insert(pointer p, Key key, const T &value) {
if(p == get_NIL()) return make_singleton(key, value);
if(key < p->key) {
pointer q = balanceR(std::move(p->key), std::move(p->value), insert(p->l, key, value), p->r);
// delete p;
return q;
} else if(p->key < key) {
pointer q = balanceL(std::move(p->key), std::move(p->value), p->l, insert(p->r, key, value));
// delete p;
return q;
} else {
return p;
}
}
static pointer insert_identity(pointer p, Key key) {
if(p == get_NIL()) return make_singleton(key, Monoid::identity());
if(key < p->key) {
pointer q = balanceR(std::move(p->key), std::move(p->value), std::move(p->accum), insert_identity(p->l, key), p->r);
// delete p;
return q;
} else if(p->key < key) {
pointer q = balanceL(std::move(p->key), std::move(p->value), std::move(p->accum), p->l, insert_identity(p->r, key));
// delete p;
return q;
} else {
return p;
}
}
static pointer erase(pointer p, Key key) {
if(p == get_NIL()) return get_NIL();
if(key < p->key) {
pointer q = balanceL(p->key, p->value, erase(p->l, key), p->r);
// delete p;
return q;
} else if(p->key < key) {
pointer q = balanceR(p->key, p->value, p->l, erase(p->r, key));
// delete p;
return q;
} else {
pointer q = glue(p->l, p->r);
// delete p;
return q;
}
}
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) {
Key k2;
T v2;
pointer l2;
std::tie(k2, v2, l2) = delete_find_max(l);
return balanceL(k2, v2, l2, r);
} else {
Key k2;
T v2;
pointer r2;
std::tie(k2, v2, r2) = delete_find_min(r);
return balanceR(k2, v2, l, r2);
}
}
// BST basic operations {{{
static pointer merge(pointer l, Key k, T v, pointer r) {
if(l == get_NIL()) return insert(r, k, v); // TODO : optimize
if(r == get_NIL()) return insert(l, k, v); // 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) {
return balanceL(l->key, l->value, l->l, merge(l->r, k, v, r));
} else {
return balanceR(r->key, r->value, merge(l, k, v, r->l), r->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);
return std::tuple< pointer, bool, pointer >(
l2, erased, merge(r2, a->key, a->value, a->r));
// TODO : make it faster
} else if(a->key < k) {
std::tie(l2, erased, r2) = split(a->r, k, right);
return std::tuple< pointer, bool, pointer >(
merge(a->l, a->key, a->value, l2), erased, r2);
// TODO : make it faster
}
return std::tuple< pointer, bool, pointer >(
!right ? insert(a->l, a->key, a->value) : a->l, 1,
right ? insert(a->r, a->key, a->value) : a->r);
}
// }}}
// 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);
return merge(unionL(t1->l, t_lesser), t1->key, t1->value, unionL(t1->r, t_greater));
}
// }}}
using DP = std::tuple< Key, T, pointer >; // Data and Pointer
static DP delete_find_max(pointer p) {
assert(p != get_NIL());
if(p->r == get_NIL()) {
DP res(p->key, p->value, p->l);
// delete p;
return res;
} else {
Key k;
T v;
pointer r2;
std::tie(k, v, r2) = delete_find_max(p->r);
// delete p;
return DP(k, v, balance(p->key, p->value, p->l, r2));
}
}
static DP delete_find_min(pointer p) {
assert(p != get_NIL());
if(p->l == get_NIL()) {
DP res(p->key, p->value, p->r);
// delete p;
return res;
} else {
Key k;
T v;
pointer l2;
std::tie(k, v, l2) = delete_find_min(p->l);
// delete p;
return DP(k, v, balance(p->key, p->value, l2, p->r));
}
}
static pointer balanceL(Key key, const T &value, pointer l, pointer r) {
if(is_balanced(l, r)) return make(key, value, l, r);
return rotateL(key, value, l, r);
}
static pointer balanceR(Key key, const T &value, pointer l, pointer r) {
if(is_balanced(r, l)) return make(key, value, l, r);
return rotateR(key, value, l, r);
}
static pointer balanceL(Key &&key, T &&value, T && accum, pointer l, pointer r) {
if(is_balanced(l, r)) return make(std::move(key), std::move(value), std::move(accum), l, r);
return rotateL(key, value, l, r);
}
static pointer balanceR(Key &&key, T &&value, T && accum, pointer l, pointer r) {
if(is_balanced(r, l)) return make(std::move(key), std::move(value), std::move(accum), l, r);
return rotateR(key, value, l, r);
}
static pointer rotateL(Key key, const T &value, pointer l, pointer r) {
const pointer rl = r->l, rr = r->r;
if(is_single(rl, rr)) return singleL(key, value, l, r);
return doubleL(key, value, l, r);
}
static pointer rotateR(Key key, const T &value, pointer l, pointer r) {
const pointer ll = l->l, lr = l->r;
if(is_single(lr, ll)) return singleR(key, value, l, r);
return doubleR(key, value, l, r);
}
static pointer singleL(Key k1, const T &v1, pointer l, pointer r) {
const Key &k2 = r->key;
const T &v2 = r->value;
pointer t1 = l, t2 = r->l, t3 = r->r;
return make(k2, v2, make(k1, v1, t1, t2), t3);
}
static pointer singleR(Key k1, const T &v1, pointer l, pointer r) {
const Key &k2 = l->key;
const T &v2 = l->value;
pointer t1 = l->l, t2 = l->r, t3 = r;
return make(k2, v2, t1, make(k1, v1, t2, t3));
}
static pointer doubleL(Key k1, const T &v1, pointer l, pointer r) {
const Key &k2 = r->key, &k3 = r->l->key;
const T &v2 = r->value, &v3 = r->l->value;
pointer t1 = l, t2 = r->l->l, t3 = r->l->r, t4 = r->r;
return make(k3, v3, make(k1, v1, t1, t2), make(k2, v2, t3, t4));
}
static pointer doubleR(Key k1, const T &v1, pointer l, pointer r) {
Key &k2 = l->key, &k3 = l->r->key;
const T &v2 = l->value, &v3 = l->r->value;
pointer t1 = l->l, t2 = l->r->l, t3 = l->r->r, t4 = r;
return make(k3, v3, make(k2, v2, t1, t2), make(k1, v1, t3, t4));
}
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 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 pointer make(Key key, T &&value, pointer l, pointer r) {
// pointer p = new WeightBalancedTreeNode;
// p->sz = l->sz + r->sz + 1;
// p->key = key;
// p->value = std::move(value);
// p->accum = Monoid::op(Monoid::op(l->accum, value), r->accum);
// p->l = l;
// p->r = r;
// return p;
// }
std::pair< Key, T > get_min() const {
assert(this != get_NIL());
if(l == get_NIL()) return std::pair< Key, T >(key, value);
return l->get_min();
}
std::pair< Key, T > get_max() const {
assert(this != get_NIL());
if(r == get_NIL()) return std::pair< Key, T >(key, value);
return r->get_max();
}
std::pair< std::pair< Key, T >, bool > get_min(Key keyL, bool include_bound) const {
if(this == get_NIL()) return std::pair< std::pair< Key, T >, bool >();
if(keyL < key) {
auto res = l->get_min(keyL, include_bound);
if(res.second) return res;
return std::pair< std::pair< Key, T >, bool >(std::pair< Key, T >(key, value), 1);
}
// keyR <= key
if(include_bound && !(key < keyL))
return std::pair< std::pair< Key, T >, bool >(std::pair< Key, T >(key, value), 1);
return r->get_max(keyL, include_bound);
}
std::pair< std::pair< Key, T >, bool > get_max(Key keyR, bool include_bound) const {
if(this == get_NIL()) return std::pair< std::pair< Key, T >, bool >();
if(key < keyR) {
auto res = r->get_max(keyR, include_bound);
if(res.second) return res;
return std::pair< std::pair< Key, T >, bool >(std::pair< Key, T >(key, value), 1);
}
// keyR <= key
if(include_bound && !(keyR < key))
return std::pair< std::pair< Key, T >, bool >(std::pair< Key, T >(key, value), 1);
return l->get_max(keyR, include_bound);
}
void get_all_dfs(std::vector< std::pair< Key, T > > &res) {
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) >;
using find_func = std::function< int(Key key, T &v, T &accum) >;
using check_func = std::function< bool(Key key, T &v, T &accum) >;
// bottom up
bool touch_finding(const find_func &find, const touch_func &touch) {
if(this == get_NIL()) return 0;
int ch = find(key, value, accum);
assert(ch == -1 || ch == 0 || ch == +1);
if(ch == 0) {
touch(key, value, accum, 1);
return 1;
}
bool found;
if(ch == -1) {
found = l->touch_finding(find, touch);
} else {
found = r->touch_finding(find, touch);
}
if(found) touch(key, value, accum, 0);
return found;
}
// bool touch_path_to(const Key &target, const touch_func &touch) {
// return touch_finding(
// [target](
// Key key, ...) -> int { return key < target ? +1 : target < key ? -1 : 0; },
// touch);
// }
bool touch_path_to(const Key &target, const touch_func &touch) {
if(this == get_NIL()) return 0;
bool found;
if(target < key) {
found = l->touch_path_to(target, touch);
} else if(key < target) {
found = r->touch_path_to(target, touch);
} else {
touch(key, value, accum, 1);
return 1;
}
if(found) touch(key, value, accum, 0);
return found;
}
};
// }}}
// 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) {
assert(active);
*this = wbt;
}
WeightBalancedTree(WeightBalancedTree &&wbt) {
assert(active);
*this = std::move(wbt);
}
WeightBalancedTree &operator=(const WeightBalancedTree &wbt) {
// if(p->sz >= 100) dump(p->sz, "copy");
// dump(p->sz, "copy");
p = node_type::copy(wbt.p);
return *this;
}
WeightBalancedTree &operator=(WeightBalancedTree &&wbt) {
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);
}
void insert(Key key) {
assert(active);
p = node_type::insert_identity(p, key);
}
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 p->lookup(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) 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();
}
std::pair< std::pair< Key, T >, bool > get_min(T l, bool include_bound) const {
assert(active);
return p->get_min(l, include_bound);
}
std::pair< std::pair< Key, T >, bool > get_max(T r, bool include_bound) const {
assert(active);
return p->get_max(r, include_bound);
}
size_type count(Key l, Key r, bool include_left = 1, bool include_right = 0) const {
assert(active);
return p->count(l, r, include_left, include_right);
}
size_type count_lesser(Key key, bool include_bound) const {
assert(active);
return p->count_lesser(key, include_bound);
}
size_type count_greater(Key key, bool include_bound) const {
assert(active);
return p->count_greater(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;
pointer q = node_type::unionL(p, a.p);
WeightBalancedTree res(q);
return res;
}
using touch_func = std::function< void(Key key, T &v, T &accum, bool eq) >;
using find_func = std::function< int(Key key, T &v, T &accum) >;
using check_func = std::function< bool(Key key, T &v, T &accum) >;
static touch_func touch_default;
void touch_finding(const find_func &find, const touch_func &touch) {
assert(active);
p->touch_finding(find, touch);
}
void touch_path_to(const Key &target, const touch_func &touch) {
assert(active);
p->touch_path_to(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 >;
ll GCNT = 0;
/// --- 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 GCNT += a.size() + b.size(), 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) {
// if(i % 1000 == 0) dump(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));
});
// if(i % 1000 == 0) dump(i, cnt);
}
}
void insert(Index i, T v) {
ll cnt = -GCNT;
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));
});
cnt += GCNT;
// dump(cnt);
}
bool erase(Index i, T v) {
bool erased = 0;
// dump(Point(i, v));
wbt.touch_path_to(v, [&erased, i, v](T, T_SET &x, T_SET &accum, bool eq) {
// dump(eq, x.get_all());
// dump(accum.get_all());
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);
// dump(p->sz, k);
// dump(c, p->l->sz);
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;
// dump(x, p->key);
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 {
// dump(wbt.p->accum.get_all());
// dump(i, j);
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;
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
);
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);
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]);
// dump(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];
}
cout << z << "\n";
}
}
return 0;
}