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

提出ソース
結果

問題	No.925 紲星 Extra
ユーザー	polylogK
提出日時	2019-11-01 19:59:00
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	3,309 ms / 10,000 ms
コード長	40,492 bytes
コンパイル時間	3,432 ms
コンパイル使用メモリ	184,320 KB
実行使用メモリ	116,664 KB
最終ジャッジ日時	2023-10-13 00:58:59
合計ジャッジ時間	48,056 ms
ジャッジサーバーID （参考情報）	judge15 / judge13
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	1 ms 4,348 KB
testcase_02	AC	1 ms 4,352 KB
testcase_03	AC	11 ms 4,988 KB
testcase_04	AC	12 ms 4,352 KB
testcase_05	AC	2,876 ms 101,432 KB
testcase_06	AC	2,773 ms 102,508 KB
testcase_07	AC	2,784 ms 101,720 KB
testcase_08	AC	1,660 ms 44,760 KB
testcase_09	AC	885 ms 30,628 KB
testcase_10	AC	2,716 ms 97,872 KB
testcase_11	AC	2,799 ms 106,060 KB
testcase_12	AC	2,318 ms 84,988 KB
testcase_13	AC	2,578 ms 107,232 KB
testcase_14	AC	1,866 ms 46,236 KB
testcase_15	AC	2,578 ms 108,184 KB
testcase_16	AC	1,940 ms 96,548 KB
testcase_17	AC	1,256 ms 88,084 KB
testcase_18	AC	2,841 ms 102,668 KB
testcase_19	AC	2,495 ms 96,824 KB
testcase_20	AC	2,816 ms 107,680 KB
testcase_21	AC	3,309 ms 116,664 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#if 0

想定解

time   : O((N + Q) lg^2 (Q + N))
space  : O((Q + N) lg (Q + N))

必要のない機能 (lazy, include_i, include_j, ...) は実装を省略している

<3, 2>
<5/2, 3/2>
<1 + _/2, _/2> <- this

上２つはset操作が O(lg N) でできることが証明されてるとかなんとか
(この問題の場合は必要ない)

少し高速化

#endif

#define NDEBUG

// includes {{{
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
// #include<deque>
// #include<multiset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

#define DEBUG_OUT std::cerr
#define ONLINE

// #undef DEBUG
// #define DEBUG
// DEBUG {{{
#include <array>
#include <deque>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <valarray>
#include <vector>
template < int n, class... T >
typename std::enable_if< (n >= sizeof...(T)) >::type __output_tuple(
    std::ostream &, std::tuple< T... > const &) {}
