#396838 (C++17) No.925 紲星 Extra

• 問題: No.925 紲星 Extra
• ユーザー: ei1333333
• 提出日時: 2019-11-08 23:07:40
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: MLE
• 実行時間: -
• コード長: 18,511 bytes
• コンパイル時間: 3,239 ms
• コンパイル使用メモリ: 234,016 KB
• 実行使用メモリ: 814,720 KB
• 最終ジャッジ日時: 2024-09-15 02:16:39
• 合計ジャッジ時間: 10,387 ms
• ジャッジサーバーID （参考情報）: judge3 / judge6

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,812 KB
testcase_01	AC	2 ms; 6,816 KB
testcase_02	AC	2 ms; 6,940 KB
testcase_03	AC	192 ms; 66,048 KB
testcase_04	AC	155 ms; 46,848 KB
testcase_05	MLE	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-

ソースコード

#include <bits/stdc++.h>

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;


const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

template< typename F >
struct FixPoint : F {
  FixPoint(F &&f) : F(forward< F >(f)) {}

  template< typename... Args >
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward< Args >(args)...);
  }
};

template< typename F >
inline decltype(auto) MFP(F &&f) {
  return FixPoint< F >{forward< F >(f)};
}

// かずまさんありがとう
using COL = bool;
const COL RED = false, BLACK = true;

class fid {

  struct node {
    COL color;
    int size;
    bool val;
    int all;
    node *p, *ch[2];

    node() : color(BLACK), size(0), val(0), all(0), p(nullptr), ch{nullptr, nullptr} {}

    node(COL c, bool v, node *par, node *l, node *r) : color(c), size(1), val(v), all(v), p(par), ch{l, r} {}
  } *NIL, *root;

  node *new_node(bool val) const {
    return new node(RED, val, NIL, NIL, NIL);
  }

  void update(node *x) {
    x->size = x->ch[0]->size + 1 + x->ch[1]->size;
    x->all = x->ch[0]->all + x->val + x->ch[1]->all;
  }

  void update_up(node *x) {
    while(x != NIL) update(x), x = x->p;
  }

  void rotate(node *x, int b) {
    node *y = x->ch[1 - b];
    x->ch[1 - b] = y->ch[b];
    if(y->ch[b] != NIL) {
      y->ch[b]->p = x;
    }
    y->p = x->p;
    if(x->p == NIL) {
      root = y;
    } else {
      x->p->ch[x != x->p->ch[0]] = y;
    }
    y->ch[b] = x;
    x->p = y;
    update(x);
    update(y);
  }

  void insert_fix(node *x) {
    while(x->p->color == RED) {
      int b = (x->p != x->p->p->ch[0]);
      node *y = x->p->p->ch[1 - b];
      if(y->color == RED) {
        x->p->color = BLACK;
        y->color = BLACK;
        x->p->p->color = RED;
        x = x->p->p;
        continue;
      }
      if(x == x->p->ch[1 - b]) {
        x = x->p;
        rotate(x, b);
      }
      x->p->color = BLACK;
      x->p->p->color = RED;
      rotate(x->p->p, 1 - b);
    }
    root->color = BLACK;
  }

  void transplant(node *u, node *v) {
    if(u->p == NIL) {
      root = v;
    } else {
      u->p->ch[u != u->p->ch[0]] = v;
    }
    v->p = u->p;
  }

  void erase_fix(node *x) {
    while(x != root && x->color == BLACK) {
      int b = (x != x->p->ch[0]);
      node *w = x->p->ch[1 - b];
      if(w->color == RED) {
        w->color = BLACK;
        x->p->color = RED;
        rotate(x->p, b);
        w = x->p->ch[1 - b];
      }
      if(w->ch[b]->color == BLACK && w->ch[1 - b]->color == BLACK) {
        w->color = RED;
        x = x->p;
        continue;
      }
      if(w->ch[1 - b]->color == BLACK) {
        w->ch[b]->color = BLACK;
        w->color = RED;
        rotate(w, 1 - b);
        w = x->p->ch[1 - b];
      }
      w->color = x->p->color;
      x->p->color = BLACK;
      w->ch[1 - b]->color = BLACK;
      rotate(x->p, b);
      x = root;
    }
    x->color = BLACK;
  }

  node *find_first(node *x) const {
    while(x->ch[0] != NIL) x = x->ch[0];
    return x;
  }

