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

• 問題: No.925 紲星 Extra
• ユーザー: lumc_
• 提出日時: 2019-09-23 22:22:47
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: MLE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 34,747 bytes
• コンパイル時間: 2,750 ms
• コンパイル使用メモリ: 177,868 KB
• 実行使用メモリ: 814,888 KB
• 最終ジャッジ日時: 2024-09-19 04:42:26
• 合計ジャッジ時間: 44,127 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	2 ms; 6,944 KB
testcase_02	AC	2 ms; 6,944 KB
testcase_03	AC	11 ms; 6,944 KB
testcase_04	AC	11 ms; 6,940 KB
testcase_05	AC	2,717 ms; 103,880 KB
testcase_06	AC	2,644 ms; 104,908 KB
testcase_07	AC	2,728 ms; 104,280 KB
testcase_08	AC	1,624 ms; 44,920 KB
testcase_09	AC	811 ms; 31,072 KB
testcase_10	AC	2,608 ms; 98,148 KB
testcase_11	AC	2,533 ms; 109,532 KB
testcase_12	AC	1,873 ms; 84,008 KB
testcase_13	AC	2,895 ms; 462,468 KB
testcase_14	AC	2,112 ms; 46,588 KB
testcase_15	AC	2,849 ms; 457,460 KB
testcase_16	AC	1,734 ms; 98,400 KB
testcase_17	AC	1,096 ms; 88,784 KB
testcase_18	AC	2,611 ms; 105,388 KB
testcase_19	AC	2,511 ms; 98,224 KB
testcase_20	AC	2,406 ms; 111,792 KB
testcase_21	MLE	-

ソースコード

#if 0

想定解 : スケープゴート木

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

alpha = 7/10

rebuildの計算量は O(N lg^2 N) だけど
insert/delete は O(N lg N) なきがする

alphaの大きさ [0.5, 1.0] : 何が嬉しくなるか (たぶん)
小さなalpha : insert/delete の時間, 木の高さ
大きなalpha : rebuild の時間, 回数

6/11 はたぶん欲張りすぎた
2/3 もだめだった, 調整ゲー

上/下のスケゴのステータスは変えたほうがいいかもしれないというのはありそう

#endif

#if 0

スケープゴート木

* ScapegoatTreeDriver はスケゴ以外にも乗せることを想定した名前，そう変える
* 必要ない機能は一部省略
  * split, mergeなどはなし
  * split_min はない
  * inlcude_i, include_j もなし
  * lazy なし
* union はサイズに対し線形時間 (これで十分)

#endif

#define NDEBUG

#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; }
};
/// }}}--- ///

#define SCAPEGOAT_SAVE_SIZE 1

// scapegoat tree {{{

#include <cassert>
#include <cmath>
#include <tuple>
#include <vector>
namespace scapegoat_tree {

// node {{{
template < class Key, class M_act >
struct Node {
  using size_type = std::size_t;
  using pointer = Node *;
  using const_pointer = const Node *;
  using Monoid = typename M_act::Monoid;
  using T = typename Monoid::T;

#if SCAPEGOAT_SAVE_SIZE
  size_type sz = 0;
#endif

  pointer ch[2] = {0, 0}; // l = 0, r = 1
  Key key;
  T value, accum;

  template < class K, class U >
  Node(K &&key, U &&value)
      : key(std::forward< K >(key)), value(value), accum(std::forward< U >(value)) {
#if SCAPEGOAT_SAVE_SIZE
    sz = 1;
#endif
  }
  template < class K >
  Node(K &&key) : Node(std::forward< Key >(key), Monoid::identity()) {}

  static size_type size(const_pointer p) {
    if(!p) return 0;
#if SCAPEGOAT_SAVE_SIZE
    return p->sz;
#else
    return size(p->ch[0]) + 1 + size(p->ch[1]); // definition-base
#endif
  }

  static bool is_nil(const_pointer p) { return !p; }

  static const T &get_accum(const_pointer p) {
    static auto identity = Monoid::identity();
    if(!p) return identity;
    return p->accum;
  }

  static pointer update(pointer p, bool is_identity = 0) {
    if(is_nil(p)) return p; // TODO : assert ?
#if SCAPEGOAT_SAVE_SIZE
    p->sz = size(p->ch[0]) + 1 + size(p->ch[1]);
#endif
    if(!is_identity) {
      p->accum =
          Monoid::op(Monoid::op(get_accum(p->ch[0]), p->value), get_accum(p->ch[1]));
    }
    return p;
  }

