結果

問題 No.925 紲星 Extra
ユーザー pekempeypekempey
提出日時 2019-11-09 00:19:46
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 5,818 ms / 10,000 ms
コード長 7,589 bytes
コンパイル時間 2,273 ms
コンパイル使用メモリ 182,144 KB
実行使用メモリ 465,024 KB
最終ジャッジ日時 2024-09-15 03:14:56
合計ジャッジ時間 67,595 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 3 ms
5,376 KB
testcase_03 AC 24 ms
9,984 KB
testcase_04 AC 25 ms
9,216 KB
testcase_05 AC 4,134 ms
366,464 KB
testcase_06 AC 4,345 ms
368,768 KB
testcase_07 AC 4,258 ms
367,104 KB
testcase_08 AC 2,987 ms
233,600 KB
testcase_09 AC 2,438 ms
210,304 KB
testcase_10 AC 3,325 ms
291,200 KB
testcase_11 AC 5,656 ms
432,896 KB
testcase_12 AC 4,741 ms
385,024 KB
testcase_13 AC 3,018 ms
289,280 KB
testcase_14 AC 2,685 ms
169,472 KB
testcase_15 AC 2,926 ms
336,640 KB
testcase_16 AC 3,938 ms
261,248 KB
testcase_17 AC 2,118 ms
202,112 KB
testcase_18 AC 4,308 ms
370,816 KB
testcase_19 AC 2,709 ms
253,952 KB
testcase_20 AC 5,818 ms
465,024 KB
testcase_21 AC 3,543 ms
439,424 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
 
#define rep(i, n)      for (int i = 0; i < (n); i++)
#define repr(i, n)     for (int i = (n) - 1; i >= 0; i--)
#define repe(i, l, r)  for (int i = (l); i < (r); i++)
#define reper(i, l, r) for (int i = (r) - 1; i >= (l); i--)
#define repi(i, l, r)  for (int i = (l); i <= (r); i++)
#define repir(i, l, r) for (int i = (r); i >= (l); i--)
#define range(a) a.begin(), a.end()
void init_io() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(15); }
 
using namespace std;
using ll = long long;

template<class T>
struct treemultiset {
  ~treemultiset() {
    release(root);
  }
  
private:
  struct node {
    node *l = nullptr;
    node *r = nullptr;
    int h;
    T k;
    int cnt = 0;
    int size = 0;
    ll sum = 0;
  };

  node *root = nullptr;

  void release(node *x) {
    if (!x) return;
    release(x->l);
    release(x->r);
    delete x;
  }

  int height(node *x) {
    return x ? x->h : -1;
  }

  int size(node *x) {
    return x ? x->size : 0;
  }


  ll sum(node *x) {
    return x ? x->sum : 0;
  }

  void fix(node *x) {
    x->h = max(height(x->l), height(x->r)) + 1;
    x->size = x->cnt + size(x->l) + size(x->r);
    x->sum = x->k * x->cnt + sum(x->l) + sum(x->r);
  }

  node *rotL(node *x) {
    node *y = x->r;
    x->r = y->l;
    y->l = x;
    fix(x);
    fix(y);
    return y;
  }

  node *rotR(node *x) {
    node *y = x->l;
    x->l = y->r;
    y->r = x;
    fix(x);
    fix(y);
    return y;
  }

  node *insert(node *x, const T &k) {
    if (!x) {
      node *res = new node();
      res->k = k;
      res->cnt = 1;
      res->size = 1;
      res->sum = k;
      return res;
    }
    if (k == x->k) {
      x->cnt++;
      fix(x);
      return x;
    } else if (k < x->k) {
      x->l = insert(x->l, k);
      fix(x);
      if (height(x->r) + 2 <= height(x->l)) {
        if (height(x->l->r) > height(x->l->l)) {
          x->l = rotL(x->l);
        }
        x = rotR(x);
      }
    } else {
      x->r = insert(x->r, k);
      fix(x);
      if (height(x->l) + 2 <= height(x->r)) {
        if (height(x->r->l) > height(x->r->r)) {
          x->r = rotR(x->r);
        }
        x = rotL(x);
      }
    }
    return x;
  }

  node *erase(node *x, const T &k) {
    if (!x) return x;
    if (k == x->k) {
      x->cnt--;
    } else if (k < x->k) {
      x->l = erase(x->l, k);
    } else {
      x->r = erase(x->r, k);
    }
    fix(x);
    return x;
  }

  bool in(node *x, const T &k) {
    if (!x) return false;
    if (k == x->k) {
      return x->cnt > 0;
    } else if (k < x->k) {
      return in(x->l, k);
    } else {
      return in(x->r, k);
    }
  }

  int countlt(node *x, const T &k) {
    if (!x) return 0;
    if (k == x->k) return size(x->l);
    else if (k < x->k) return countlt(x->l, k);
    else return size(x->l) + x->cnt + countlt(x->r, k);
  }

  int countle(node *x, const T &k) {
    if (!x) return 0;
    if (k == x->k) return x->cnt + size(x->l);
    else if (k < x->k) return countle(x->l, k);
    else return size(x->l) + x->cnt + countle(x->r, k);
  }

  T sumlt(node *x, const T &k) {
    if (!x) return 0;
    if (k == x->k) return sum(x->l);
    else if (k < x->k) return sumlt(x->l, k);
    else return sum(x->l) + x->k * x->cnt + sumlt(x->r, k);
  }

