#if 0 dynamic seg on dynamic seg + 二分探索 かなりおそそうなので差別化できそう? #endif // includes {{{ #include #include #include #include #include #include #include #include #include #include #include #include #include #include // #include // #include // #include // #include // }}} using namespace std; using ll = long long; constexpr int inf = 1e9; // - scalable // DynamicSegmentTree([ ]) // - fixed-range // DynamicSegmentTree(L, R [, ]) // DynamicSegmentTree(size [, ]) // === initial values === // := one value or function // when you feed initial-one-value : O(log^2 N) time / query // when you feed initial-function // : O(timeof(f(l, r)) log N) time / query // === --- === // NOTE : one value is recommended rather than O(log SIZE) function // NOTE : better to use fixed-range /// --- Dynamic SegmentTree {{{ /// #include #include #include template < class Monoid > struct DynamicSegmentTreeNode { public: using T = typename Monoid::T; using node_type = DynamicSegmentTreeNode; using pointer = node_type *; T value; pointer l = 0, r = 0; DynamicSegmentTreeNode(T value = Monoid::identity()) : value(value) {} DynamicSegmentTreeNode(pointer l, pointer r) : l(l), r(r) {} }; template < class Monoid, class Allocator = std::allocator< DynamicSegmentTreeNode< Monoid > > > struct DynamicSegmentTree { public: using T = typename Monoid::T; using size_type = long long; using node_type = DynamicSegmentTreeNode< Monoid >; using pointer = node_type *; using func_type = std::function< T(size_type l, size_type r) >; private: static Allocator alc; pointer top = 0; // it should be only given positive length ranges func_type get_initial = [](...) { return Monoid::identity(); }; const bool range_fixed; size_type L, R; void expand(size_type t) { assert(!range_fixed); while(t < L || R <= t) { if(R == static_cast< size_type >(0)) R = 1; else { R <<= 1; if(top) { pointer new_l = 0, new_r = 0; if(top->l) std::allocator_traits< Allocator >::construct( alc, new_l = alc.allocate(1), nullptr, top->l); if(top->r) std::allocator_traits< Allocator >::construct( alc, new_r = alc.allocate(1), top->r, nullptr); top->l = new_l, top->r = new_r; if(new_l) update(new_l, -R, 0); if(new_r) update(new_r, 0, R); update(top, -R, R); } } L = -R; } } void update(pointer node, size_type l, size_type r) { assert(node && r - l >= 2); node->value = Monoid::op(node->l ? node->l->value : get_initial(l, (l + r) / 2), node->r ? node->r->value : get_initial((l + r) / 2, r)); } public: // scalable DynamicSegmentTree() : range_fixed(0), L(0), R(0) {} DynamicSegmentTree(const T &initial) : DynamicSegmentTree() { set_initial(initial); } DynamicSegmentTree(const func_type &get_initial) : DynamicSegmentTree() { this->get_initial = get_initial; } // [L, R) DynamicSegmentTree(size_type L, size_type R) : range_fixed(1), L(L), R(R) { assert(L < R); } DynamicSegmentTree(size_type L, size_type R, const T &initial) : DynamicSegmentTree(L, R) { set_initial(initial); } DynamicSegmentTree(size_type L, size_type R, const func_type &get_initial) : DynamicSegmentTree(L, R) { this->get_initial = get_initial; } // [0, R) DynamicSegmentTree(size_type R) : DynamicSegmentTree(0, R) {} DynamicSegmentTree(size_type R, const T &initial) : DynamicSegmentTree(R) { set_initial(initial); } DynamicSegmentTree(size_type R, const func_type &get_initial) : DynamicSegmentTree(R) { this->get_initial = get_initial; } void set_initial(const T &initial) { get_initial = [initial](size_type l, size_type r) { size_type n = r - l; n--; T u = initial, v = initial; while(n) { if(n & 1) u = Monoid::op(u, v); n >>= 1; if(n) v = Monoid::op(v, v); } return u; }; } void set(size_type i, const T &val) { if(!range_fixed) expand(i); else assert(L <= i && i < R); if(!top) std::allocator_traits< Allocator >::construct( alc, top = alc.allocate(1), get_initial(L, R)); set(i, val, L, R, top); } private: void set(size_type i, const T &val, size_type l, size_type r, pointer node) { assert(node); if(r - l == 1) { node->value = val; return; } size_type m = (l + r) / 2; if(i < m) { if(!node->l) std::allocator_traits< Allocator >::construct( alc, node->l = alc.allocate(1), get_initial(l, m)); set(i, val, l, m, node->l); } else { if(!node->r) std::allocator_traits< Allocator >::construct( alc, node->r = alc.allocate(1), get_initial(m, r)); set(i, val, m, r, node->r); } update(node, l, r); } public: T fold(size_type l, size_type r) { if(range_fixed) { if(l < L) l = L; if(R < r) r = R; } if(l >= r) return Monoid::identity(); if(!range_fixed) { if(r < L || R < l) return get_initial(l, r); if(l < L) return Monoid::op(get_initial(l, L), fold(L, r)); if(R < r) return Monoid::op(fold(l, R), get_initial(R, r)); } return fold(l, r, L, R, top); } T get(size_type i) { if(range_fixed) assert(L <= i && i < R); return fold(i, i + 1); } private: T fold(size_type a, size_type b, size_type l, size_type r, pointer node) { if(b <= l || r <= a) return Monoid::identity(); if(!node) return get_initial(std::max< size_type >(a, l), std::min< size_type >(b, r)); if(a <= l && r <= b) return node->value; return Monoid::op( fold(a, b, l, (l + r) / 2, node->l), fold(a, b, (l + r) / 2, r, node->r)); } }; template < class Monoid, class Allocator > Allocator DynamicSegmentTree< Monoid, Allocator >::alc; /// }}}--- /// /// --- Monoid examples {{{ /// constexpr long long inf_monoid = 1e18 + 100; #include 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 T(a.first + b.first, a.second + b.second); } static constexpr T identity() { return T(0, 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 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(); } }; /// }}}--- /// using Seg = DynamicSegmentTree< RangeSum> >; using P = pair; P op(P a, P b) { a.first += b.first; a.second += b.second; return a; } template struct DynamicSegmentTree2D { Index L, R; struct Node { Seg seg; Node *l = 0, *r = 0; Node() {} }; Node *p = 0; DynamicSegmentTree2D(Index L, Index R): L(L), R(R) { } void upd(Seg& seg, Index x, T v) { auto w = seg.get(x); w.first += v.first; w.second += v.second; seg.set(x, w); } public: void add(Index y, Index x, T v) { assert(L <= y && y < R); add(p, L, R, y, x, v); } private: void add(Node*& t, Index a, Index b, Index y, Index x, T v) { if(!t) t = new Node; upd(t->seg, x, v); if(a == y && y + 1 == b) return; Index mid = (a + b) / 2; if(y < mid) add(t->l, a, mid, y, x, v); else add(t->r, mid, b, y, x, v); } public: T fold(Index yl, Index yr, Index xl, Index xr) { if(yl < L) yl = L; if(yr > R) yl = R; if(yl >= yr) return T(); if(xl >= xr) return T(); return fold(p, L, R, yl, yr, xl, xr); } private: T fold(Node* k, Index a, Index b, Index yl, Index yr, Index xl, Index xr) { if(!k) return T(0, 0); if(yr <= a || b <= yl) return T(0, 0); if(yl <= a && b <= yr) return k->seg.fold(xl, xr); Index mid = (a + b) / 2; return op( fold(k->l, a, mid, yl, yr, xl, xr), fold(k->r, mid, b, yl, yr, xl, xr) ); } }; constexpr int N = 5e5; constexpr int Q = 5e5; int n, q; int t[Q], l[Q], r[Q]; int med[Q], smaller[Q], bigger[Q]; using P = pair; int main() { std::ios::sync_with_stdio(false), std::cin.tie(0); cin >> n >> q; DynamicSegmentTree2D

dseg(-inf - 1, inf + 1); vector 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++) dseg.add(v[i], i, P(v[i], 1)); for(int i = 0; i < q; i++) { if(t[i] == 1) { // update dseg.add(v[l[i]], l[i], P(-v[l[i]], -1)); dseg.add(r[i], l[i], P(r[i], 1)); v[l[i]] = r[i]; } else { // query int len = r[i] - l[i]; int ok = inf, ng = -inf-1; while(abs(ok - ng) > 1) { int mid = (ok + ng) / 2; auto f1 = dseg.fold(mid + 1, inf, l[i], r[i]); if(f1.second <= len / 2) ok = mid; else ng = mid; } med[i] = ok; smaller[i] = dseg.fold(-inf, med[i], l[i], r[i]).second; bigger[i] = dseg.fold(med[i] + 1, inf, l[i], r[i]).second; ll z = -dseg.fold(-inf, med[i], l[i], r[i]).first + dseg.fold(med[i] + 1, inf, l[i], r[i]).first; z -= ll(len / 2 - smaller[i]) * med[i]; z += ll((len - len / 2) - bigger[i]) * med[i]; if(len % 2 == 0) { } else { z -= med[i]; } cout << z << "\n"; } } return 0; }