  static pointer copy(const_pointer p) {
    static std::vector< const_pointer > v;

    v.clear();
    get_all_ptr_dfs(p, v);
    std::vector< pointer > w;
    for(const_pointer e : v) w.push_back(new Node(e->key, e->value));
    return make_perfect(w, 0, w.size());
  }

  // p を根とする部分木を rebuild して新しい根のポインターを返す
  static pointer rebuild(pointer p) {
    static std::vector< pointer > v;

    v.clear();
    get_all_ptr_dfs(p, v);
    return make_perfect(v, 0, v.size());
  }

  // make perfect balanced binary search tree
  static pointer make_perfect(std::vector< pointer > &pts, size_type l, size_type r) {
    if(l == r) return 0;
    size_type m = (l + r) / 2;
    pts[m]->ch[0] = make_perfect(pts, l, m);
    pts[m]->ch[1] = make_perfect(pts, m + 1, r);
    update(pts[m]);
    return pts[m];
  }

  template < class P >
  static void get_all_ptr_dfs(P p, std::vector< P > &v) {
    if(!p) return;
    get_all_ptr_dfs< P >(p->ch[0], v);
    v.push_back(p);
    get_all_ptr_dfs< P >(p->ch[1], v);
  }

  static std::vector< Key > get_all(const_pointer p) {
    std::vector< Key > v;
    get_all_dfs(p, v);
    return v;
  }
  static void get_all_dfs(const_pointer p, std::vector< Key > &v) {
    if(!p) return;
    get_all_dfs(p->ch[0], v);
    v.push_back(p->key);
    get_all_dfs(p->ch[1], v);
  }

  static pointer splice(pointer p) {
    if(!p->ch[0]) {
      pointer q = p->ch[1];
      delete p;
      return q;
    } else if(!p->ch[1]) {
      pointer q = p->ch[0];
      delete p;
      return q;
    } else {
      pointer s, t;
      std::tie(s, t) = split_max(p->ch[0]);
      t->ch[0] = s;
      t->ch[1] = p->ch[1];
      delete p;
      update(t);
      return t;
    }
  }

  static std::pair< pointer, pointer > split_max(pointer p) {
    assert(p);
    pointer t = p, s = 0;
    static std::vector< pointer > pts;
    assert(pts.empty());

    while(t->ch[1]) {
      pts.push_back(t);
      s = t;
      t = t->ch[1];
    }
    assert(t && !t->ch[1]);

    if(s) {
      s->ch[1] = t->ch[0];
      update(s);
      s = p;
    } else
      s = p->ch[0];

    t->ch[0] = 0;
    while(pts.size()) {
      update(pts.back());
      pts.pop_back();
    }
    update(t);
    return {s, t};
  }

  static T fold(const_pointer p, Key keyL, Key keyR, bool include_l, bool include_r) {
    while(p) {
      if(p->key < keyL || (!include_l && !(keyL < p->key)))
        p = p->ch[1];
      else if(keyR < p->key || (!include_r && !(p->key < keyR)))
        p = p->ch[0];
      else
        break;
    }

    if(!p) return Monoid::identity();

    T x = p->value;

    const_pointer pl = p->ch[0], pr = p->ch[1];

    while(pl) {
      if(pl->key < keyL) {
        pl = pl->ch[1];
      } else {
        x = Monoid::op(get_accum(pl->ch[1]), std::move(x));
        if(keyL < pl->key) {
          x = Monoid::op(pl->value, std::move(x));
          pl = pl->ch[0];
        } else {
          if(include_l) x = Monoid::op(pl->value, std::move(x));
          break;
        }
      }
    }

    while(pr) {
      if(keyR < pr->key) {
        pr = pr->ch[0];
      } else {
        x = Monoid::op(std::move(x), get_accum(pr->ch[0]));
        if(pr->key < keyR) {
          x = Monoid::op(std::move(x), pr->value);
          pr = pr->ch[1];
        } else {
          if(include_r) x = Monoid::op(std::move(x), pr->value);
          break;
        }
      }
    }

    return x;
  }

  // set operations {{{
  static pointer union_(pointer t1, pointer t2) {
    if(is_nil(t1)) return t2;
    if(is_nil(t2)) return t1;

    static std::vector< pointer > v1, v2;
    v1.clear(), v2.clear();

    get_all_ptr_dfs(t1, v1);
    get_all_ptr_dfs(t2, v2);

    static std::vector< pointer > w;
    w.clear();

    size_type i1 = 0, i2 = 0;
    while(i1 < v1.size() || i2 < v2.size()) {
      if(i2 == v2.size()) {
        w.push_back(v1[i1++]);
      } else if(i1 == v1.size()) {
        w.push_back(v2[i2++]);
      } else {
        if(v1[i1]->key < v2[i2]->key) {
          w.push_back(v1[i1++]);
        } else if(v2[i2]->key < v1[i1]->key) {
          w.push_back(v2[i2++]);
        } else {
          w.push_back(v1[i1++]);
          delete v2[i2++];
        }
      }
    }

    return make_perfect(w, 0, w.size());
  }
  // }}}

