Segment Treap，一个由烂炖而生的 Treap

tiger2005 · 2022-08-31 19:04:39 · 个人记录

这个算法时间复杂度并未经过证明。

Segment Treap，顾名思义，就是将线段树思想和 Treap 结合在一起的一个乱炖数据结构。

具体而言，Segment Treap 将非常多的操作直接变成了树上的寻找点操作，但是我们考虑将过程中遇到的所有点的中序遍历记录下来（包括路径和路径上的所有左右儿子）。此时中序序列应当为 路径 和 路径上点的非路径儿子 交替出现的序列。

随后我们隔一个选一个，将 路径上点的非路径儿子 选出来，根据其最长祖先-儿子链长度为依据，在单调栈上进行贪心。

单调栈维护最长链递减序列，按顺序加入每个 路径上点的非路径儿子。加入后，如果违反单调栈规定，那么将单调栈末尾的一部分取出并合并，保证最后合并的树最长链不超过待插入树最长链长度加一。然后直接对单调栈的单调性进行维护，疯狂弹出并合并直到满足为止即可。

目前的代码版本为直接构造完全二叉树。第一个猜想的代码在注释中有。

对于每一个操作的处理如下：

• Add：寻找到当前数字，找不到则直接添加一个点。记录下中序遍历序列并重构树。
• Delete：寻找到当前数字，将其左右子树的中序序列分别记录。
  • 如果当前数字没有出现，那么直接重构即可。
  • 如果当前数字出现至少一次，减掉 1 之后将左右子树合并即可。
  • 如果当前数字只出现一次，那么查询左子树中最大值，此时左子树记录的中序遍历序列最后一项必然等于 0，将其去除后添加入右子树（或者未重构的中序遍历序列），然后重构即可。这一步待优化。
• Rank / Number / Previos / Next：照抄 FHQ Treap 方法，前两个操作需要记录下中序遍历序列并重构。

整个重构的复杂度为 O(len)，但是由于重构后期望高度未知，而且代码又臭又长（虽然一堆可以复制粘贴的），所以不建议大家受这个罪。

以下为代码实现，在 【模板】普通平衡树 中跑出了 210ms 的成绩，被 FHQ Treap 吊着打。

提交记录

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

int N, opt, x;

namespace Segment_Treap {
  const int MAXN = 1e5 + 10;
  int ch[MAXN][2], sm[MAXN], val[MAXN], lnk[MAXN], siz[MAXN];
  int cnt = 0;
  int root = 0;

  vector<int> stk;
  vector<pair<int, int> > pStk;

  inline int newNode (int v) {
    int ret = ++ cnt;
    val[ret] = v;
    sm[ret] = lnk[ret] = siz[ret] = 1;
    return ret;
  }

  inline void push_up (int x) {
    siz[x] = sm[x] + siz[ch[x][0]] + siz[ch[x][1]];
  }

  inline void merge (int x, int y, int f) {
    ch[f][0] = x;
    ch[f][1] = y;
    lnk[f] = max(lnk[x], lnk[y]) + 1;
    push_up(f);
  }

