【模板】普通平衡树（数据加强版）
题目背景
本题是 P3369 数据加强版， ** 扩大数据范围** 并增加了 **强制在线** 。 **题目的输入、输出和原题略有不同**，但需要支持的操作相同。题目描述
您需要写一种数据结构（可参考题目标题），来维护一些整数，其中需要提供以下操作：- 插入一个整数 \(x\)。
- 删除一个整数 \(x\)（若有多个相同的数，只删除一个）。
- 查询整数 \(x\) 的排名（排名定义为比当前数小的数的个数 \(+1\)）。
- 查询排名为 \(x\) 的数（如果不存在，则认为是排名小于 \(x\) 的最大数。保证 \(x\) 不会超过当前数据结构中数的总数）。
- 求 \(x\) 的前驱（前驱定义为小于 \(x\)，且最大的数）。
- 求 \(x\) 的后继（后继定义为大于 \(x\)，且最小的数）。
本题强制在线，保证所有操作合法（操作 \(2\) 保证存在至少一个 \(x\)，操作 \(4,5,6\) 保证存在答案）。
输入输出格式
输入格式
第一行两个正整数 $n,m$，表示**初始数的个数**和操作的个数。第二行 \(n\) 个整数 \(a_1,a_2,a_3,\ldots,a_n\)，表示初始的数。
接下来 \(m\) 行，每行有两个整数 \(\text{opt}\) 和 \(x\)，\(\text{opt}\) 表示操作的序号（$ 1 \leq \text{opt} \leq 6 \(），\)x'$ 表示加密后的操作数。
我们记 \(\text{last}\) 表示上一次 \(3,4,5,6\) 操作的答案，则每次操作的 \(x\) 都要异或上 \(\text{last}\) 才是真实的 \(x\)。初始 \(\text{last}\) 为 \(0\)。
输出格式
输出一行一个整数，表示所有 \(3,4,5,6\) 操作的答案的 异或和。
输入输出样例
输入样例 #1
6 7
1 1 4 5 1 4
2 1
1 9
4 1
5 8
3 13
6 7
1 4
输出样例 #1
6
说明
### 样例解释样例加密前为：
6 7
1 1 4 5 1 4
2 1
1 9
4 1
5 9
3 8
6 1
1 0
限制与约定
对于 \(100\%\) 的数据，\(1\leq n\leq 10^5\)，\(1\leq m\leq 10^6\)，\(0\leq a_i,x\lt 2^{30}\)。
本题输入数据较大，请使用较快的读入方式。
#include <bits/stdc++.h>
using namespace std;
#define getsize(x) (x ? x -> size : 0)
#define ll long long
const int MAXN = 1e6 + 10;
#define USE_FREAD // 使用 fread 读入，去注释符号
#define USE_FWRITE // 使用 fwrite 输出，去注释符号
#ifdef USE_FREAD
namespace iB
{
char buf[1 << 21], *p1 = buf, *p2 = buf;
}
#define getchar() (iB::p1 == iB::p2 && (iB::p2 = (iB::p1 = iB::buf) + fread(iB::buf, 1, 1 << 21, stdin), iB::p1 == iB::p2) ? EOF : *iB::p1++)
#endif
#ifdef USE_FWRITE
namespace oB
{
char buf[1 << 21], *p1 = buf, *p2 = buf + (1 << 21);
}
#define putchar(ch) ((oB::p1 == oB::p2 && fwrite(oB::p1 = oB::buf, 1, 1 << 21, stdout)), *oB::p1++ = ch)
#endif
namespace Fastio
{
struct Reader
{
char endch;
Reader()
{
endch = '\0';
}
Reader& operator >> (char &ch) // ignore character ' ', '\r', '\n', '\t'
{
ch = getchar();
while (ch == ' ' || ch == '\r' || ch == '\n' || ch == '\t') ch = getchar();
return *this;
}
Reader& operator >> (char *str)
{
while (((*str = getchar()) == ' ' || *str == '\n' || *str == '\r' || *str == '\t') && *str != EOF);
while ((*++str = getchar()) != ' ' && *str != '\n' && *str != '\r' && *str != '\t' && *str != EOF);
*str = '\0';
return *this;
}
template <typename Int>
Reader& operator >> (Int &d)
{
bool flag = 0;
endch = getchar();
while ((!isdigit(endch)) && endch != '-' && endch != EOF) endch = getchar();
if (endch == '-') flag = 1, endch = getchar();
d = endch & 15;
while (isdigit(endch = getchar())) d = (d << 3) + (d << 1) + (endch & 15);
if (flag) d = -d;
return *this;
}
template <typename T>
inline T get()
{
T Val;
(*this) >> Val;
return Val;
}
};
struct Writer
{
~Writer()
{
#ifdef USE_FWRITE
fwrite(oB::buf, 1, oB::p1 - oB::buf, stdout);
#endif
}
Writer& operator << (const char ch)
{
putchar(ch);
return *this;
}
Writer& operator << (const char *ch)
{
while (*ch) putchar(*(ch++));
return *this;
}
Writer& operator << (char* ss)
{
return *this << (const char *)ss;
}
template <typename Int>
Writer& operator << (Int x)
{
static char buffer[33];
static int top = 0;
if (!x)
{
putchar('0');
return *this;
}
if (x < 0) putchar('-'), x = -x;
while (x)
{
buffer[++top] = '0' | (x % 10);
x /= 10;
}
while (top) putchar(buffer[top--]);
return *this;
}
};
void flush_output()
{
#ifdef USE_FWRITE
fwrite(oB::buf, 1, oB::p1 - oB::buf, stdout);
oB::p1 = oB::buf;
#else
fflush(stdout);
#endif
}
}
Fastio::Reader kin;
Fastio::Writer kout;
class FHQ
{
public :
class Node
{
public :
ll key, rank;
int size;
Node *ls, *rs;
void push_up()
{
size = getsize(ls) + getsize(rs) + 1;
}
}pool[2 * MAXN], *rt;
int top;
//分裂 p 返回 p 的左子p_l, 右子p_r
void split(Node *p , Node *&p_l, Node *&p_r, int x)//分裂当前子树
{
if(!p)//p 为空，无需分离
{
p_l = p_r = NULL;
return ;
}
if(p -> key <= x)//如果 p 的值比 x 小，就把 p 接到左子上，继续分裂 p 的右子
{
p_l = p;
split(p -> rs, p_l -> rs, p_r, x);
p_l -> push_up();
}
else//否则分 p 的左子
{
p_r = p;
split(p -> ls, p_l ,p_r -> ls, x);
p_r -> push_up();
}
}
void merge(Node *&p, Node *p_l, Node *p_r)
{
if(!p_l || !p_r)
{
p = p_l ? p_l : p_r;
return ;
}
if(p_l -> rank < p_r -> rank)
{
p = p_l;
merge(p -> rs, p_l -> rs, p_r);
}
else
{
p = p_r;
merge(p -> ls, p_l, p_r -> ls);
}
p -> push_up();
}
Node *newNode(int x)
{
Node *p = pool + (++top);
p -> key = x;
p -> rank = rand();
p -> size = 1;
return p;
}
void insert(Node *&rt, int x)
{
Node *p1, *p2;
split(rt, p1, p2 ,x - 1);
merge(rt, p1 ,newNode(x));
merge(rt, rt, p2);
}
void remove(Node *&rt, int x)
{
Node *p1, *p2, *p3 , *p4;
split(rt, p1 ,p2 ,x - 1);
split(p2, p3 ,p4, x);
merge(p3, p3 -> ls, p3 -> rs);
merge(p3, p3, p4);
merge(rt, p1, p3);
}
ll getRank(Node *&rt, int x)
{
Node *p1 ,*p2;
split(rt, p1 ,p2, x - 1);
ll ans = getsize(p1);
merge(rt, p1 ,p2);
return ans;
}
ll getKey(Node *p, ll rank)
{
while(p)
{
if(rank <= getsize(p -> ls))
p = p -> ls;
else if(rank > getsize(p -> ls) + 1)
{
rank -= getsize(p -> ls) + 1;
p = p -> rs;
}
else return p -> key;
}
return 0;
}
ll lower(Node *p, ll x)
{
ll ans = INT_MIN;
while(p)
{
if(x > p -> key)
{
ans = max(ans, p -> key);
p = p -> rs;
}
else p = p -> ls;
}
return ans;
}
ll upper(Node *p, int x)
{
ll ans = INT_MAX;
while(p)
{
if(x < p -> key)
{
ans = min(ans, p -> key);
p = p -> ls;
}
else p = p -> rs;
}
return ans;
}
}FHQ;
int t;
int op;
ll x;
long long ans;
int n;
ll last;
int main()
{
// scanf("%d %d", &n,&t);
kin >> n >> t;
for(int i = 1; i <= n; i++)
{
//scanf("%lld", &x);
kin >> x;
FHQ.insert(FHQ.rt, x);
}
while(t--)
{
//scanf("%d %lld", &op, &x);
kin >> op >> x;
x ^= last;
if(op == 1)
{
FHQ.insert(FHQ.rt, x);
}
if(op == 2)
{
FHQ.remove(FHQ.rt, x);
}
if(op == 3)
{
last = FHQ.getRank(FHQ.rt, x) + 1;
ans ^= last;
}
if(op == 4)
{
last = FHQ.getKey(FHQ.rt, x);
ans ^= last;
}
if(op == 5)
{
last = FHQ.lower(FHQ.rt, x);
ans ^= last;
}
if(op == 6)
{
last = FHQ.upper(FHQ.rt, x);
ans ^= last;
}
// printf("%lld\n", last);
}
kout << ans;
//printf("%lld", ans);
return 0;
}