cp-includes/SegtreeSplash.cpp at master · rsalesc/cp-includes · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#ifndef _LIB_SEGTREE_SPLASH
#define _LIB_SEGTREE_SPLASH
#include "SegtreeBeats.cpp"
#include <bits/stdc++.h>

namespace lib {
using namespace std;
namespace seg {
template <typename Node, typename NodeManager = Explicit<Node>>
struct SegtreeSplash : SegtreeBeats<Node, NodeManager, EmptyFolder<void>> {
  typedef SegtreeBeats<Node, NodeManager, EmptyFolder<void>> Base;
  using Base::L;
  using Base::manager;
  using Base::R;
  using Base::SegtreeBeats;
  using Base::split;
  using typename Base::vnode;

  template <typename T, typename Folder>
  T query_element(vnode no, int l, int r, int idx, const Folder &folder) {
    if (!manager.has(no))
      return folder();
    T res = folder(manager.ref(no));
    if (l != r) {
      int mid = split(l, r);
      if (idx <= mid)
        res = folder(res,
                     query_element<T>(manager.left(no), l, mid, idx, folder));
      else
        res = folder(
            res, query_element<T>(manager.right(no), mid + 1, r, idx, folder));
    }
    return res;
  }

  template <typename T, typename Folder>
  inline T query_element(vnode root, int idx, const Folder &folder) {
    return query_element<T>(root, L, R, idx, folder);
  }

  template <typename T, typename Folder>
  inline T query_element(int idx, const Folder &folder) {
    return query_element<T>(this->root(), idx, folder);
  }

  template <typename Updater>
  vnode splash(vnode no, int l, int r, int i, int j, const Updater &updater) {
    no = manager.persist(no);
    if (tag_cond(manager.ref(no), l, r, i, j)) {
      updater(manager.ref(no));
      return no;
    }
    int mid = split(l, r);
    if (j <= mid) {
      manager.ensure_left(no);
      splash(manager.left(no), l, mid, i, j, updater);
    } else if (i > mid) {
      manager.ensure_right(no);
      splash(manager.right(no), mid + 1, r, i, j, updater);
    } else {
      manager.ensure_left(no), manager.ensure_right(no);
      splash(manager.left(no), l, mid, i, j, updater);
      splash(manager.right(no), mid + 1, r, i, j, updater);
    }
    return no;
  }

  template <typename Updater>
  inline vnode splash(vnode root, int i, int j, const Updater &updater) {
    return manager.new_root(splash(root, L, R, i, j, updater));
  }

  template <typename Updater>
  inline vnode splash(int i, int j, const Updater &updater) {
    return splash(this->root(), i, j, updater);
  }
};
} // namespace seg
} // namespace lib

#endif