  node *find(node *t, int k) const {
    if(k < 0 || t->size <= k) return NIL;
    node *x = t;
    while(x->ch[0]->size != k) {
      if(k < x->ch[0]->size) {
        x = x->ch[0];
      } else {
        k -= x->ch[0]->size + 1;
        x = x->ch[1];
      }
    }
    return x;
  }

  int find(node *t, int l, int r) const {
    if(t == NIL || r <= 0 || t->size <= l) return 0;
    if(l <= 0 && t->size <= r) return t->all;
    int c = t->ch[0]->size;
    return find(t->ch[0], l, r) + (l <= c && c < r ? t->val : 0) + find(t->ch[1], l - (c + 1), r - (c + 1));
  }

public:

  fid() : NIL(new node()), root(NIL) {}

  int size() const {
    return root->size;
  }

  void insert(int k, bool b) {
    node *y = NIL, *v = new_node(b);
    if(root == NIL) {
      root = v;
    } else if(k == 0) {
      y = find_first(root);
      y->ch[0] = v;
    } else {
      y = find(root, k - 1);
      if(y->ch[1] == NIL) {
        y->ch[1] = v;
      } else {
        y = find_first(y->ch[1]);
        y->ch[0] = v;
      }
    }
    v->p = y;
    update_up(y);
    insert_fix(v);
  }

  void erase(int k) {
    node *x = find(root, k);
    node *y = x, *z;
    COL c = y->color;
    if(x->ch[0] == NIL) {
      z = x->ch[1];
      transplant(x, x->ch[1]);
    } else if(x->ch[1] == NIL) {
      z = x->ch[0];
      transplant(x, x->ch[0]);
    } else {
      y = find_first(x->ch[1]);
      c = y->color;
      z = y->ch[1];
      if(y->p == x) {
        z->p = y;
      } else {
        transplant(y, y->ch[1]);
        y->ch[1] = x->ch[1];
        y->ch[1]->p = y;
      }
      transplant(x, y);
      y->ch[0] = x->ch[0];
      y->ch[0]->p = y;
      y->color = x->color;
      update(y);
    }
    update_up(z->p);
    if(c == BLACK) erase_fix(z);
  }

  bool find(int k) const {
    return find(root, k)->val;
  }

  int rank(int k, bool b) const {
    return b ? find(root, 0, k) : k - find(root, 0, k);
  }

  int rank(int l, int r, bool b) const {
    return b ? find(root, l, r) : r - l - find(root, l, r);
  }

  int select(int k, bool b) const {
    int res = 0;
    node *x = root;
    while(true) {
      assert(x != NIL);
      int c = b ? x->ch[0]->all : x->ch[0]->size - x->ch[0]->all;
      if(k == c && x->val == b) return res + x->ch[0]->size;
      if(k < c) {
        x = x->ch[0];
      } else {
        k -= c + (x->val == b);
        res += x->ch[0]->size + 1;
        x = x->ch[1];
      }
    }
  }

  int select(int l, int k, bool b) const {
    return select(k + rank(l, b), b);
  }
};

template< typename T >
class red_black_tree {

  struct node {
    COL color;
    int size;
    T val;
    node *p, *ch[2];

    node() : color(BLACK), size(0), val(), p(nullptr), ch{nullptr, nullptr} {}

    node(COL c, T v, node *par, node *l, node *r) : color(c), size(1), val(v), p(par), ch{l, r} {}
  } *NIL, *root;

  node *new_node(T val) const {
    return new node(RED, val, NIL, NIL, NIL);
  }

  void update(node *x) {
    x->size = x->ch[0]->size + 1 + x->ch[1]->size;
  }

  void update_up(node *x) {
    while(x != NIL) update(x), x = x->p;
  }

  void rotate(node *x, int b) {
    node *y = x->ch[1 - b];
    x->ch[1 - b] = y->ch[b];
    if(y->ch[b] != NIL) {
      y->ch[b]->p = x;
    }
    y->p = x->p;
    if(x->p == NIL) {
      root = y;
    } else {
      x->p->ch[x != x->p->ch[0]] = y;
    }
    y->ch[b] = x;
    x->p = y;
    update(x);
    update(y);
  }