  inline void rebuild () {
    // int siz = stk.size(); stk.push_back(0);
    // for (int i = 0; i <= siz; i += 2) {
    //   pair<int, int> hold = make_pair(stk[i], stk[i + 1]);
    //   if (!pStk.empty() && (lnk[pStk.back().first]) <= lnk[stk[i]]) {
    //     pair<int, int> hold2 = pStk.back(); pStk.pop_back();
    //     while (!pStk.empty() && (lnk[pStk.back().first]) <= lnk[stk[i]]) {
    //       merge (pStk.back().first, hold2.first, pStk.back().second);
    //       hold2.first = pStk.back().second;
    //       pStk.pop_back();
    //     }
    //     merge (hold2.first, hold.first, hold2.second);
    //     hold.first = hold2.second;
    //   }
    //   while (!pStk.empty() && (lnk[pStk.back().first]) <= lnk[hold.first]) {
    //     merge (pStk.back().first, hold.first, pStk.back().second);
    //     hold.first = pStk.back().second;
    //     pStk.pop_back();
    //   }
    //   pStk.push_back(hold);
    // }
    // pair<int, int> hold = pStk.back(); pStk.pop_back();
    // while (!pStk.empty()) {
    //   merge (pStk.back().first, hold.first, pStk.back().second);
    //   hold.first = pStk.back().second;
    //   pStk.pop_back();
    // }
    // root = hold.first;
    // stk.clear();
    int siz = stk.size();
    // fprintf(stderr, "* %d\n", siz);
    int u = siz - 1;
    for (int i = 2; i <= siz; i <<= 1)
      for (int j = i - 1; j < siz; j += (i << 1)) {
        // fprintf(stderr, "> %d %d %d\n", j - (i >> 1), j + (i >> 1), j);
        if (j == siz - 1) 
          merge(stk[j - (i >> 1)], 0, stk[j]);
        else {
          merge(stk[j - (i >> 1)], stk[min(u, j + (i >> 1))], stk[j]);
          if (j + (i >> 1) >= u)
            u = j;
        }
      }
    root = stk[(1 << __lg(siz)) - 1];
    stk.clear();
  }

  void add (int x, int r = root) {
    if (r == 0) {
      stk.push_back(newNode(x));
      return;
    }
    if (val[r] == x) {
      ++ sm[r]; ++ siz[r];
      stk.push_back(r);
      return;
    }
    else if (val[r] < x) {
      stk.push_back(ch[r][0]);
      stk.push_back(r);
      add (x, ch[r][1]);
    }
    else {
      add (x, ch[r][0]);
      stk.push_back(r);
      stk.push_back(ch[r][1]);
    }
  }

  void right_abst (int r) {
    if (r == 0)
      return;
    stk.push_back(ch[r][0]);
    stk.push_back(r);
    right_abst(ch[r][1]);
  }

  void del (int x, int r = root) {
    if (!r) {
      stk.push_back(0);
      return;
    }
    if (val[r] == x) {
      if (-- sm[r] == 0) {
        right_abst(ch[r][0]);
        stk.push_back(ch[r][1]);
      }
      else {
        -- siz[r];
        stk.push_back(r);
      }
    }
    else if (val[r] < x) {
      stk.push_back(ch[r][0]);
      stk.push_back(r);
      del (x, ch[r][1]);
    }
    else {
      del (x, ch[r][0]);
      stk.push_back(r);
      stk.push_back(ch[r][1]);
    }
  }

  int rk (int x, int r = root) {
    if (!r) {
      stk.push_back(0);
      return 0;
    }
    if (val[r] == x) {
      stk.push_back(r);
      return siz[ch[r][0]] + 1;
    }
    if (val[r] > x) {
      int ret = rk (x, ch[r][0]);
      stk.push_back(r);
      stk.push_back(ch[r][1]);
      return ret;
    }
    stk.push_back(ch[r][0]);
    stk.push_back(r);
    return siz[ch[r][0]] + sm[r] + rk(x, ch[r][1]);
  }

  int num (int x, int r = root) {
    if (!r) {
      stk.push_back(0);
      return 0;
    }
    if (siz[ch[r][0]] >= x) {
      int ret = num (x, ch[r][0]);
      stk.push_back(r);
      stk.push_back(ch[r][1]);
      return ret;
    }
    if (siz[ch[r][0]] + sm[r] >= x) {
      stk.push_back(r);
      return val[r];
    }
    stk.push_back(ch[r][0]);
    stk.push_back(r);
    return num(x - siz[ch[r][0]] - sm[r], ch[r][1]);
  }

  inline int pre (int x) {
    int n = root;
    int ans = -1e9;
    while (n) {
      if (val[n] > ans && val[n] < x)
        ans = val[n];
      n = ch[n][val[n] < x];
    }
    return ans;
  }

