P1503 鬼子进村 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
栈模拟+平衡树维护前驱后缀。
#include<bits/stdc++.h>
using namespace std;
#define N 100005
stack<int> des;
int n, m, dest[N];
int ch[N][2], size[N], rnd[N], val[N], tot, root;
int newnode(int v)
{
int x = ++tot;
ch[x][0] = ch[x][1] = 0;
val[x] = v;
size[x] = 1;
rnd[x] = rand();
return x;
}
void pushup(int x)
{
size[x] = size[ch[x][0]] + size[ch[x][1]] + 1;
return;
}
void give(int a, int b)
{
ch[a][0] = ch[b][0];
ch[a][1] = ch[b][1];
size[a] = size[b];
rnd[a] = rnd[b];
val[a] = val[b];
return;
}
int merge(int a, int b)
{
if(!a || !b)
{
return a + b;
}
if(rnd[a] < rnd[b])
{
ch[a][1] = merge(ch[a][1], b);
pushup(a);
return a;
}
else
{
ch[b][0] = merge(a, ch[b][0]);
pushup(b);
return b;
}
return 0;
}
void split(int rt, int v, int &x, int &y)
{
if(!rt)
{
x = 0;
y = 0;
return;
}
if(val[rt] <= v)
{
x = rt;
split(ch[rt][1], v, ch[rt][1], y);
pushup(x);
}
else
{
y = rt;
split(ch[rt][0], v, x, ch[rt][0]);
pushup(y);
}
return;
}
void insert(int &rt, int v)
{
int x = 0, y = 0, z = 0;
split(rt, v, x, y);
z = newnode(v);
rt = merge(merge(x, z), y);
return;
}
void del(int &rt, int v)
{
int x = 0, y = 0, z = 0;
split(rt, v, x, z);
split(x, v - 1, x, y);
y = merge(ch[y][0], ch[y][1]);
rt = merge(merge(x, y), z);
return;
}
int kth(int rt, int k)
{
while(rt)
{
if(size[ch[rt][0]] + 1 == k)
{
return val[rt];
}
if(k <= size[ch[rt][0]])
{
rt = ch[rt][0];
}
else
{
k -= size[ch[rt][0]] + 1;
rt = ch[rt][1];
}
}
return 0;
}
int rank(int &rt, int v)
{
int x = 0, y = 0;
split(rt, v - 1, x, y);
int ret = size[x] + 1;
rt = merge(x, y);
return ret;
}
int pre(int &rt, int v)
{
int x = 0, y = 0;
split(rt, v - 1, x, y);
int k = size[x];
int ret = kth(x, k);
rt = merge(x, y);
return ret;
}
int succ(int &rt, int v)
{
int x = 0, y = 0;
split(rt, v, x, y);
int ret = kth(y, 1);
rt = merge(x, y);
return ret;
}
int main()
{
srand(time(0));
scanf("%d%d", &n, &m);
insert(root, 0);
insert(root, n + 1);
char opt[2];
int x;
for(int i = 1; i <= m; i++)
{
scanf("%s", opt);
if(opt[0] == 'D')
{
scanf("%d", &x);
des.push(x);
dest[x] = 1;
insert(root, x);
}
else if(opt[0] == 'R')
{
dest[des.top()] = 0;
del(root, des.top());
des.pop();
}
else if(opt[0] == 'Q')
{
scanf("%d", &x);
if(dest[x])
{
printf("0\n");
}
else
{
printf("%d\n", succ(root, x) - pre(root, x) - 1);
}
}
}
return 0;
}