  void insert_fix(node *x) {
    while(x->p->color == RED) {
      int b = (x->p != x->p->p->ch[0]);
      node *y = x->p->p->ch[1 - b];
      if(y->color == RED) {
        x->p->color = BLACK;
        y->color = BLACK;
        x->p->p->color = RED;
        x = x->p->p;
        continue;
      }
      if(x == x->p->ch[1 - b]) {
        x = x->p;
        rotate(x, b);
      }
      x->p->color = BLACK;
      x->p->p->color = RED;
      rotate(x->p->p, 1 - b);
    }
    root->color = BLACK;
  }

  void transplant(node *u, node *v) {
    if(u->p == NIL) {
      root = v;
    } else {
      u->p->ch[u != u->p->ch[0]] = v;
    }
    v->p = u->p;
  }

  void erase_fix(node *x) {
    while(x != root && x->color == BLACK) {
      int b = (x != x->p->ch[0]);
      node *w = x->p->ch[1 - b];
      if(w->color == RED) {
        w->color = BLACK;
        x->p->color = RED;
        rotate(x->p, b);
        w = x->p->ch[1 - b];
      }
      if(w->ch[b]->color == BLACK && w->ch[1 - b]->color == BLACK) {
        w->color = RED;
        x = x->p;
        continue;
      }
      if(w->ch[1 - b]->color == BLACK) {
        w->ch[b]->color = BLACK;
        w->color = RED;
        rotate(w, 1 - b);
        w = x->p->ch[1 - b];
      }
      w->color = x->p->color;
      x->p->color = BLACK;
      w->ch[1 - b]->color = BLACK;
      rotate(x->p, b);
      x = root;
    }
    x->color = BLACK;
  }

  node *find_first(node *x) const {
    if(x == NIL) return NIL;
    while(x->ch[0] != NIL) x = x->ch[0];
    return x;
  }

  node *find(node *t, int k) const {
    if(k < 0 || t->size <= k) return NIL;
    node *x = t;
    while(x->ch[0]->size != k) {
      if(k < x->ch[0]->size) {
        x = x->ch[0];
      } else {
        k -= x->ch[0]->size + 1;
        x = x->ch[1];
      }
    }
    return x;
  }

public:

  red_black_tree() : NIL(new node()), root(NIL) {}

  T find(int k) const {
    return find(root, k)->val;
  }

  void update(int k, T val) {
    node *t = find(root, k);
    t->val = val;
  }

  void insert(int k, T val) {
    node *y = NIL, *v = new_node(val);
    if(root == NIL) {
      root = v;
    } else if(k == 0) {
      y = find_first(root);
      y->ch[0] = v;
    } else {
      y = find(root, k - 1);
      if(y->ch[1] == NIL) {
        y->ch[1] = v;
      } else {
        y = find_first(y->ch[1]);
        y->ch[0] = v;
      }
    }
    v->p = y;
    update_up(y);
    insert_fix(v);
  }

  void erase(int k) {
    node *x = find(root, k);
    node *y = x, *z;
    COL c = y->color;
    if(x->ch[0] == NIL) {
      z = x->ch[1];
      transplant(x, x->ch[1]);
    } else if(x->ch[1] == NIL) {
      z = x->ch[0];
      transplant(x, x->ch[0]);
    } else {
      y = find_first(x->ch[1]);
      c = y->color;
      z = y->ch[1];
      if(y->p == x) {
        z->p = y;
      } else {
        transplant(y, y->ch[1]);
        y->ch[1] = x->ch[1];
        y->ch[1]->p = y;
      }
      transplant(x, y);
      y->ch[0] = x->ch[0];
      y->ch[0]->p = y;
      y->color = x->color;
      update(y);
    }
    update_up(z->p);
    if(c == BLACK) erase_fix(z);
  }

};


template< typename T >
class dynamic_wavelet_matrix {
  T h;
  red_black_tree< T > all;
  vector< fid > data;
  vector< int > mid;

public:
  dynamic_wavelet_matrix(T h_ = 30) : h(h_), data(h), mid(h) {}

  void insert(int k, T val) {
    all.insert(k, val);
    for(T b = 0; b < h; b++) {
      bool d = (val >> (h - 1 - b)) & 1;
      data[b].insert(k, d);
      if(d) {
        k = data[b].rank(k, d) + mid[b];
      } else {
        k = data[b].rank(k, d);
        mid[b]++;
      }
    }
  }

