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

提出ソース

結果

問題	No.925 紲星 Extra
ユーザー	noshi91
提出日時	2019-11-08 22:37:21
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	9,319 ms / 10,000 ms
コード長	5,978 bytes
コンパイル時間	2,250 ms
コンパイル使用メモリ	116,332 KB
実行使用メモリ	263,244 KB
最終ジャッジ日時	2023-10-13 04:17:34
合計ジャッジ時間	85,623 ms
ジャッジサーバーID （参考情報）	judge15 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,368 KB
testcase_01	AC	2 ms 4,372 KB
testcase_02	AC	2 ms 4,372 KB
testcase_03	AC	20 ms 7,944 KB
testcase_04	AC	19 ms 6,536 KB
testcase_05	AC	3,779 ms 243,636 KB
testcase_06	AC	3,802 ms 245,916 KB
testcase_07	AC	3,725 ms 244,444 KB
testcase_08	AC	7,305 ms 170,692 KB
testcase_09	AC	8,910 ms 170,692 KB
testcase_10	AC	3,441 ms 226,608 KB
testcase_11	AC	4,272 ms 256,788 KB
testcase_12	AC	5,846 ms 236,488 KB
testcase_13	AC	4,283 ms 192,332 KB
testcase_14	AC	9,319 ms 170,376 KB
testcase_15	AC	3,549 ms 224,056 KB
testcase_16	AC	5,379 ms 177,064 KB
testcase_17	AC	2,718 ms 172,408 KB
testcase_18	AC	3,529 ms 247,284 KB
testcase_19	AC	2,623 ms 223,392 KB
testcase_20	AC	4,261 ms 263,244 KB
testcase_21	AC	4,227 ms 243,120 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code


/*

限度さん...

*/

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

yukicoder

結果

テストケース

ソースコード