  // order statistics operations {{{
  static std::pair< Key, T > select(pointer p, size_type k) {
    assert(!is_nil(p));
    if(k < size(p->ch[0])) return select(p->ch[0], k);
    k -= size(p->ch[0]);
    if(k == 0) return {p->key, p->value};
    k--;
    return select(p->ch[1], k);
  }

  // count {{{
  static size_type count(const_pointer p, const Key &keyL, const Key &keyR,
                         bool include_l, bool include_r) {
    if(keyR < keyL) return 0;
    const_pointer t = p;
    while(!is_nil(t)) {
      if(!(keyL < t->key)) {
        // key <= keyL
        if(include_l && !(t->key < keyL))
          return 1 + count_lesser(t->ch[1], keyR, include_r);
        t = t->ch[1];
      } else if(!(t->key < keyR)) {
        // keyR <= key
        if(include_r && !(keyR < t->key))
          return 1 + count_greater(t->ch[0], keyL, include_l);
        t = t->ch[0];
      } else {
        // keyL < key < keyR
        return count_greater(t->ch[0], keyL, include_l) + 1 +
               count_lesser(t->ch[1], keyR, include_r);
      }
    }
    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(!is_nil(t)) {
      if(t->key < keyR) {
        res += size(t->ch[0]) + 1;
        t = t->ch[1];
      } else {
        // keyR <= key
        if(include_bound && !(keyR < t->key)) return res + size(t->ch[0]) + 1;
        t = t->ch[0];
      }
    }
    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(!is_nil(t)) {
      if(keyL < t->key) {
        res += size(t->ch[1]) + 1;
        t = t->ch[0];
      } else {
        // key <= keyL
        if(include_bound && !(t->key < keyL)) return res + size(t->ch[1]) + 1;
        t = t->ch[1];
      }
    }
    return res;
  }
  // }}}
  // }}}

  static void delete_all(pointer p) {
    if(is_nil(p)) return;
    delete_all(p->ch[0]);
    delete_all(p->ch[1]);
    delete p;
  }
};
// }}}

// scapegoat tree {{{
template < class Key, class M_act >
struct ScapegoatTree {
  using node_type = Node< Key, M_act >;
  using size_type = std::size_t;
  using pointer = Node< Key, M_act > *;
  using const_pointer = const Node< Key, M_act > *;
  using Monoid = typename M_act::Monoid;
  using T = typename Monoid::T;

  pointer p = 0;

  size_type rsz = 0; // size of real nodes including removed nodes
  size_type vsz = 0; // size of valid nodes

  ScapegoatTree() {}
  ~ScapegoatTree() { clear(); }

public:
  ScapegoatTree(const ScapegoatTree &sgt) { *this = sgt; }
  ScapegoatTree(ScapegoatTree &&sgt) { *this = std::move(sgt); }

  ScapegoatTree &operator=(const ScapegoatTree &sgt) {
    p = node_type::copy(sgt.p);
    rsz = vsz = sgt.vsz;
    return *this;
  }
  ScapegoatTree &operator=(ScapegoatTree &&sgt) {
    p = sgt.p;
    rsz = sgt.rsz;
    vsz = sgt.vsz;
    sgt.p = 0;
    sgt.rsz = sgt.vsz = 0;
    return *this;
  }

  // log_{1/alpha}(rsz) = log(rsz) / log(1/alpha)
  // log_{3/2}(rsz) = log(rsz) / log(3/2)
  // TODO : name
  bool is_unbalance(size_type deepest) const {
    // deepest > log_{1/alpha}(rsz)

    constexpr double inv_log_inv_alpha = 1.0 / std::log(10.0 / 7.0);
    return deepest > std::log(rsz) * inv_log_inv_alpha;
  }

  // a : parent
  // b : child
  bool is_weight_balanced(size_type a, size_type b) const {
    assert(a > b);
    // alpha a >= b

    return 7 * a >= 10 * b;
  }

  // BST operations {{{
public:
  template < class K, class = typename std::enable_if<
                          std::is_convertible< K &&, Key >::value >::type >
  bool insert(K &&key) {
    return insert(std::forward< K >(key), Monoid::identity(), 1);
  }

