Processing math: 100%
My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

RBST Query

コードについての説明(個人的メモ)

RBST とは randomized binary search tree の略で平衡二分木の乱択を用いた実装である.
以下の実装では平衡二分木に遅延処理をのっけたデータ構造になっています. 具体的には範囲への加算 ai←ai+x(i∈[l,r) + 範囲の swap ([ap,aq) と [ar,as) (q−p=s−r) を swap) のようなクエリなどを処理できます.
また擬似乱数の生成に xor shift と呼ばれる手法を用いています(メルセンヌ・ツイスタとかだと遅くなるので).
経験上, Splay Tree の方が速くなることが多い(入力で与えられた数列などから始める場合は bst_build で最初に完全平衡二分探索木を作ってから始めるとかなり速くなる).

時間計算量: insert, erase, get および 各クエリ O(logn) (期待計算量)

コード

  1. // 返り値のノードはその木の新たな root として更新することを忘れない.
  2. template<typename _Tp> class RBSTNode {
  3. public:
  4.     unsigned sz;
  5.     _Tp val, lazy, al;
  6.     RBSTNode* left, *right;
  7.     RBSTNode(){};
  8.     RBSTNode(_Tp v) : sz(1), val(v), lazy(id1), al(val), left(nullptr), right(nullptr){}
  9.     static const _Tp id1 = (_Tp)0;
  10.     static const _Tp id2 = (_Tp)0;
  11.     static void opr1(_Tp& arg1, const _Tp arg2){ arg1 = arg1 + arg2; }
  12.     static _Tp opr2(const _Tp arg1, const _Tp arg2){ return arg1 + arg2; }
  13.     void push(){
  14.         if(lazy == id1) return;
  15.         opr1(val, lazy), al += lazy * sz;
  16.         if(left) opr1(left->lazy, lazy);
  17.         if(right) opr1(right->lazy, lazy);
  18.         lazy = id1;
  19.     }
  20.     void eval(){
  21.         sz = 1, al = val;
  22.         if(left) left->push(), sz += left->sz, al = opr2(left->al, al);
  23.         if(right) right->push(), sz += right->sz, al = opr2(al, right->al);
  24.     }
  25.     static unsigned rnd(){
  26.         static unsigned x = 123456789, y = 362436069, z = 521288629, w = 86675123;
  27.         unsigned t = (x^(x<<11));
  28.         x = y, y = z, z = w;
  29.         return (w = (w^(w>>19))^(t^(t>>8)));
  30.     }
  31. };
  32.  
  33. template<typename _Tp>
  34. inline unsigned size(RBSTNode<_Tp> *t){ return t ? t->sz : 0u; }
  35.  
  36. // r を根とする木内のすべてのキー値が l を根とする木内どのキー値よりも大きいというような場合に, その 2 つの木 merge させる.
  37. template<typename _Tp>
  38. RBSTNode<_Tp> *join(RBSTNode<_Tp> *l, RBSTNode<_Tp> *r){
  39.     if(!l) return r;
  40.     if(!r) return l;
  41.     l->push(), r->push();
  42.     if(RBSTNode<_Tp>::rnd() % (l->sz + r->sz) < l->sz){
  43.         return l->right = join(l->right, r), l->eval(), l;
  44.     }else{
  45.         return r->left = join(l, r->left), r->eval(), r;
  46.     }
  47. }
  48.  
  49. // n 点の木を頂点数 k の木, 頂点数 n-k の木に split する.
  50. template<typename _Tp>
  51. pair<RBSTNode<_Tp>*, RBSTNode<_Tp>*> split(RBSTNode<_Tp> *t, unsigned k){
  52.     if(!t) return make_pair(nullptr, nullptr);
  53.     t->push();
  54.     if(!k) return make_pair(nullptr, t);
  55.     if(k <= size(t->left)){
  56.         pair<RBSTNode<_Tp>*, RBSTNode<_Tp>*> s = split(t->left, k);
  57.         return t->left = s.second, t->eval(), make_pair(s.first, t);
  58.     }else{
  59.         pair<RBSTNode<_Tp>*, RBSTNode<_Tp>*> s = split(t->right, k-size(t->left)-1);
  60.         return t->right = s.first, t->eval(), make_pair(t, s.second);
  61.     }
  62. }
  63.  
  64. // k 番目に頂点 u(を根とする木) を insert する.
  65. template<typename _Tp>
  66. RBSTNode<_Tp>* insert(RBSTNode<_Tp> *root, RBSTNode<_Tp>* u, const unsigned k){
  67.     auto s = split(root, k);
  68.     return join(join(s.first, u), s.second);
  69. }
  70.  
  71. // k 番目の要素を erase する.
  72. template<typename _Tp>
  73. RBSTNode<_Tp>* erase(RBSTNode<_Tp> *root, unsigned k){
  74.     auto sl = split(root, k);
  75.     auto sr = split(sl.second, 1);
  76.     delete sr.first;
  77.     return join(sl.first, sr.second);
  78. }
  79.  
  80. // k 番目の頂点を取得する
  81. template<typename _Tp>
  82. pair<RBSTNode<_Tp>*, _Tp> get(RBSTNode<_Tp> *root, unsigned k){
  83.     auto sr = split(root, k+1);
  84.     auto sl = split(sr.first, k);
  85.     auto lr = sl.second;
  86.     _Tp res = lr->val;
  87.     return make_pair(join(join(sl.first, lr), sr.second), res);
  88. }
  89.  
  90. template<typename _Tp>
  91. RBSTNode<_Tp> *range(RBSTNode<_Tp> *root, const unsigned l, const unsigned r, const _Tp x){
  92.     if(l >= r) return nullptr;
  93.     auto sl = split(root, l);
  94.     auto sr = split(sl.second, r-l);
  95.     RBSTNode<_Tp>::opr1(sr.first->lazy, x);
  96.     return join(join(sl.first, sr.first), sr.second);
  97. }
  98.  
  99. template<typename _Tp>
  100. pair<RBSTNode<_Tp>*, _Tp> query(RBSTNode<_Tp> *root, const unsigned l, const unsigned r){
  101.     if(l >= r) return make_pair(nullptr, (_Tp)RBSTNode<_Tp>::id2);
  102.     auto sl = split(root, l);
  103.     auto sr = split(sl.second, r-l);
  104.     _Tp res = sr.first->al;
  105.     return make_pair(join(join(sl.first, sr.first), sr.second), res);
  106. }
  107.  
  108.  
  109. // ヘルパー関数
  110. template<typename _Tp>
  111. RBSTNode<_Tp> *bst_build(vector<RBSTNode<_Tp>*>& vec){
  112.     RBSTNode<_Tp> *root = vec[0];
  113.     int i, n = (int)vec.size(), st = 2, isolate = ((n % 4 == 1) ? (n-1) : -1);
  114.     while(st <= n){
  115.         root = vec[st-1];
  116.         for(i = st-1; i < n; i += 2*st){
  117.             vec[i]->left = vec[i-st/2];
  118.             if(i+st/2 < n) vec[i]->right = vec[i+st/2];
  119.             else if(isolate >= 0) vec[i]->right = vec[isolate];
  120.             vec[i]->eval();
  121.         }
  122.         isolate = ((n % (4*st) >= st && (n % (4*st) < 2*st)) ? (i-2*st): isolate);
  123.         st <<= 1;
  124.     }
  125.     return root;
  126. }

verify 用の問題

Atcoder : Hash Swapping 提出コード