  void erase(int k) {
    T val = all.find(k);
    all.erase(k);
    for(T b = 0; b < h; b++) {
      bool d = (val >> (h - 1 - b)) & 1;
      data[b].erase(k);
      if(d) {
        k = data[b].rank(k, d) + mid[b];
      } else {
        k = data[b].rank(k, d);
        mid[b]--;
      }
    }
  }

  T get(int k) const {
    return all.find(k);
  }

  int rank(int p, T val) {
    return rank(0, p, val);
  }

  int rank(int l, int r, T val) {
    if(val >> h) return 0;
    for(T b = 0; b < h; b++) {
      if(val & ((T) 1 << (h - 1 - b))) {
        l = data[b].rank(l, true) + mid[b];
        r = data[b].rank(r, true) + mid[b];
      } else {
        l = data[b].rank(l, false);
        r = data[b].rank(r, false);
      }
    }
    return r - l;
  }

  int rank_less_than(int l, int r, T ub) {
    if(ub >> h) return r - l;
    int res = 0;
    for(T b = 0; b < h; b++) {
      bool d = (ub >> (h - 1 - b)) & 1;
      int lcnt = data[b].rank(l, d);
      int rcnt = data[b].rank(r, d);
      if(d) res += (r - l) - (rcnt - lcnt);
      l = lcnt;
      r = rcnt;
      if(d) {
        l += mid[b];
        r += mid[b];
      }
    }
    return res;
  }

  int rank_range(int l, int r, T lb, T ub) {
    return rank_less_than(l, r, ub) - rank_less_than(l, r, lb);
  }

  int select(int x, T val) {
    static int left[h];
    int l = 0, r = data[0].size();
    for(T b = 0; b < h; b++) {
      left[b] = l;
      if(val & ((T) 1 << (h - 1 - b))) {
        l = data[b].rank(l, true) + mid[b];
        r = data[b].rank(r, true) + mid[b];
      } else {
        l = data[b].rank(l, false);
        r = data[b].rank(r, false);
      }
    }
    for(int b = h - 1; b >= 0; b--) {
      x = data[b].select(left[b], x, (bool) ((val >> (h - 1 - b)) & 1)) - left[b];
    }
    return x;
  }

  int select(int l, int r, int x, T val) {
    return select(x + rank(l, val), val);
  }

  T kth_element(int l, int r, int k) const {
    T res = 0;
    for(T b = 0; b < h; b++) {
      int cnt = data[b].rank(l, r, false);
      res <<= 1;
      if(k >= cnt) {
        l = data[b].rank(l, true) + mid[b];
        r = data[b].rank(r, true) + mid[b];
        k -= cnt;
        res |= 1;
      } else {
        l = data[b].rank(l, false);
        r = data[b].rank(r, false);
      }
    }
    return res;
  }
};


using ll = long long;


struct RMQ {
  using type = pair< int64, int >;

  static type id() { return type(0, 0); }

  static type op(const type &l, const type &r) { return type(l.first + r.first, l.second + r.second); }
};

template< typename M >
class node {
  using T = typename M::type;
public:
  T val;
  node< M > *l, *r;

  node(T val_) : val(val_), l(nullptr), r(nullptr) {}
};

template< typename M >
class dynamic_segment_tree {
  using T = typename M::type;
  const ll n;
  node< M > *root;

  T value(node< M > *t) {
    return t ? t->val : M::id();
  }

  T sub(ll l, ll r, node< M > *n, ll lb, ll ub) {
    if(!n || ub <= l || r <= lb) return M::id();
    if(l <= lb && ub <= r) return n->val;
    ll c = (lb + ub) / 2;
    return M::op(sub(l, r, n->l, lb, c), sub(l, r, n->r, c, ub));
  }

  node< M > *suc(ll p, node< M > *t, ll lb, ll ub, T val) {
    if(!t) t = new node< M >(M::id());
    if(lb + 1 == ub) {
      t->val = val;
      return t;
    }
    ll c = (lb + ub) / 2;
    if(p < c) t->l = suc(p, t->l, lb, c, val);
    else t->r = suc(p, t->r, c, ub, val);
    t->val = M::op(value(t->l), value(t->r));
    return t;
  }

public:
  dynamic_segment_tree(ll n_) :
      n(1ll << (ll) ceil(log2(n_))), root(nullptr) {
  }