  // NOTE : (グローバルな) 親ありきの関数というのが存在する
  template < class K, class U, class = typename std::enable_if<
                                   std::is_convertible< K &&, Key >::value &&
                                   std::is_convertible< U &&, T >::value >::type >
  bool insert(K &&key, U &&x, bool is_identity = 0) {
    if(!p) {
      p = new node_type(std::forward< K >(key), std::forward< U >(x));
      ++rsz, ++vsz;
      return 0;
    }

    static std::vector< std::pair< pointer, bool > > pts;
    assert(pts.empty());
    pointer t = p;

    while(t) {
      bool R = t->key < key;
      pts.emplace_back(t, R);

      if(!R && !(key < t->key)) {
        // found
        // TODO : replace
        pts.clear();
        return 1;
      }
      t = t->ch[R];
    }

    ++rsz, ++vsz;

    pointer u;
    bool R;
    std::tie(u, R) = pts.back();
    assert(!u->ch[R]);
    u->ch[R] = new node_type(std::forward< K >(key), std::forward< U >(x));
    node_type::update(u, is_identity);

    size_type is_unb = is_unbalance(pts.size()); // TODO : name
    pointer w = 0, v = 0;

    while(pts.size()) {
      std::tie(w, std::ignore) = pts.back();
      pts.pop_back();
      if(pts.size()) {
        std::tie(v, std::ignore) = pts.back();
        node_type::update(v, is_identity);
        if(is_unb) {
          if(!is_weight_balanced(node_type::size(v), node_type::size(w))) {
            // partial rebuild
            pointer u = node_type::rebuild(v);
            if(pts.size() >= 2) {
              pointer z;
              bool R;
              std::tie(z, R) = pts[pts.size() - 2];
              z->ch[R] = u;
            } else {
              assert(p == v);
              p = u;
            }
            is_unb = 0;
          }
        }
      }
    }

    assert(pts.empty());
    return 0;
  }

public:
  template < class K, class = typename std::enable_if<
                          std::is_convertible< K &&, Key >::value >::type >
  bool erase(K &&key) {
    if(!p) return 0;

    static std::vector< pointer > pts;
    assert(pts.empty());

    pointer t = p;
    pointer q = 0;
    bool R;

    while(t) {
      bool R2 = t->key < key;

      if(!R2 && !(key < t->key)) break;
      pts.emplace_back(t);
      q = t;
      R = R2;
      t = t->ch[R2];
    }

    if(!t) {
      // not found
      pts.clear();
      return 0;
    }

    // found

    assert(vsz);
    --vsz;
    (q ? q->ch[R] : p) = node_type::splice(t);

    if(2 * vsz < rsz) {
      // global rebuild
      p = node_type::rebuild(p);
      pts.clear();
      rsz = vsz;
    } else {
      while(pts.size()) {
        node_type::update(pts.back());
        pts.pop_back();
      }
    }

    return 1;
  }

public:
  std::vector< Key > get_all() const { return node_type::get_all(p); }

public:
  T fold(Key keyL, Key keyR) const { return node_type::fold(p, keyL, keyR, 1, 0); }
  T fold(Key keyL, Key keyR, bool include_l, bool include_r) const {
    return node_type::fold(p, keyL, keyR, include_l, include_r);
  }

public:
  size_type size() const { return vsz; }

public:
  void clear() {
    node_type::delete_all(p);
    p = 0;
    rsz = vsz = 0;
  }

public:
  static bool is_nil(const_pointer p) { return !p; }

  // }}}

  // set operations {{{
public:
  ScapegoatTree &union_with(ScapegoatTree &&sgt) {
    p = node_type::union_(p, sgt.p);
    sgt.p = 0;
    sgt.vsz = sgt.rsz = 0;
    rsz = vsz = node_type::size(p);
    return *this;
  }
  // }}}

  // order statistics operations {{{
  std::pair< Key, T > select(size_type k) const { return node_type::select(p, k); }
  // count {{{
public:
  size_type count(const Key &keyL, const Key &keyR) const {
    return node_type::count(p, keyL, keyR, 1, 0);
  }
  size_type count(const Key &keyL, const Key &keyR, bool include_l,
                  bool include_r) const {
    return node_type::count(p, keyL, keyR, include_l, include_r);
  }

  size_type count_lesser(const Key &keyR, bool include_r) const {
    return node_type::count_lesser(p, keyR, include_r);
  }

  size_type count_greater(const Key &keyL, bool include_l) const {
    return node_type::count_greater(p, keyL, include_l);
  }
  // }}}
  // }}}
};

// }}}
}

// }}}