  inline int nxt (int x) {
    int n = root;
    int ans = 1e9;
    while (n) {
      if (val[n] < ans && val[n] > x)
        ans = val[n];
      n = ch[n][val[n] <= x];
    }
    return ans;
  }

  void print (int x, int dep) {
    if (!x)
      return;
    print(ch[x][0], dep + 1);
    for (int i = 0; i < dep; i ++)
      printf("  ");
    printf("* %d %d %d %d %d\n", x, val[x], sm[x], siz[x], lnk[x]);
    print(ch[x][1], dep + 1);
  }

}

using namespace Segment_Treap;

int main() {
  scanf("%d", &N);
  while (N --) {
    scanf("%d%d", &opt, &x);
    if (opt == 1) {
      add(x); rebuild();
    }
    else if (opt == 2) {
      del(x); rebuild();
    }
    else if (opt == 3) {
      printf("%d\n", rk(x));
      rebuild();
    }
    else if (opt == 4) {
      printf("%d\n", num(x));
      rebuild();
    }
    else if (opt == 5) {
      printf("%d\n", pre(x));
    }
    else {
      printf("%d\n", nxt(x));
    }
    // print(root, 0);
    // printf("\n");
  }
}

以下代码在 【模板】普通平衡树（数据加强版） 中跑出了 14.45s 的成绩，被分块吊着打。

提交记录