  void update(ll p, T val) {
    root = suc(p, root, 0, n, val);
  }

  T find(ll l, ll r) {
    return sub(l, r + 1, root, 0, n);
  }
};

template< typename M >
class node2 {
  using T = typename M::type;
public:
  dynamic_segment_tree< M > val;
  node2< M > *l, *r;

  node2(ll size) : val(size), l(nullptr), r(nullptr) {}
};

template< typename M >
class dynamic_segment_tree2 {
  using T = typename M::type;
  const ll h, w;
  node2< M > *root;

  T value(node2< M > *t, ll p) {
    return t ? t->val.find(p, p) : M::id();
  }

  T sub(ll li, ll lj, ll ri, ll rj, node2< M > *n, ll lb, ll ub) {
    if(!n || ub <= li || ri <= lb) return M::id();
    if(li <= lb && ub <= ri) {
      return n->val.find(lj, rj);
    }
    ll c = (lb + ub) / 2;
    return M::op(sub(li, lj, ri, rj, n->l, lb, c), sub(li, lj, ri, rj, n->r, c, ub));
  }

  node2< M > *suc(ll pi, ll pj, node2< M > *t, ll lb, ll ub, T val) {
    if(!t) t = new node2< M >(w);
    if(lb + 1 == ub) {
      t->val.update(pj, val);
      return t;
    }
    ll c = (lb + ub) / 2;
    if(pi < c) t->l = suc(pi, pj, t->l, lb, c, val);
    else t->r = suc(pi, pj, t->r, c, ub, val);
    t->val.update(pj, M::op(value(t->l, pj), value(t->r, pj)));
    return t;
  }

public:
  dynamic_segment_tree2(ll h_, ll w_) :
      h(1ll << (ll) ceil(log2(h_))), w(w_), root(nullptr) {}

  void update(ll pi, ll pj, T val) {
    root = suc(pi, pj, root, 0, h, val);
  }

  T find(ll li, ll lj, ll ri, ll rj) {
    return sub(li, lj, ri + 1, rj, root, 0, h);
  }
};

template< class T >
struct BinaryIndexedTree {
  vector< T > data;

  BinaryIndexedTree(int sz) {
    data.assign(++sz, 0);
  }

  T sum(int k) {
    T ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }

  void add(int k, T x) {
    for(++k; k < data.size(); k += k & -k) data[k] += x;
  }
};

int main() {
  int N, Q;
  cin >> N >> Q;
  vector< int64 > A(N);
  cin >> A;

  int64 s = 0;
  const int B = 1000;
  for(int x = 0; x < Q; x += B) {
    int L = x;
    int R = min(x + B, Q);


    dynamic_wavelet_matrix< int64 > mat(41);
    for(int i = 0; i < N; i++) {
      mat.insert(i, A[i]);
    }
    const int64 two16 = 65536;
    const int64 two40 = 1099511627776;
    dynamic_segment_tree2< RMQ > seg(N, two40);
    for(int i = 0; i < N; i++) {
      seg.update(i, A[i], make_pair(A[i], 1));
    }

    BinaryIndexedTree< int64 > bit(N);
    for(int i = 0; i < N; i++) {
      bit.add(i, A[i]);
    }

    for(int i = 0; i < R - L; i++) {
      int64 t, l, r;
      cin >> t >> l >> r;
      if(t == 1) {

        l ^= s % two16;
        r ^= s % two40;
        --l;
        mat.erase(l);
        seg.update(l, A[l], make_pair(0, 0));
        bit.add(l, -A[l]);
        A[l] = r;
        bit.add(l, A[l]);
        seg.update(l, A[l], make_pair(A[l], 1));
        mat.insert(l, A[l]);
      } else {

        l ^= s % two16;
        r ^= s % two16;
        if(l > r) swap(l, r);

        --l;
        int md = (r - l) / 2;
        int64 val = mat.kth_element(l, r, md);


        auto ret = seg.find(l, val, r - 1, infll);


        int64 upcnt = ret.second;
        int64 upsum = ret.first;

        int64 lowcnt = (r - l) - upcnt;
        int64 lowsum = bit.sum(r - 1) - bit.sum(l - 1) - upsum;

        int64 sum = (upsum - upcnt * val) + (val * lowcnt - lowsum);
        cout << sum << endl;

        s ^= sum;
      }
    }
  }
}