#379580 (C++14) No.925 紲星 Extra

提出ソース
結果

問題	No.925 紲星 Extra
コンテスト
ユーザー	lumc_
提出日時	2019-09-15 03:09:52
言語	C++14 (gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	RE * 3
other	RE * 2 MLE * 10 -- * 7
権限があれば一括ダウンロードができます
ソースコード

raw source code
// 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;
}
yukicoder

結果

ソースコード