/*******************************
| Author:  tiger2005
| Problem: P6136 【模板】普通平衡树（数据加强版）
| Contest: Luogu
| URL:     https://www.luogu.com.cn/problem/P6136
| When:    2022-09-06 01:25:40
| 
| Memory:  89 MB
| Time:    3000 ms
*******************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <string>
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

namespace Segment_Treap {
  const int MAXN = 1100000 + 10;
  int ch[MAXN][2], sm[MAXN], val[MAXN], lnk[MAXN], siz[MAXN];
  int cnt = 0;
  int root = 0;

  vector<int> stk;
  vector<pair<int, int> > pStk;

  inline int newNode (int v) {
    int ret = ++ cnt;
    val[ret] = v;
    sm[ret] = lnk[ret] = siz[ret] = 1;
    return ret;
  }

  inline void push_up (int x) {
    siz[x] = sm[x] + siz[ch[x][0]] + siz[ch[x][1]];
  }

  inline void merge (int x, int y, int f) {
    ch[f][0] = x;
    ch[f][1] = y;
    lnk[f] = max(lnk[x], lnk[y]) + 1;
    push_up(f);
  }

  inline void rebuild () {
    int siz = stk.size(); stk.push_back(0);
    for (int i = 0; i <= siz; i += 2) {
      pair<int, int> hold = make_pair(stk[i], stk[i + 1]);
      if (!pStk.empty() && (lnk[pStk.back().first]) <= lnk[stk[i]]) {
        pair<int, int> hold2 = pStk.back(); pStk.pop_back();
        while (!pStk.empty() && (lnk[pStk.back().first]) <= lnk[stk[i]]) {
          merge (pStk.back().first, hold2.first, pStk.back().second);
          hold2.first = pStk.back().second;
          pStk.pop_back();
        }
        merge (hold2.first, hold.first, hold2.second);
        hold.first = hold2.second;
      }
      while (!pStk.empty() && (lnk[pStk.back().first]) <= lnk[hold.first]) {
        merge (pStk.back().first, hold.first, pStk.back().second);
        hold.first = pStk.back().second;
        pStk.pop_back();
      }
      pStk.push_back(hold);
    }
    pair<int, int> hold = pStk.back(); pStk.pop_back();
    while (!pStk.empty()) {
      merge (pStk.back().first, hold.first, pStk.back().second);
      hold.first = pStk.back().second;
      pStk.pop_back();
    }
    root = hold.first;
    stk.clear();
  }

  void add (int x, int r = root) {
    if (r == 0) {
      stk.push_back(newNode(x));
      return;
    }
    if (val[r] == x) {
      ++ sm[r]; ++ siz[r];
      stk.push_back(r);
      return;
    }
    else if (val[r] < x) {
      stk.push_back(ch[r][0]);
      stk.push_back(r);
      add (x, ch[r][1]);
    }
    else {
      add (x, ch[r][0]);
      stk.push_back(r);
      stk.push_back(ch[r][1]);
    }
  }

  void right_abst (int r) {
    if (r == 0)
      return;
    stk.push_back(ch[r][0]);
    stk.push_back(r);
    right_abst(ch[r][1]);
  }

  void del (int x, int r = root) {
    if (!r) {
      stk.push_back(0);
      return;
    }
    if (val[r] == x) {
      if (-- sm[r] == 0) {
        right_abst(ch[r][0]);
        stk.push_back(ch[r][1]);
      }
      else {
        -- siz[r];
        stk.push_back(r);
      }
    }
    else if (val[r] < x) {
      stk.push_back(ch[r][0]);
      stk.push_back(r);
      del (x, ch[r][1]);
    }
    else {
      del (x, ch[r][0]);
      stk.push_back(r);
      stk.push_back(ch[r][1]);
    }
  }

  int rk (int x, int r = root) {
    if (!r) {
      stk.push_back(0);
      return 0;
    }
    if (val[r] == x) {
      stk.push_back(r);
      return siz[ch[r][0]];
    }
    if (val[r] > x) {
      int ret = rk (x, ch[r][0]);
      stk.push_back(r);
      stk.push_back(ch[r][1]);
      return ret;
    }
    stk.push_back(ch[r][0]);
    stk.push_back(r);
    return siz[ch[r][0]] + sm[r] + rk(x, ch[r][1]);
  }

  int num (int x, int r = root) {
    if (!r) {
      stk.push_back(0);
      return 0;
    }
    if (siz[ch[r][0]] >= x) {
      int ret = num (x, ch[r][0]);
      stk.push_back(r);
      stk.push_back(ch[r][1]);
      return ret;
    }
    if (siz[ch[r][0]] + sm[r] >= x) {
      stk.push_back(r);
      return val[r];
    }
    stk.push_back(ch[r][0]);
    stk.push_back(r);
    return num(x - siz[ch[r][0]] - sm[r], ch[r][1]);
  }

  inline int pre (int x) {
    int n = root;
    int ans = INT_MIN;
    while (n) {
      if (val[n] > ans && val[n] < x)
        ans = val[n];
      n = ch[n][val[n] < x];
    }
    return ans;
  }

  inline int nxt (int x) {
    int n = root;
    int ans = INT_MAX;
    while (n) {
      if (val[n] < ans && val[n] > x)
        ans = val[n];
      n = ch[n][val[n] <= x];
    }
    return ans;
  }

  void print (int x, int dep) {
    if (!x)
      return;
    print(ch[x][0], dep + 1);
    for (int i = 0; i < dep; i ++)
      printf("  ");
    printf("* %d %d %d %d %d\n", x, val[x], sm[x], siz[x], lnk[x]);
    print(ch[x][1], dep + 1);
  }

}

using namespace Segment_Treap;

int N, opt, x, M;

int main() {
    scanf("%d%d", &N, &M);
    while (N --) {
        scanf("%d", &x);
        add(x); rebuild();
    }
    int lans = 0, aans = 0;
  while (M --) {
    scanf("%d%d", &opt, &x);
    x ^= lans;
    if (opt == 1) {
      add(x); rebuild();
    }
    else if (opt == 2) {
      del(x); rebuild();
    }
    else if (opt == 3) {
      aans ^= (lans = rk(x) + 1);
      rebuild();
    }
    else if (opt == 4) {
      aans ^= (lans = num(x));
      rebuild();
    }
    else if (opt == 5) {
      aans ^= (lans = pre(x));
    }
    else {
      aans ^= (lans = nxt(x));
    }
    // print(root, 0);
    // printf("\n");
  }
  printf("%d", aans);
}