結果

問題 No.925 紲星 Extra
ユーザー noshi91noshi91
提出日時 2019-11-08 22:37:21
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 8,696 ms / 10,000 ms
コード長 5,978 bytes
コンパイル時間 2,021 ms
コンパイル使用メモリ 116,532 KB
実行使用メモリ 263,296 KB
最終ジャッジ日時 2024-09-15 01:51:59
合計ジャッジ時間 82,441 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 


/*

限度さん...

*/

#include <cstddef>
#include <cstdint>
#include <memory>
#include <utility>

using usize = std::size_t;
using u64 = std::uint_fast64_t;

class treap {
public:
  using size_type = std::size_t;

private:
  static u64 xorshift() {
    static u64 seed = 91;
    seed ^= seed << 7;
    seed ^= seed >> 9;
    return seed;
  }

  class node_type;
  using pointer = std::unique_ptr<node_type>;
  class node_type {
    friend treap;

    pointer left;
    pointer right;
    size_type size;
    u64 priority;
    usize key;
    u64 val;
    u64 sum;

  public:
    node_type(const usize key, const u64 val)
        : left(), right(), size(1), priority(xorshift()), key(key), val(val),
          sum(val) {}
  };

  static size_type size(const pointer &ptr) { return ptr ? ptr->size : 0; }

  static u64 sum(const pointer &ptr) { return ptr ? ptr->sum : 0; }

  static u64 priority(const pointer &ptr) { return ptr ? ptr->priority : 0; }

  static void fix(const pointer &ptr) {
    ptr->size = size(ptr->left) + 1 + size(ptr->right);
    ptr->sum = sum(ptr->left) + ptr->val + sum(ptr->right);
  }

  static void rotate_left(pointer &ptr) {
    pointer right = std::move(ptr->right);
    ptr->right = std::move(right->left);
    fix(ptr);
    right->left = std::move(ptr);
    fix(right);
    ptr = std::move(right);
  }

  static void rotate_right(pointer &ptr) {
    pointer left = std::move(ptr->left);
    ptr->left = std::move(left->right);
    fix(ptr);
    left->right = std::move(ptr);
    fix(left);
    ptr = std::move(left);
  }

  static void insert(pointer &ptr, const usize key, const u64 val) {
    if (!ptr) {
      ptr = std::make_unique<node_type>(key, val);
      return;
    }
    if (key == ptr->key) {
      return;
    }
    if (key < ptr->key) {
      insert(ptr->left, key, val);
      fix(ptr);
      if (ptr->left->priority > ptr->priority) {
        rotate_right(ptr);
      }
    } else {
      insert(ptr->right, key, val);
      fix(ptr);
      if (ptr->right->priority > ptr->priority) {
        rotate_left(ptr);
      }
    }
  }

  static void erase(pointer &ptr, const usize key) {
    if (!ptr) {
      return;
    }
    if (key == ptr->key) {
      if (!ptr->left && !ptr->right) {
        ptr.reset();
        return;
      }
      if (priority(ptr->left) > priority(ptr->right)) {
        rotate_right(ptr);
      } else {
        rotate_left(ptr);
      }
    }
    if (key < ptr->key) {
      erase(ptr->left, key);
      fix(ptr);
    } else {
      erase(ptr->right, key);
      fix(ptr);
    }
  }

  static usize count(const pointer &ptr, const size_type key) {
    if (!ptr) {
      return 0;
    }
    if (key <= ptr->key) {
      return count(ptr->left, key);
    } else {
      return size(ptr->left) + 1 + count(ptr->right, key);
    }
  }

  static u64 fold(const pointer &ptr, const usize key) {
    if (!ptr) {
      return 0;
    }
    if (key <= ptr->key) {
      return fold(ptr->left, key);
    } else {
      return sum(ptr->left) + ptr->val + fold(ptr->right, key);
    }
  }

  pointer root;

public:
  treap() : root() {}

  void insert_(const usize key, const u64 val) { insert(root, key, val); }

  void erase_(const usize key) { erase(root, key); }

  usize count_(const usize l, const usize r) {
    return count(root, r) - count(root, l);
  }

  u64 fold_(const usize l, const usize r) {
    return fold(root, r) - fold(root, l);
  }
};

struct kizuna {
  struct base;
  using base_ptr = std::unique_ptr<base>;

  struct base {
    base_ptr left, right;
    treap tree;
  };

  base_ptr root;

  void erase(u64 pos, usize pos2) {
    base *ptr = root.get();
    usize p = 40;
    while (p != 0) {
      p -= 1;
      ptr->tree.erase_(pos2);
      if (pos >> p & 1) {
        ptr = ptr->right.get();
      } else {
        ptr = ptr->left.get();
      }
    }
    ptr->tree.erase_(pos2);
  }
  void insert(u64 pos, usize pos2) {
    if (!root) {
      root = std::make_unique<base>();
    }
    base *ptr = root.get();
    ptr->tree.insert_(pos2, pos);
    usize p = 40;
    while (p != 0) {
      p -= 1;
      if (pos >> p & 1) {
        if (!ptr->right) {
          ptr->right = std::make_unique<base>();
        }
        ptr = ptr->right.get();
      } else {
        if (!ptr->left) {
          ptr->left = std::make_unique<base>();
        }
        ptr = ptr->left.get();
      }
      ptr->tree.insert_(pos2, pos);
    }
  }
  u64 score(const usize l, const usize r) {
    const usize mid_c = (r - l) / 2;
    usize mid = mid_c;
    u64 less = 0, greater = 0;
    u64 sep = 0;
    base *ptr = root.get();
    usize p = 40;
    while (p != 0) {
      p -= 1;
      const usize count = ptr->left ? ptr->left->tree.count_(l, r) : 0;
      if (mid >= count) {
        mid -= count;
        less += ptr->left ? ptr->left->tree.fold_(l, r) : 0;
        ptr = ptr->right.get();
        sep |= u64(1) << p;
      } else {
        greater += ptr->right ? ptr->right->tree.fold_(l, r) : 0;
        ptr = ptr->left.get();
      }
    }
    const usize lc = mid_c - mid;
    const usize gc = r - l - lc - ptr->tree.count_(l, r);
    return sep * lc - less + greater - sep * gc;
  }
};

#include <iostream>
#include <vector>

int main() {
  int n, q;
  std::cin >> n >> q;
  kizuna kiz;
  std::vector<u64> a(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> a[i];
    kiz.insert(a[i], i);
  }
  u64 acc = 0;
  for (int i = 0; i < q; ++i) {
    int t;
    std::cin >> t;
    if (t == 1) {
      u64 x, y;
      std::cin >> x >> y;
      x = x ^ acc % (u64(1) << 16);
      y = y ^ acc % (u64(1) << 40);
      x -= 1;
      kiz.erase(a[x], x);
      a[x] = y;
      kiz.insert(a[x], x);
    } else {
      u64 l, r;
      std::cin >> l >> r;
      l = l ^ acc % (u64(1) << 16);
      r = r ^ acc % (u64(1) << 16);
      if (l > r) {
        std::swap(l, r);
      }
      l -= 1;
      const u64 ans = kiz.score(l, r);
      std::cout << ans << std::endl;
      acc ^= ans;
    }
  }
  return 0;
}
0