做题记录 Luogu P1503

本文主要是介绍做题记录 Luogu P1503，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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;
}

这篇关于做题记录 Luogu P1503的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！