template < int n, class... T >
typename std::enable_if< (n < sizeof...(T)) >::type __output_tuple(
    std::ostream &os, std::tuple< T... > const &t) {
  os << (n == 0 ? "" : ", ") << std::get< n >(t);
  __output_tuple< n + 1 >(os, t);
}
template < class... T >
std::ostream &operator<<(std::ostream &os, std::tuple< T... > const &t) {
  os << "(";
  __output_tuple< 0 >(os, t);
  os << ")";
  return os;
}
template < class T, class U >
std::ostream &operator<<(std::ostream &os, std::pair< T, U > const &p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template < class T >
std::ostream &operator<<(std::ostream &os, const std::stack< T > &a) {
  os << "{";
  for(auto tmp = a; tmp.size(); tmp.pop())
    os << (a.size() == tmp.size() ? "" : ", ") << tmp.top();
  os << "}";
  return os;
}
template < class T, class Container, class Compare >
std::ostream &operator<<(std::ostream &os,
                         std::priority_queue< T, Container, Compare > a) {
  os << "{ (top) ";
  while(a.size()) os << a.top() << (a.size() == 1 ? "" : ", "), a.pop();
  os << " }";
  return os;
}
template < class T, class Container >
std::ostream &operator<<(std::ostream &os, std::queue< T, Container > a) {
  os << "{ ";
  while(a.size()) os << a.front() << (a.size() == 1 ? "" : ", "), a.pop();
  os << " }";
  return os;
}
#ifdef DEBUG
#if !defined(DEBUG_OUT)
#define DEBUG_OUT std::cerr
#endif
#define dump(...)                                                                \
  [&]() {                                                                        \
    auto __debug_tap = std::make_tuple(__VA_ARGS__);                             \
    DEBUG_OUT << "[" << __LINE__ << "] " << #__VA_ARGS__ << " = " << __debug_tap \
              << std::endl;                                                      \
  }()
template < class T >
inline void dump2D(T &d, size_t sizey, size_t sizex) {
  for(size_t i = 0; i < sizey; i++) {
    DEBUG_OUT << "\t";
    for(size_t j = 0; j < sizex; j++)
      DEBUG_OUT << d[i][j] << (j + 1 == sizex ? "" : "\t");
    DEBUG_OUT << std::endl;
  }
}
template < class T >
inline void dump1D(T &d, size_t sizey) {
  for(size_t i = 0; i < sizey; i++) {
    DEBUG_OUT << d[i] << (i + 1 == sizey ? "" : " ");
  }
  DEBUG_OUT << std::endl;
}
template <
    class T, class = typename std::iterator_traits< decltype(begin(T())) >::value_type,
    class = typename std::enable_if< !std::is_same< T, std::string >::value >::type >
std::ostream &operator<<(std::ostream &os, const T &a) {
  os << "{";
  for(auto ite = begin(a); ite != end(a); ++ite)
    os << (ite == begin(a) ? "" : ", ") << *ite;
  os << "}";
  return os;
}
#else
#define dump(...) ((void) 42)
#define dump2D(...) ((void) 42)
#define dump1D(...) ((void) 42)
template <
    class T, class = typename std::iterator_traits< decltype(begin(T())) >::value_type,
    class = typename std::enable_if< !std::is_same< T, std::string >::value >::type >
std::ostream &operator<<(std::ostream &os, const T &a) {
  for(auto ite = begin(a); ite != end(a); ++ite)
    os << (ite == begin(a) ? "" : " ") << *ite;
  return os;
}
#endif
// }}}

/// --- Monoid examples {{{ ///
constexpr long long inf_monoid = 1e18 + 100;
#include <algorithm>
struct Nothing {
  using T = char;
  using Monoid = Nothing;
  using M = T;
  static constexpr T op(const T &, const T &) { return T(); }
  static constexpr T identity() { return T(); }
  template < class X >
  static constexpr X actInto(const M &, long long, const X &x) {
    return x;
  }
};

template<class _Monoid>
struct Nothing_M_act {
  using Monoid = _Monoid;
  using T = typename Monoid::T;
  using M = char;
  static constexpr M op(const T &, const T &) { return T(); }
  static constexpr M identity() { return T(); }
  template < class X >
  static constexpr X actInto(const M &, long long, const X &x) {
    return x;
  }
};

template < class U = long long >
struct RangeMin {
  using T = U;
  static T op(const T &a, const T &b) { return std::min< T >(a, b); }
  static constexpr T identity() { return T(inf_monoid); }
};

template < class U = long long >
struct RangeMax {
  using T = U;
  static T op(const T &a, const T &b) { return std::max< T >(a, b); }
  static constexpr T identity() { return T(-inf_monoid); }
};

template < class U = long long >
struct RangeSum {
  using T = U;
  static T op(const T &a, const T &b) { return a + b; }
  static constexpr T identity() { return T(0); }
};

template < class U >
struct RangeProd {
  using T = U;
  static T op(const T &a, const T &b) { return a * b; }
  static constexpr T identity() { return T(1); }
};

template < class U = long long >
struct RangeOr {
  using T = U;
  static T op(const T &a, const T &b) { return a | b; }
  static constexpr T identity() { return T(0); }
};

#include <bitset>

template < class U = long long >
struct RangeAnd {
  using T = U;
  static T op(const T &a, const T &b) { return a & b; }
  static constexpr T identity() { return T(-1); }
};

template < size_t N >
struct RangeAnd< std::bitset< N > > {
  using T = std::bitset< N >;
  static T op(const T &a, const T &b) { return a & b; }
  static constexpr T identity() { return std::bitset< N >().set(); }
};

/// }}}--- ///

/// --- M_act examples {{{ ///
template < class U = long long, class V = U >
struct RangeMinAdd {
  using X = U;
  using M = V;
  using Monoid = RangeMin< U >;
  static M op(const M &a, const M &b) { return a + b; }
  static constexpr M identity() { return 0; }
  static X actInto(const M &m, long long, const X &x) { return m + x; }
};

template < class U = long long, class V = U >
struct RangeMaxAdd {
  using X = U;
  using M = V;
  using Monoid = RangeMax< U >;
  static M op(const M &a, const M &b) { return a + b; }
  static constexpr M identity() { return 0; }
  static X actInto(const M &m, long long, const X &x) { return m + x; }
};

template < class U = long long, class V = U >
struct RangeMinSet {
  using M = U;
  using Monoid = RangeMin< U >;
  using X = typename Monoid::T;
  static M op(const M &a, const M &b) { return a == identity() ? b : a; }
  static constexpr M identity() { return M(-inf_monoid); }
  static X actInto(const M &m, long long, const X &x) { return m == identity() ? x : m; }
};

template < class U = long long, class V = U >
struct RangeMaxSet {
  using M = U;
  using Monoid = RangeMax< U >;
  using X = typename Monoid::T;
  static M op(const M &a, const M &b) { return a == identity() ? b : a; }
  static constexpr M identity() { return M(-inf_monoid); }
  static X actInto(const M &m, long long, const X &x) { return m == identity() ? x : m; }
};

template < class U = long long, class V = U >
struct RangeSumAdd {
  using X = U;
  using M = V;
  using Monoid = RangeSum< U >;
  static M op(const M &a, const M &b) { return a + b; }
  static constexpr M identity() { return 0; }
  static X actInto(const M &m, long long n, const X &x) { return m * n + x; }
};

template < class U = long long, class V = U >
struct RangeSumSet {
  using X = U;
  using M = V;
  using Monoid = RangeSum< U >;
  static M op(const M &a, const M &b) { return a == identity() ? a : b; }
  static constexpr M identity() { return M(-inf_monoid); }
  static X actInto(const M &m, long long n, const X &x) {
    return m == identity() ? x : m * n;
  }
};

template < class U, class V = U >
struct RangeProdMul {
  using X = U;
  using M = V;
  using Monoid = RangeProd< U >;
  static M mpow(M a, long long b) {
    X r(1);
    while(b) {
      if(b & 1) r = r * a;
      a = a * a;
      b >>= 1;
    }
    return r;
  }
  static M op(const M &a, const M &b) { return a * b; }
  static constexpr M identity() { return M(1); }
  static X actInto(const M &m, long long n, const X &x) { return x * mpow(m, n); }
};

template < class U, class V = U >
struct RangeProdSet {
  using X = U;
  using M = V;
  using Monoid = RangeProd< U >;
  static M op(const M &a, const M &b) { return a == identity() ? b : a; }
  static constexpr M identity() { return V::unused; }
  static X actInto(const M &m, long long n, const X &) {
    if(m == identity()) return;
    return RangeProdMul< U, V >::mpow(m, n);
  }
};

template < class U = long long, class V = U >
struct RangeOrSet {
  using X = U;
  using M = V;
  using Monoid = RangeOr< U >;
  static M op(const M &a, const M &b) { return a == identity() ? b : a; }
  static constexpr M identity() { return M(-inf_monoid); }
  static X actInto(const M &m, long long, const X &x) { return m == identity() ? x : m; }
};

template < class U = long long, class V = U >
struct RangeAndSet {
  using X = U;
  using M = V;
  using Monoid = RangeAnd< U >;
  static M op(const M &a, const M &b) { return a == identity() ? b : a; }
  static constexpr M identity() { return M(-inf_monoid); }
  static X actInto(const M &m, long long, const X &x) { return m == identity() ? x : m; }
};

template < class U = long long, class V = U >
struct RangeOr2 {
  using X = U;
  using M = V;
  using Monoid = RangeOr< U >;
  static M op(const M &a, const M &b) { return a | b; }
  static constexpr M identity() { return M(0); }
  static X actInto(const M &m, long long, const X &x) { return m | x; }
};

template < class U = long long, class V = U >
struct RangeAnd2 {
  using X = U;
  using M = V;
  using Monoid = RangeAnd< U >;
  static M op(const M &a, const M &b) { return a & b; }
  static constexpr M identity() { return M(-1); }
  static X actInto(const M &m, long long, const X &x) { return m & x; }
};

template < class U, size_t N >
struct RangeAnd2< U, std::bitset< N > > {
  using X = U;
  using M = std::bitset< N >;
  using Monoid = RangeAnd< U >;
  static M op(const M &a, const M &b) { return a & b; }
  static constexpr M identity() { return std::bitset< N >().set(); }
  static X actInto(const M &m, long long, const X &x) { return m & x; }
};
/// }}}--- ///

#include <cassert>
#include <cstddef>
#include <functional>
#include <tuple>
#include <utility>
#include <vector>
namespace wbt {

// WeightBalancedTreeNode {{{

template < class Key, class M_act >
struct WeightBalancedTreeNode {
  using size_type = std::size_t;
  using node_type = WeightBalancedTreeNode;
  using pointer = WeightBalancedTreeNode *;
  using const_pointer = const WeightBalancedTreeNode *;

  using Monoid = typename M_act::Monoid;
  using T = typename Monoid::T;
  using M = typename M_act::M;

  size_type sz;
  Key key;
  T value = Monoid::identity(), accum = Monoid::identity();
  pointer l, r;

  size_type weight() const { return sz + 1; }

  bool bounded_balanced() const {
    if(this == get_NIL()) return 1;
    return is_balanced(l, r) && is_balanced(r, l) && l->bounded_balanced() &&
           r->bounded_balanced();
  }

  static long long sq(long long a) { return a * a; };

  static bool is_balanced(const_pointer a, const_pointer b) {
    // return delta * a->weight() >= b->weight();
    // delta = 3

    // return 3 * a->weight() >= b->weight();

    // delta = 5 / 2

    // return 5 * a->weight() >= 2 * b->weight();

    // delta = 1 + _/2
    // (1 + _/2) a >= b
    // _/2 a >= b - a
    // 2 a^2 >= (b - a)^2

    return 2 * sq(a->weight()) >= sq(static_cast<long long>(a->weight()) - static_cast<long long>(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();

    // gamma = 3 / 2

    // return 2 * a->weight() < 3 * b->weight();

    // gamma = _/2

    return sq(a->weight()) < 2 * sq(b->weight());
  }

  static std::pair< T, bool > lookup(const_pointer p, Key key) {
    const_pointer t = p;
    while(t != get_NIL()) {
      if(key < t->key) {
        t = t->l;
      } else if(t->key < key) {
        t = t->r;
      } else {
        return std::pair< T, bool >(t->value, 1);
      }
    }
    return std::pair< T, bool >();
  }

  static pointer copy(const_pointer a) {
    if(a == get_NIL()) return get_NIL();
    return make(a->key, a->value, a->accum, copy(a->l), copy(a->r));
  }

  static T fold(const_pointer p, Key keyL, Key keyR, bool include_left,
                bool include_right) {
    while(p != get_NIL()) {
      if(p->key < keyL || (!include_left && !(keyL < p->key))) p = p->r;
      else if(keyR < p->key || (!include_right && !(p->key < keyR))) p = p->l;
      else break;
    }

    if(p == get_NIL()) return Monoid::identity();

    T x = p->value;

    const_pointer pl = p->l, pr = p->r;

    while(pl != get_NIL()) {
      if(pl->key < keyL) {
        pl = pl->r;
      } else {
        x = Monoid::op(pl->r->accum, x);
        if(keyL < pl->key) {
          x = Monoid::op(pl->value, x);
          pl = pl->l;
        } else {
          if(include_left) x = Monoid::op(pl->value, x);
          break;
        }
      }
    }

    while(pr != get_NIL()) {
      if(keyR < pr->key) {
        pr = pr->l;
      } else {
        x = Monoid::op(x, pr->l->accum);
        if(pr->key < keyR) {
          x = Monoid::op(x, pr->value);
          pr = pr->r;
        } else {
          if(include_right) x = Monoid::op(x, pr->value);
          break;
        }
      }
    }

    return x;
  }

  static size_type count(const_pointer p, const Key &keyL, const Key &keyR,
                         bool include_left, bool include_right) {
    if(keyR < keyL) return 0;
    const_pointer t = p;
    while(t != get_NIL()) {
      if(!(keyL < t->key)) {
        // key <= keyL
        if(include_left && !(t->key < keyL))
          return 1 + count_lesser(t->r, keyR, include_right);
        t = t->r;
      } else if(!(t->key < keyR)) {
        // keyR <= key
        if(include_right && !(keyR < t->key))
          return 1 + count_greater(t->l, keyL, include_left);
        t = t->l;
      } else {
        // keyL < key < keyR
        return count_greater(t->l, keyL, include_left) + 1 +
               count_lesser(t->r, keyR, include_right);
      }
    }
    return 0;
  }

  static size_type count_lesser(const_pointer p, const Key &keyR, bool include_bound) {
    size_type res = 0;
    const_pointer t = p;
    while(t != get_NIL()) {
      if(t->key < keyR) {
        res += t->l->sz + 1;
        t = t->r;
      } else {
        // keyR <= key
        if(include_bound && !(keyR < t->key)) return res + t->l->sz + 1;
        t = t->l;
      }
    }
    return res;
  }

  static size_type count_greater(const_pointer p, const Key &keyL, bool include_bound) {
    size_type res = 0;
    const_pointer t = p;
    while(t != get_NIL()) {
      if(keyL < t->key) {
        res += t->r->sz + 1;
        t = t->l;
      } else {
        // key <= keyL
        if(include_bound && !(t->key < keyL)) return res + t->r->sz + 1;
        t = t->r;
      }
    }
    return res;
  }

  static pointer insert(pointer p, Key key, T value, bool is_identity) {
    if(p == get_NIL()) return make_singleton(key, value);
    static std::vector< std::pair< pointer, bool > > pts;
    pointer t = p;
    while(t != get_NIL()) {
      if(key < t->key) {
        pts.emplace_back(t, 1);
        t = t->l;
      } else if(t->key < key) {
        pts.emplace_back(t, 0);
        t = t->r;
      } else {
        pts.clear();
        return p;
      }
    }

    pointer q;
    bool is_left;
    std::tie(q, is_left) = pts.back();
    (is_left ? q->l : q->r) = make_singleton(key, value);

    while(pts.size()) {
      std::tie(q, is_left) = pts.back();
      pts.pop_back();
      update(q, is_identity);
      if(is_left) {
        balanceR(q);
      } else {
        balanceL(q);
      }
    }
    return p;
  }

  static pointer insert_min(pointer p, Key key, T value, bool is_identity) {
    if(p == get_NIL()) return make_singleton(key, value);
    static std::vector< pointer > pts;
    pointer t = p;
    while(t != get_NIL()) {
      pts.emplace_back(t);
      t = t->l;
    }

    pointer q = pts.back();
    q->l = make_singleton(key, value);

    while(pts.size()) {
      q = pts.back();
      pts.pop_back();
      update(q, is_identity);
      balanceR(q);
    }
    return p;
  }

  static pointer insert_max(pointer p, Key key, T value, bool is_identity) {
    if(p == get_NIL()) return make_singleton(key, value);
    static std::vector< pointer > pts;
    pointer t = p;
    while(t != get_NIL()) {
      pts.emplace_back(t);
      t = t->r;
    }

    pointer q = pts.back();
    q->r = make_singleton(key, value);

    while(pts.size()) {
      q = pts.back();
      pts.pop_back();
      update(q, is_identity);
      balanceR(q);
    }
    return p;
  }

  static pointer erase(pointer p, Key key) {
    static std::vector< std::pair< pointer, bool > > pts;
    pointer t = p;
    while(t != get_NIL()) {
      if(key < t->key) {
        pts.emplace_back(t, 1);
        t = t->l;
      } else if(t->key < key) {
        pts.emplace_back(t, 0);
        t = t->r;
      } else {
        pointer s = glue(t->l, t->r);
        delete t;

        if(pts.empty()) return s;

        pointer q;
        bool is_left;
        std::tie(q, is_left) = pts.back();
        (is_left ? q->l : q->r) = s;

        while(pts.size()) {
          std::tie(q, is_left) = pts.back();
          pts.pop_back();
          update(q);
          if(is_left) {
            balanceL(q);
          } else {
            balanceR(q);
          }
        }
        break;
      }
    }
    pts.clear();
    return p;
  }

  Key select(size_type k) const {
    assert(this != get_NIL());
    if(k < l->sz) return l->select(k);
    k -= l->sz;
    if(k == 0) return key;
    k--;
    return r->select(k);
  }

  static pointer balance(Key k, T v, pointer l, pointer r) {
    if(is_balanced(l, r) && is_balanced(r, l)) return make(k, v, l, r);
    if(l->sz > r->sz) return rotateR(k, v, l, r);
    return rotateL(k, v, l, r);
  }

  static pointer glue(pointer l, pointer r) {
    if(l == get_NIL()) return r;
    if(r == get_NIL()) return l;
    if(l->sz > r->sz) {
      pointer l2, p;
      std::tie(l2, p) = delete_find_max(l);
      p->l = l2;
      p->r = r;
      update(p);
      balanceL(p);
      return p;
    } else {
      pointer r2, p;
      std::tie(r2, p) = delete_find_min(r);
      p->l = l;
      p->r = r2;
      update(p);
      balanceR(p);
      return p;
    }
  }

  // BST basic operations {{{
  static pointer merge(pointer l, Key k, T v, pointer r) {
    static std::vector< std::pair< pointer, bool > > pts;
    pointer q;
    while(1) {
      if(l == get_NIL()) {
        q = insert_min(r, k, v, 0);
        break;
      }
      if(r == get_NIL()) {
        q = insert_max(l, k, v, 0);
        break;
      }
      bool bal1 = is_balanced(l, r);
      bool bal2 = is_balanced(r, l);
      if(bal1 && bal2) {
        q = make(k, v, l, r);
        break;
      } else if(bal1) {
        pts.emplace_back(l, 1);
        l = l->r;
      } else {
        pts.emplace_back(r, 0);
        r = r->l;
      }
    }
    while(pts.size()) {
      pointer p;
      bool is_left;
      std::tie(p, is_left) = pts.back();
      pts.pop_back();
      (is_left ? p->r : p->l) = q;
      q = p;
      update(q);
      if(is_left) {
        balanceL(q);
      } else {
        balanceR(q);
      }
    }
    return q;
  }
  static std::tuple< pointer, bool, pointer > split(pointer a, const Key &k) {
    static std::vector< std::pair< pointer, int > > pts;
    bool erased = 0;
    while(1) {
      if(a == get_NIL()) break;
      if(k < a->key) {
        pts.emplace_back(a, 1);
        a = a->l;
      } else if(a->key < k) {
        pts.emplace_back(a, 0);
        a = a->r;
      } else {
        erased = 1;
        break;
      }
    }
    pointer l = a->l, r = a->r;
    if(a != get_NIL()) delete a;
    while(pts.size()) {
      pointer p;
      bool is_left;
      std::tie(p, is_left) = pts.back();
      pts.pop_back();
      if(is_left) {
        r = merge(r, std::move(p->key), std::move(p->value), p->r);
      } else {
        l = merge(p->l, std::move(p->key), std::move(p->value), l);
      }
      delete p;
    }
    return std::tuple< pointer, bool, pointer >(l, erased, r);
  }
  // }}}

  // set operations {{{
  static pointer unionL(pointer t1, pointer t2) {
    if(t1 == get_NIL()) return t2;
    if(t2 == get_NIL()) return t1;
    // if(t1->sz < t2->sz) swap(t1, t2);
    pointer t_lesser, t_greater;
    std::tie(t_lesser, std::ignore, t_greater) = split(t2, t1->key);
    pointer q = merge(unionL(t1->l, t_lesser), std::move(t1->key), std::move(t1->value),
                      unionL(t1->r, t_greater));
    delete t1;
    return q;
  }
  // }}}

  using PP = std::tuple< pointer, pointer >;
  static PP delete_find_max(pointer p) {
    assert(p != get_NIL());
    if(p->r == get_NIL()) {
      pointer q = p->l;
      p->l = get_NIL();
      update(p);
      return PP(q, p);
    }
    pointer t = p;
    static std::vector<pointer> pts;
    while(1) {
      pts.push_back(t);
      if(t->r->r == get_NIL()) {
        pointer q = t->r;
        t->r = q->l;
        q->l = get_NIL();
        update(q);

        while(pts.size()) {
          pointer s = pts.back();
          pts.pop_back();
          update(s);
        }

        return PP(p, q);
      } else {
        t = t->r;
      }
    }
  }

  static PP delete_find_min(pointer p) {
    assert(p != get_NIL());
    if(p->l == get_NIL()) {
      pointer q = p->r;
      p->r = get_NIL();
      update(p);
      return PP(q, p);
    }
    pointer t = p;
    static std::vector<pointer> pts;
    while(1) {
      pts.push_back(t);
      if(t->l->l == get_NIL()) {
        pointer q = t->l;
        t->l = q->r;
        q->r = get_NIL();
        update(q);

        while(pts.size()) {
          pointer s = pts.back();
          pts.pop_back();
          update(s);
        }

        return PP(p, q);
      } else {
        t = t->l;
      }
    }
  }

  // rotate {{{
  static void balanceL(pointer p) {
    if(is_balanced(p->l, p->r)) return;
    rotateL(p);
  }
  static void balanceR(pointer p) {
    if(is_balanced(p->r, p->l)) return;
    rotateR(p);
  }

  static void rotateL(pointer p) {
    const pointer rl = p->r->l, rr = p->r->r;
    if(is_single(rl, rr)) {
      singleL(p);
    } else {
      doubleL(p);
    }
  }
  static void rotateR(pointer p) {
    const pointer ll = p->l->l, lr = p->l->r;
    if(is_single(lr, ll)) {
      singleR(p);
    } else {
      doubleR(p);
    }
  }

  static void singleL(pointer p) {
    pointer q = p->r;
    assert(q != get_NIL());
    p->r = q->r;
    q->r = q->l;
    q->l = p->l;
    p->l = q;
    std::swap(p->key, q->key);
    std::swap(p->value, q->value);
    update(q);
    update(p);
  }
  static void singleR(pointer p) {
    pointer q = p->l;
    assert(q != get_NIL());
    p->l = q->l;
    q->l = q->r;
    q->r = p->r;
    p->r = q;
    std::swap(p->key, q->key);
    std::swap(p->value, q->value);
    update(q);
    update(p);
  }

  static void doubleL(pointer p) {
    pointer s = p->r->l;
    assert(s != get_NIL());
    p->r->l = s->r;
    s->r = s->l;
    s->l = p->l;
    p->l = s;
    std::swap(p->key, s->key);
    std::swap(p->value, s->value);
    update(p->l);
    update(p->r);
    update(p);
  }
  static void doubleR(pointer p) {
    pointer s = p->l->r;
    assert(s != get_NIL());
    p->l->r = s->l;
    s->l = s->r;
    s->r = p->r;
    p->r = s;
    std::swap(p->key, s->key);
    std::swap(p->value, s->value);
    update(p->l);
    update(p->r);
    update(p);
  }
  // }}}

  static pointer get_NIL() {
    static pointer NIL = make_NIL();
    return NIL;
  }

  static pointer make_NIL() {
    pointer p = new WeightBalancedTreeNode;
    p->sz = 0;
    p->value = p->accum = Monoid::identity();
    p->l = p;
    p->r = p;
    return p;
  }

  static pointer make_singleton(Key key, T value) {
    pointer p = new WeightBalancedTreeNode;
    p->sz = 1;
    p->key = std::move(key);
    p->value = p->accum = std::move(value);
    p->l = get_NIL();
    p->r = get_NIL();
    return p;
  }

  static pointer make(Key key, T value, pointer l, pointer r) {
    pointer p = new WeightBalancedTreeNode;
    p->sz = l->sz + r->sz + 1;
    p->key = std::move(key);
    p->value = value;
    p->accum = Monoid::op(Monoid::op(l->accum, std::move(value)), r->accum);
    p->l = l;
    p->r = r;
    return p;
  }

  static void update(pointer p, bool is_identity = 0) {
    p->sz = p->l->sz + p->r->sz + 1;
    if(!is_identity)
      p->accum = Monoid::op(Monoid::op(p->l->accum, p->value), p->r->accum);
  }

  static pointer make(Key key, T value, T accum, pointer l, pointer r) {
    pointer p = new WeightBalancedTreeNode;
    p->sz = l->sz + r->sz + 1;
    p->key = std::move(key);
    p->value = std::move(value);
    p->accum = std::move(accum);
    p->l = l;
    p->r = r;
    return p;
  }

  static std::pair< Key, T > get_min(const_pointer p) {
    assert(p != get_NIL());
    while(p->l != get_NIL()) p = p->l;
    return std::pair< Key, T >(p->key, p->value);
  }
  static std::pair< Key, T > get_max(const_pointer p) {
    assert(p != get_NIL());
    while(p->r != get_NIL()) p = p->r;
    return std::pair< Key, T >(p->key, p->value);
  }

  void get_all_dfs(std::vector< std::pair< Key, T > > &res) const {
    if(this == get_NIL()) return;
    l->get_all_dfs(res);
    res.emplace_back(key, value);
    r->get_all_dfs(res);
  }

  static void delete_all(pointer p) {
    if(p == get_NIL()) return;
    delete_all(p->l);
    delete_all(p->r);
    delete p;
  }

  using touch_func = std::function< void(Key key, T &v, T &accum, bool eq) >;

  static bool touch_path_to(pointer p, const Key &target, const touch_func &touch) {
    pointer t = p;
    static std::vector< pointer > pts;
    while(t != get_NIL()) {
      if(target < t->key) {
        pts.push_back(t);
        t = t->l;
      } else if(t->key < target) {
        pts.push_back(t);
        t = t->r;
      } else {
        touch(t->key, t->value, t->accum, 1);
        while(pts.size()) {
          t = pts.back();
          pts.pop_back();
          touch(t->key, t->value, t->accum, 0);
        }
        return 1;
      }
    }
    pts.clear();
    return 0;
  }
};

// }}}

// WeightBalancedTree {{{

template < class Key, class M_act >
struct WeightBalancedTree {
  using size_type = std::size_t;
  using node_type = WeightBalancedTreeNode< Key, M_act >;
  using pointer = WeightBalancedTreeNode< Key, M_act > *;
  using const_pointer = const WeightBalancedTreeNode< Key, M_act > *;

  using Monoid = typename M_act::Monoid;
  using T = typename Monoid::T;
  using M = typename M_act::M;

  bool active = 1;
  pointer p = node_type::get_NIL();

  WeightBalancedTree() {}
  WeightBalancedTree(pointer p) : p(p) {}

  WeightBalancedTree(const WeightBalancedTree &wbt) { *this = wbt; }
  WeightBalancedTree(WeightBalancedTree &&wbt) { *this = std::move(wbt); }

  WeightBalancedTree &operator=(const WeightBalancedTree &wbt) {
    assert(wbt.active);
    if(active) node_type::delete_all(p);
    active = 1;
    p = node_type::copy(wbt.p);
    return *this;
  }
  WeightBalancedTree &operator=(WeightBalancedTree &&wbt) {
    assert(wbt.active);
    if(active) node_type::delete_all(p);
    active = 1;
    wbt.active = 0;
    p = wbt.p;
    return *this;
  }

  ~WeightBalancedTree() {
    if(active) {
      node_type::delete_all(p);
    }
  }

  void insert(Key key, T value, bool is_identity = 0) {
    assert(active);
    p = node_type::insert(p, key, value, is_identity);
  }
  void insert(Key key) {
    insert(key, Monoid::identity(), 1);
  }
  bool erase(Key key) {
    assert(active);
    p = node_type::erase(p, key);

    // TODO
    return 1;
  }
  std::pair< T, bool > lookup(Key key) const {
    assert(active);
    return node_type::lookup(p, key);
  }
  T get(Key key) const {
    assert(active);
    return lookup(key).first;
  }
  size_type count(Key key) const {
    assert(active);
    return lookup(key).second;
  }

  void clear() {
    if(p == node_type::get_NIL()) {
      active = 1;
      return;
    }
    if(active) node_type::delete_all(p);
    active = 1;
    p = node_type::get_NIL();
  }

  std::vector< std::pair< Key, T > > get_all() const {
    assert(active);
    std::vector< std::pair< Key, T > > res;
    res.reserve(size());
    p->get_all_dfs(res);
    return res;
  }

  T fold(Key keyL, Key keyR) const {
    assert(active);
    return node_type::fold(p, keyL, keyR, 1, 0);
  }
  T fold(Key keyL, Key keyR, bool include_left, bool include_right) const {
    assert(active);
    return node_type::fold(p, keyL, keyR, include_left, include_right);
  }

  std::pair< Key, T > get_min() const {
    assert(active);
    return p->get_min();
  }
  std::pair< Key, T > get_max() const {
    assert(active);
    return p->get_max();
  }

  size_type count(Key l, Key r) const {
    assert(active);
    return node_type::count(p, l, r, 1, 0);
  }
  size_type count(Key l, Key r, bool include_left, bool include_right) const {
    assert(active);
    return node_type::count(p, l, r, include_left, include_right);
  }

  size_type count_lesser(Key key, bool include_bound) const {
    assert(active);
    return node_type::count_lesser(p, key, include_bound);
  }
  size_type count_greater(Key key, bool include_bound) const {
    assert(active);
    return node_type::count_greater(p, key, include_bound);
  }

  Key select(size_type k) const {
    assert(active);
    assert(k < size());
    return p->select(k);
  }

  WeightBalancedTree &union_with(WeightBalancedTree &&a) {
    assert(active && a.active);
    a.active = 0;

    p = node_type::unionL(p, a.p);

    return *this;
  }

  using touch_func = std::function< void(Key key, T &v, T &accum, bool eq) >;
  static touch_func touch_default;

  void touch_path_to(const Key &target, const touch_func &touch) {
    assert(active);
    node_type::touch_path_to(p, target, touch);
  }

  size_type size() const {
    assert(active);
    return p->sz;
  }
  bool empty() const {
    assert(active);
    return p == node_type::get_NIL();
  }
};

template < class Key, class M_act >
typename WeightBalancedTree< Key, M_act >::touch_func
    WeightBalancedTree< Key, M_act >::touch_default = [](...) {};

// }}}
}

template < class Key, class M_act >
using WBT = wbt::WeightBalancedTree< Key, M_act >;

/// --- RangeMedianWithUpdate {{{ ///

#include <ostream>
namespace wbt {
template < class _T, class _Monoid, class Index = long long >
struct RangeMedianWithUpdate {
  using size_type = std::size_t;
  using T = _T;
  using Monoid = _Monoid;
  using X = typename Monoid::T;

  struct Point {
    Index x;
    T y;
    bool minus_inf = 0;

    Point() {}
    Point(Index x) : x(x), minus_inf(1) {}
    Point(Index x, T y) : x(x), y(y) {}
    bool operator<(const Point &a) const {
      if(x < a.x) return 1;
      if(a.x < x) return 0;
      if(a.minus_inf) return 0;
      if(minus_inf) return 1;
      return 0;
    }

    friend std::ostream &operator<<(std::ostream &os, Point a) {
      if(a.minus_inf)
        os << "(" << a.x << ", "
           << "-inf"
           << ")";
      else
        os << "(" << a.x << ", " << a.y << ")";
      return os;
    }
  };

  struct RMWU_Monoid {
    using T = WeightBalancedTree< Point, Nothing_M_act<Monoid> >;
    static T op(T a, T b) { return a.union_with(std::move(b)); }
    static T identity() { return T(); }
  };
  struct RMWU_M_act {
    using Monoid = RMWU_Monoid;
    using X = typename Monoid::T;
    using M = char;
    static M op(const M &, const M &) { return 0; }
    static constexpr M identity() { return 0; }
    static X actInto(const M &, long long, const X &x) { return x; }
  };

  using T_SET = typename RMWU_Monoid::T;
  using WBT = WeightBalancedTree< T, RMWU_M_act >;
  using pointer = typename WBT::pointer;
  using const_pointer = typename WBT::const_pointer;

  WeightBalancedTree< T, RMWU_M_act > wbt;

  RangeMedianWithUpdate() {}

  static RangeMedianWithUpdate with2(const std::vector< std::tuple< T, X > > &v,
                                   Index start = 0) {
    std::vector< std::tuple< Index, T, X > > w;
    w.reserve(v.size());
    for(size_type i = 0; i < v.size(); ++i, ++start)
      w.emplace_back(start, std::get< 0 >(v[i]), std::get< 1 >(v[i]));
    return with3(w);
  }
  static RangeMedianWithUpdate with3(std::vector< std::tuple< Index, T, X > > v) {
    RangeMedianWithUpdate res;
    using V = std::tuple< Index, T, X >;
    std::sort(v.begin(), v.end(),
              [](const V &a, const V &b) { return std::get< 1 >(a) < std::get< 1 >(b); });
    static std::queue< std::pair< size_type, size_type > > q;
    q.emplace(0, v.size());
    while(q.size()) {
      Index l, r;
      std::tie(l, r) = q.front();
      q.pop();
      if(l == r) continue;
      Index m = (l + r) / 2;
      res.insert(std::get< 0 >(v[m]), std::get< 1 >(v[m]), std::get< 2 >(v[m]));
      q.emplace(l, m);
      q.emplace(m + 1, r);
    }
    return res;
  }

  void insert(Index i, T v, X x, bool is_identity = 0) {
    wbt.insert(v);
    insert_path_to(wbt.p, v, Point(i, v), x, is_identity);
  }

  void insert(Index i, T v) {
    insert(i, v, Monoid::identity(), 1);
  }

  bool erase(Index i, T v) { return erase_path_to(wbt.p, v, Point(i, v)); }

  static bool insert_path_to(pointer p, T target, const Point &v, X x, bool is_identity) {
    pointer t = p;
    static std::vector< pointer > pts;
    while(t != WBT::node_type::get_NIL()) {
      if(target < t->key) {
        pts.push_back(t);
        t = t->l;
      } else if(t->key < target) {
        pts.push_back(t);
        t = t->r;
      } else {
        t->value.insert(v, x, is_identity);
        t->accum.insert(v, x, is_identity);
        while(pts.size()) {
          t = pts.back();
          pts.pop_back();
          t->accum.insert(v, x, is_identity);
        }
        return 1;
      }
    }
    pts.clear();
    return 0;
  }

  static bool erase_path_to(pointer p, T target, const Point &v) {
    pointer t = p;
    static std::vector< pointer > pts;
    while(t != WBT::node_type::get_NIL()) {
      if(target < t->key) {
        pts.push_back(t);
        t = t->l;
      } else if(t->key < target) {
        pts.push_back(t);
        t = t->r;
      } else {
        t->value.erase(v);
        t->accum.erase(v);
        while(pts.size()) {
          t = pts.back();
          pts.pop_back();
          t->accum.erase(v);
        }
        return 1;
      }
    }
    pts.clear();
    return 0;
  }

  X rect_fold(Index i, Index j, T l, T r) {
    return rect_fold(i, j, l, r, 1, 0, 1, 0);
  }

  X rect_fold(Index i, Index j, T l, T r, bool include_i, bool include_j, bool include_l, bool include_r) const {
    const_pointer p = wbt.p;

    while(p != WBT::node_type::get_NIL()) {
      if(p->key < l || (!include_l && !(l < p->key))) p = p->r;
      else if(r < p->key || (!include_r && !(p->key < r))) p = p->l;
      else break;
    }
    if(p == WBT::node_type::get_NIL()) return Monoid::identity();

    X x = p->value.fold(i, j);

    const_pointer pl = p->l, pr = p->r;

    while(pl != WBT::node_type::get_NIL()) {
      if(pl->key < l) {
        pl = pl->r;
      } else {
        x = Monoid::op(pl->r->accum.fold(i, j), x);
        if(l < pl->key) {
          x = Monoid::op(pl->value.fold(i, j), x);
          pl = pl->l;
        } else {
          if(include_l) x = Monoid::op(pl->value.fold(i, j), x);
          break;
        }
      }
    }

    while(pr != WBT::node_type::get_NIL()) {
      if(r < pr->key) {
        pr = pr->l;
      } else {
        x = Monoid::op(x, pr->l->accum.fold(i, j));
        if(pr->key < r) {
          x = Monoid::op(x, pr->value.fold(i, j));
          pr = pr->r;
        } else {
          if(include_r) x = Monoid::op(x, pr->value.fold(i, j));
          break;
        }
      }
    }

    return x;
  }

  Point range_select(Index i, Index j, size_type k) const {
    return range_select_dfs(wbt.p, i, j, k);
  }

  size_type range_count_smaller(Index i, Index j, T x, bool include_bound) const {
    return range_count_smaller_dfs(wbt.p, i, j, x, include_bound);
  }

private:
  Point range_select_dfs(const_pointer p, Index i, Index j, size_type k) const {
    assert(p != WBT::node_type::get_NIL());
    assert(k < p->accum.count(i, j));
    size_type lsz = p->l->accum.count(i, j);
    if(k < lsz) {
      return range_select_dfs(p->l, i, j, k);
    }
    k -= lsz;
    size_type hsz = p->value.count(i, j);
    if(k < hsz) {
      return p->value.select(p->value.count_lesser(i, 0) + k);
    }
    k -= hsz;
    return range_select_dfs(p->r, i, j, k);
  }
  size_type range_count_smaller_dfs(const_pointer p, Index i, Index j, T x,
                                    bool include_bound) const {
    if(p == WBT::node_type::get_NIL()) return 0;
    if(x < p->key) return range_count_smaller_dfs(p->l, i, j, x, include_bound);
    // p->key <= x
    size_type lsz = p->l->accum.count(i, j);
    size_type hsz = p->value.count(i, j);
    if(!(p->key < x)) {
      if(include_bound) return lsz + hsz;
      return lsz;
    }
    return lsz + hsz + range_count_smaller_dfs(p->r, i, j, x, include_bound);
  }

public:
  Point range_median(Index i, Index j, bool choose_greater = 0) const {
    return range_select(i, j, (count(i, j) - 1 + choose_greater) / 2);
  }
  size_type count(Index i, Index j) const { return wbt.p->accum.count(i, j); }
  size_type size() const { return wbt.p->accum.size(); }
};
}

/// }}}--- ///

template < class T, class Monoid, class Index = long long >
using RangeMedianWithUpdate = wbt::RangeMedianWithUpdate< T, Monoid, Index >;

constexpr int N = 1 << 16;

constexpr ll inf = 1ll << 40; // 1e12

int n, q;
ll t[N], l[N], r[N];
ll med[N], smaller[N], bigger[N];

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  cin >> n >> q;

  assert(1 <= n && n < N);
  assert(1 <= q && q < N);

  vector< ll > v(n + 1);

  vector<tuple<ll, ll, ll>> ini;
  for(int i = 1; i <= n; i++) {
    cin >> v[i];
    // rm.insert(i, v[i], v[i]);
    ini.emplace_back(i, v[i], v[i]);

    assert(0 <= v[i] && v[i] < inf);
  }

  auto rm = RangeMedianWithUpdate< ll, RangeSum<ll> >::with3(ini);

  for(int i = 0; i < q; i++) cin >> t[i] >> l[i] >> r[i];

  auto w = v;
  ll sum16 = 0, sum40 = 0;

  for(int i = 0; i < q; i++) {
    if(t[i] == 1) { // update

#ifdef ONLINE
    l[i] ^= sum16;
    r[i] ^= sum40;
#endif

      assert(1 <= l[i] && l[i] <= n);
      assert(0 <= r[i] && r[i] < inf);
      // cout << "1 " << l[i] << " " << r[i] << "\n";

      rm.erase(l[i], w[l[i]]);
      rm.insert(l[i], r[i], r[i]);
      w[l[i]] = r[i];
    } else { // query

#ifdef ONLINE
    l[i] ^= sum16;
    r[i] ^= sum16;
#endif

      if(l[i] > r[i]) swap(l[i], r[i]);
      // cout << "2 " << l[i] << " " << r[i] << "\n";

      assert(1 <= l[i] && l[i] <= n);
      assert(1 <= r[i] && r[i] <= n);
      assert(l[i] < r[i]);

      r[i]++;
      int len = r[i] - l[i];
      med[i] = rm.range_median(l[i], r[i]).y;
      smaller[i] = rm.range_count_smaller(l[i], r[i], med[i], 0);
      bigger[i] = len - rm.range_count_smaller(l[i], r[i], med[i], 1);

      ll z = 0;
      z -= rm.rect_fold(l[i], r[i], 0, med[i]);
      z += rm.rect_fold(l[i], r[i], med[i] + 1, inf);

      z -= ll(len / 2 - smaller[i]) * med[i];
      z += ll((len - len / 2) - bigger[i]) * med[i];

      if(len % 2 == 1) z -= med[i];

      sum16 ^= z % N;
      sum40 ^= z % (1ll << 40);
      cout << z << "\n";
    }
  }
  return 0;
}
yukicoder

結果

テストケース

ソースコード