// TODO : name
// ScapegoatTreeDriver {{{
namespace scapegoat_tree {

template < class _T, class _Monoid, class Index >
struct ScapegoatTreeDriver {
  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;
    }
  };

  using T_SET = ScapegoatTree< Point, Nothing_M_act< Monoid > >;
  struct Driver_Monoid {
    using T = T_SET;
    static T op(T a, T b) { return std::move(a.union_with(std::move(b))); }
    static T identity() { return T(); }
  };
  struct Driver_M_act {
    using Monoid = Driver_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 BST = ScapegoatTree< T, Driver_M_act >;
  using pointer = typename BST::pointer;
  using const_pointer = typename BST::const_pointer;

  ScapegoatTree< T, Driver_M_act > sgt;

  ScapegoatTreeDriver() {}

  static ScapegoatTreeDriver 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 ScapegoatTreeDriver with3(std::vector< std::tuple< Index, T, X > > v) {
    ScapegoatTreeDriver 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) {
    sgt.insert(v);
    insert_path_to(sgt.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(sgt.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(!BST::is_nil(t)) {
      if(target < t->key) {
        pts.push_back(t);
        t = t->ch[0];
      } else if(t->key < target) {
        pts.push_back(t);
        t = t->ch[1];
      } 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(!BST::is_nil(t)) {
      if(target < t->key) {
        pts.push_back(t);
        t = t->ch[0];
      } else if(t->key < target) {
        pts.push_back(t);
        t = t->ch[1];
      } 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 = sgt.p;

    while(!BST::is_nil(p)) {
      if(p->key < l || (!include_l && !(l < p->key)))
        p = p->ch[1];
      else if(r < p->key || (!include_r && !(p->key < r)))
        p = p->ch[0];
      else
        break;
    }
    if(BST::is_nil(p)) return Monoid::identity();

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

    const_pointer pl = p->ch[0], pr = p->ch[1];

    while(!BST::is_nil(pl)) {
      if(pl->key < l) {
        pl = pl->ch[1];
      } else {
        x = Monoid::op(BST::node_type::get_accum(pl->ch[1]).fold(i, j), std::move(x));
        if(l < pl->key) {
          x = Monoid::op(pl->value.fold(i, j), std::move(x));
          pl = pl->ch[0];
        } else {
          if(include_l) x = Monoid::op(pl->value.fold(i, j), std::move(x));
          break;
        }
      }
    }

    while(!BST::is_nil(pr)) {
      if(r < pr->key) {
        pr = pr->ch[0];
      } else {
        x = Monoid::op(std::move(x), BST::node_type::get_accum(pr->ch[0]).fold(i, j));
        if(pr->key < r) {
          x = Monoid::op(std::move(x), pr->value.fold(i, j));
          pr = pr->ch[1];
        } else {
          if(include_r) x = Monoid::op(std::move(x), pr->value.fold(i, j));
          break;
        }
      }
    }

    return x;
  }

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

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

private:
  Point range_select_dfs(const_pointer p, Index i, Index j, size_type k) const {
    assert(!BST::is_nil(p));
    assert(k < BST::node_type::get_accum(p).count(i, j));
    size_type lsz = BST::node_type::get_accum(p->ch[0]).count(i, j);
    if(k < lsz) {
      return range_select_dfs(p->ch[0], 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).first;
    }
    k -= hsz;
    return range_select_dfs(p->ch[1], i, j, k);
  }
  size_type range_count_smaller_dfs(const_pointer p, Index i, Index j, T x,
                                    bool include_bound) const {
    if(BST::is_nil(p)) return 0;
    if(x < p->key) return range_count_smaller_dfs(p->ch[0], i, j, x, include_bound);
    // p->key <= x
    size_type lsz = BST::node_type::get_accum(p->ch[0]).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->ch[1], 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 BST::node_type::get_accum(sgt.p).count(i, j);
  }
  size_type size() const { return BST::node_type::get_accum(sgt.p).size(); }
};
}
// }}}

template < class T, class Monoid, class Index = long long >
using ScapegoatTreeDriver = scapegoat_tree::ScapegoatTreeDriver< T, Monoid, Index >;

// 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;

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(0 <= n && n < N);
  assert(0 <= q && q < N);

  vector< ll > v(n + 1);

  dump(1);

  vector< tuple< ll, ll, ll > > ini;

  // ScapegoatTreeDriver< ll, RangeSum< ll > > rm;

  for(int i = 1; i <= n; i++) {
    cin >> v[i];
    ini.emplace_back(i, v[i], v[i]);
    // rm.insert(i, v[i], v[i]);
    assert(0 <= v[i] && v[i] < inf);
  }

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

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

  dump(3);

  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);
      // 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);

      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";
    }

    // if(i % 1000 == 0) dump(i);
  }
  return 0;
}