需要写一种数据结构，来维护一些非负整数（ (int) 范围内）的升序序列，其中需要提供以下操作：
其中，初始序列大小为 (n) ，询问/操作总数为 (m) ，并要求 强制在线 。
数据范围 (n \leq 10^5, m \leq 10^6) ， 单点时限 (3s) 。
要求总复杂度为 (O(N \log N)) 级别，可以考虑伸展树（ (Splay) ），对单个节点的查询、修改都维持在 (O(\log N)) 级别。
值得注意的是，这里代码中在数据集内多加入了一大（ (INF) ）一小（ (-1) ）两个虚设端点作为平衡树的上下限（ (front, back) ），这样在实现查找、插入时可以避免越界，并能减少对于某些情况的特殊判断。
#include
#define N 1200005
#define EMPTY 0
#define INF INT_MAX
#define ll long long
using namespace std;
struct Tree{
int data, dataMin, dataMax, size, fa, child[2];
} t[N]; //其中data, fa, child为节点的基本属性
int cnt, root, front, back;
vector dataset, nodeBin;
inline void read(int &s) { //快读，支持int
s = 0;
int tt = 1, k = getchar();
for (; k < '0' || k > '9'; k = getchar()) if (k == '-') tt = -1;//判断该数正负
for (; k >= '0' && k t[root].size+1) return;
if (k == 1) {
int y = mininum(root);
if (y == EMPTY) return;
splay(y);
t[y].child[0] = x;
t[x].fa = y;
updNode(y);
return;
}
int y = findKth(root, k-1);
if (y == EMPTY) return;
splay(y);
t[x].child[1] = t[y].child[1];
if (t[y].child[1] != EMPTY) t[t[y].child[1]].fa = x;
t[y].child[1] = EMPTY;
t[x].child[0] = y;
t[y].fa= x;
root = x;
updNode(y);
updNode(x);
}
void deleteKth(int k) //删除树上序号为k的节点
{
if (!root) {return;}
if (k t[root].size) return;
if (k == 1) {
int y = mininum(root);
if (y == EMPTY) return;
nodeBin.push_back(y);
splay(y);
if (t[y].child[1] != EMPTY) t[t[y].child[1]].fa = EMPTY, root = t[y].child[1];
else root = 0;
return;
}
int y = findKth(root, k);
if (y == EMPTY) return;
splay(y);
nodeBin.push_back(y);
int z = prec(y);
t[z].child[1] = t[y].child[1];
if (t[y].child[1] != EMPTY) t[t[y].child[1]].fa = z;
t[t[y].child[0]].fa = EMPTY;
root = t[y].child[0];
while (z != EMPTY)
{
updNode(z);
z = t[z].fa;
}
}
int buildTree(int L, int R, int fa) //建树，data取用dataset[L]~[R]，L>0
{
if (L > R) return EMPTY;
if (L == R) {
t[L] = (Tree){dataset[L], dataset[L], dataset[L], 1, fa, EMPTY, EMPTY};
return L;
}
int mid = (L+R)/2;
t[mid] = (Tree){dataset[mid], 0, 0, 0, fa, EMPTY, EMPTY};
t[mid].child[0] = buildTree(L, mid-1, mid);
t[mid].child[1] = buildTree(mid+1, R, mid);
updNode(mid);
return mid;
}
inline void clearAll() { //清空全部
cnt = 0;
dataset.clear();
nodeBin.clear();
root = 0;
}
int findDataLeq(int x, int data) //找到x的子树上= checkDataMin(t[x].child[1])) {
a = findDataLeq(t[x].child[1], data);
}
}
if (a != EMPTY) return a;
if (t[x].data = checkDataMin(t[x].child[0])) {
a = findDataLeq(t[x].child[0], data);
}
}
if (a != EMPTY) return a;
return EMPTY;
}
int findDataGeq(int x, int data) //找到x的子树上>=Data的最小序号的节点
{
int a = EMPTY;
if (x == EMPTY) return EMPTY;
if (data > t[x].dataMax) return EMPTY;
if (t[x].child[0] != EMPTY) {
if (data = data) return x;
if (t[x].child[1] != EMPTY) {
if (data x
splay(back);
insertKth(createNode(x), getKth(findDataLeq(back, x))+1); break;
case 2: //删除整数data->x
splay(front);
deleteKth(getKth(findDataGeq(front, x))); break;
case 3: //查询x的排名
splay(back);
last = getKth(findDataLeq(back, x-1));
ans ^= last;
break;
case 4: //查询第x个data
last = t[findKth(root, x+1)].data;
ans ^= last;
break;
case 5: //查询小于x的最大data
splay(front);
last = t[findDataLeq(front, x-1)].data;
ans ^= last;
break;
case 6: //查询大于x的最小data
splay(back);
last = t[findDataGeq(back, x+1)].data;
ans ^= last;
break;
}
}
write(ans);
putchar('\n');
return 0;
}
感谢支持！
Original: https://www.cnblogs.com/jjmg/p/13598480.html
Author: Chiron-zy
Title: 【模板】Splay（伸展树）普通平衡树（数据加强版）/洛谷P6136
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/583722/
转载文章受原作者版权保护。转载请注明原作者出处！