/tmp/solutions/build/range_reverse_range_sum-slow.cpp:
    1|       |#include <common.h>
    2|       |prelude;
    3|       |
    4|       |namespace {
    5|       |
    6|       |constexpr int N = 200001;
    7|       |
    8|       |struct Node {
    9|       |  int pri;
   10|       |  int val;
   11|       |  u64 sum;
   12|       |  int rev;
   13|       |  int size;
   14|       |  int l, r;
   15|       |} node[N];
   16|       |
   17|   168M|def maintain(int x) -> void {
   18|   168M|  node[x].size = node[node[x].l].size + 1 + node[node[x].r].size;
   19|   168M|  node[x].sum = node[node[x].l].sum + node[x].val + node[node[x].r].sum;
   20|   168M|}
   21|       |
   22|   169M|def pushdown(int x) -> void {
   23|   169M|  if (node[x].rev) {
  ------------------
  |  Branch (23:7): [True: 25.07%, False: 74.93%]
  ------------------
   24|  42.5M|    std::swap(node[x].l, node[x].r);
   25|  42.5M|    node[node[x].l].rev ^= 1;
   26|  42.5M|    node[node[x].r].rev ^= 1;
   27|  42.5M|    node[x].rev = 0;
   28|  42.5M|  }
   29|   169M|}
   30|       |
   31|  1.13M|def reverse(int x) -> void {
   32|  1.13M|  if (x == 0) return;
                            ^115k
  ------------------
  |  Branch (32:7): [True: 10.25%, False: 89.75%]
  ------------------
   33|  1.01M|  node[x].rev ^= 1;
   34|  1.01M|  pushdown(x);
   35|  1.01M|}
   36|       |
   37|  96.1M|def merge(int x, int y) -> int {
   38|  96.1M|  if (x == 0) return y;
                            ^3.31M
  ------------------
  |  Branch (38:7): [True: 3.45%, False: 96.55%]
  ------------------
   39|  92.8M|  if (y == 0) return x;
                            ^2.92M
  ------------------
  |  Branch (39:7): [True: 3.15%, False: 96.85%]
  ------------------
   40|  89.9M|  if (node[x].pri > node[y].pri) {
  ------------------
  |  Branch (40:7): [True: 58.59%, False: 41.41%]
  ------------------
   41|  52.6M|    pushdown(x);
   42|  52.6M|    node[x].r = merge(node[x].r, y);
   43|  52.6M|    maintain(x);
   44|  52.6M|    return x;
   45|  52.6M|  } else {
   46|  37.2M|    pushdown(y);
   47|  37.2M|    node[y].l = merge(x, node[y].l);
   48|  37.2M|    maintain(y);
   49|  37.2M|    return y;
   50|  37.2M|  }
   51|  89.9M|}
   52|       |
   53|  83.4M|def split(int x, int k) -> std::pair<int, int> {
   54|  83.4M|  if (x == 0) return {0, 0};
                            ^4.52M
  ------------------
  |  Branch (54:7): [True: 5.42%, False: 94.58%]
  ------------------
   55|  78.9M|  pushdown(x);
   56|  78.9M|  if (int size = node[node[x].l].size; k <= size) {
  ------------------
  |  Branch (56:40): [True: 51.27%, False: 48.73%]
  ------------------
   57|  40.4M|    let[a, b] = split(node[x].l, k);
   58|  40.4M|    node[x].l = b;
   59|  40.4M|    maintain(x);
   60|  40.4M|    return {a, x};
   61|  40.4M|  } else {
   62|  38.4M|    let[a, b] = split(node[x].r, k - size - 1);
   63|  38.4M|    node[x].r = a;
   64|  38.4M|    maintain(x);
   65|  38.4M|    return {x, b};
   66|  38.4M|  }
   67|  78.9M|}
   68|       |
   69|       |} // namespace
   70|       |
   71|     20|int main() {
   72|     20|  rd rd;
   73|     20|  wt wt;
   74|     20|  int n = rd.uh();
   75|     20|  int q = rd.uh();
   76|     20|#ifdef LOCAL
   77|     20|  std::memset(node, 0, sizeof(Node) * (n + 1));
   78|     20|#endif
   79|     20|  int x = 0;
   80|  1.71M|  for (int i = 1; i <= n; ++i) {
                                        ^1.71M
  ------------------
  |  Branch (80:19): [True: 100.00%, False: 0.00%]
  ------------------
   81|  1.71M|    node[i].size = 1;
   82|  1.71M|    node[i].pri = node[i].sum = node[i].val = rd.uw();
   83|  1.71M|    x = merge(x, i);
   84|  1.71M|  }
   85|     20|  if (n == 0) rd.skip(1);
                            ^3
  ------------------
  |  Branch (85:7): [True: 15.00%, False: 85.00%]
  ------------------
   86|  2.26M|  while (q--) {
  ------------------
  |  Branch (86:10): [True: 100.00%, False: 0.00%]
  ------------------
   87|  2.26M|    int t = rd.u1();
   88|  2.26M|    int l = rd.uh();
   89|  2.26M|    int r = rd.uh();
   90|  2.26M|    let[a, b] = split(x, l);
   91|  2.26M|    let[c, d] = split(b, r - l);
   92|  2.26M|    if (t == 0) {
  ------------------
  |  Branch (92:9): [True: 49.99%, False: 50.01%]
  ------------------
   93|  1.13M|      reverse(c);
   94|  1.13M|    }
   95|  2.26M|    if (t == 1) {
  ------------------
  |  Branch (95:9): [True: 50.01%, False: 49.99%]
  ------------------
   96|  1.13M|      wt.ud(node[c].sum);
   97|  1.13M|    }
   98|  2.26M|    x = merge(a, merge(c, d));
   99|  2.26M|  }
  100|     20|  return 0;
  101|     20|}