  node *at(node *x, int k) {
    if (!x) return nullptr;
    if (k < size(x->l)) return at(x->l, k);
    if (k < size(x->l) + x->cnt) return x;
    return at(x->r, k - size(x->l) - x->cnt);
  }

public:
  void insert(const T &k) {
    root = insert(root, k);
  }

  void erase(const T &k) {
    root = erase(root, k);
  }

  bool in(const T &k) {
    return in(root, k);
  }

  int size() {
    return size(root);
  }

  int countlt(const T &k) {
    return countlt(root, k);
  }

  T sumlt(const T &k) {
    return sumlt(root, k);
  }

  int countgt(const T &k) {
    return size(root) - countle(root, k);
  }

  int countle(const T &k) {
    return countle(root, k);
  }

  int countge(const T &k) {
    return size(root) - countlt(root, k);
  }

  T at(int k) {
    return at(root, k)->k;
  }
};


template<class T>
struct dummyset {
  vector<ll> a;

  void insert(ll v) {
    a.push_back(v);
  }

  void erase(ll v) {
    auto it = find(range(a), v);
    a.erase(it);
  }

  int countlt(ll v) {
    int res = 0;
    for (ll x : a) {
      res += x < v;
    }
    return res;
  }

  ll sumlt(ll v) {
    ll res = 0;
    for (ll x : a) {
      if (x < v) res += x;
    }
    return res;
  }
};

struct node {
  treemultiset<int> b;
  node *l = nullptr;
  node *r = nullptr;
};

node *insert(node *x, int i, ll v, int h = 39) {
  if (!x) x = new node();
  x->b.insert(i);
  if (h == -1) return x;
  if ((v >> h & 1) == 0) {
    x->l = insert(x->l, i, v, h - 1);
  } else {
    x->r = insert(x->r, i, v, h - 1);
  }
  return x;
}

node *erase(node *x, int i, ll v, int h = 39) {
  x->b.erase(i);
  if (h == -1) return x;
  if ((v >> h & 1) == 0) {
    x->l = erase(x->l, i, v, h - 1);
  } else {
    x->r = erase(x->r, i, v, h - 1);
  }
  return x;
}

ll quantile(node *x, int l, int r, int k, ll a = 0, ll b = 1LL << 40) {
  if (b - a == 1) return a;
  ll m = (a + b) / 2;
  int ll = x->l ? x->l->b.countlt(l) : 0;
  int rr = x->l ? x->l->b.countlt(r) : 0;
  int cnt = rr - ll;
  if (k < cnt) {
    return quantile(x->l, l, r, k, a, m);
  } else {
    k -= cnt;
    return quantile(x->r, l, r, k, m, b);
  }
}

constexpr int U = 1 << 16;
treemultiset<ll> dat[U * 2];

void insert(int k, ll v) {
  k += U;
  while (k != 0) {
    dat[k].insert(v);
    k >>= 1;
  }
}

void erase(int k, ll v) {
  k += U;
  while (k != 0) {
    dat[k].erase(v);
    k >>= 1;
  }
}

int countlt(int a, int b, ll v, int k = 1, int l = 0, int r = U) {
  if (r <= a || b <= l) return 0;
  if (a <= l && r <= b) return dat[k].countlt(v);
  int m = (l + r) / 2;
  int vl = countlt(a, b, v, k * 2 + 0, l, m);
  int vr = countlt(a, b, v, k * 2 + 1, m, r);
  return vl + vr;
}

ll sumlt(int a, int b, ll v, int k = 1, int l = 0, int r = U) {
  if (r <= a || b <= l) return 0;
  if (a <= l && r <= b) return dat[k].sumlt(v);
  int m = (l + r) / 2;
  ll vl = sumlt(a, b, v, k * 2 + 0, l, m);
  ll vr = sumlt(a, b, v, k * 2 + 1, m, r);
  return vl + vr;
}

template<class T>
struct BIT {
  vector<T> dat;

  BIT(int n) : dat(n + 1) {}

  void update(int k, T v) {
    for (int i = k + 1; i < dat.size(); i += i & -i) {
      dat[i] += v;
    }
  }

  T query(int k) {
    T res = 0;
    for (int i = k; i > 0; i -= i & -i) {
      res += dat[i];
    }
    return res;
  }
};

int main() { init_io();
  int N, Q; cin >> N >> Q;
  node *wm = nullptr;
  vector<ll> A(N);
  BIT<ll> bit(N);
  rep(i, N) {
    cin >> A[i];
    wm = insert(wm, i, A[i]);
    bit.update(i, A[i]);
    insert(i, A[i]);
  }
  ll s = 0;
  while (Q--) {
    int type; cin >> type;
    if (type == 1) {
      int x; ll y; cin >> x >> y;
      x ^= s & ((1 << 16) - 1);
      x--;
      y ^= s & ((1LL << 40) - 1);
      erase(x, A[x]);
      bit.update(x, -A[x]);
      wm = erase(wm, x, A[x]);
      A[x] = y;
      insert(x, A[x]);
      bit.update(x, A[x]);
      wm = insert(wm, x, A[x]);
    } else {
      int l, r; cin >> l >> r;
      l ^= s & ((1 << 16) - 1);
      r ^= s & ((1 << 16) - 1);
      if (l > r) swap(l, r);
      l--;
      ll q = quantile(wm, l, r, (r - l) / 2);
      ll c = countlt(l, r, q);
      ll sw = bit.query(r) - bit.query(l);
      ll s0 = sumlt(l, r, q);
      ll s1 = sw - s0;
      ll ans = 0;
      ans += q * c - s0;
      ans += s1 - q * (r - l - c);
      cout << ans << endl;
      s ^= ans;
    }
  }
}
0