分块 27 pts 求调

#include<bits/stdc++.h>
using namespace std;

const int N = 5e4 + 5, T = 505;
int n, m;
int a[N];
bool ds[N];
int block, tot;
int l[T], r[T], belong[T], tag[T];
int stk[N], top;

void build()
{
	block = 100;
	tot = n / block;
	if (n % block)
		++tot;
	for (int i = 1; i <= tot; ++i)
	{
		l[i] = (i - 1) * block + 1;
		r[i] = i * block;
	}
	r[tot] = n;
	for (int i = 1; i <= n; ++i)
		belong[i] = (i - 1) / block + 1;
}

int query_L(int p)
{
	for (int i = r[p]; i >= l[p]; --i)
	{
		if (ds[i])
			return r[p] - i;
	}
	return 0;
}

int query_R(int p)
{
	for (int i = l[p]; i <= r[p]; ++i)
	{
		if (ds[i])
			return i - l[p];
	}
	return 0;
}

int query(int x)
{
	if (ds[x])
		return 0;
	int res = 0;
	int L = x, R = x;
	bool flag = 0;
	while (belong[L] == belong[x])
	{
		--L, ++res;
		if (ds[L])
		{
			flag = 1;
			break;
		}
	}
	if (!flag)
	{
		for (int i = belong[x] - 1; i >= 1; --i)
		{
			if (!tag[i])
				res += r[i] - l[i] + 1;
			else
			{
				res += query_L(i);
				break;
			}
		}
	}
	flag = 0;
	while (belong[R] == belong[x])
	{
		++R, ++res;
		if (ds[R])
		{
			flag = 1;
			break;
		}
	}
	if (!flag)
	{
		for (int i = belong[x] + 1; i <= tot; ++i)
		{
			if (!tag[i])
				res += r[i] - l[i] + 1;
			else
			{
				res += query_R(i);
				break;
			}
		}
	}
	return res;
}

int main()
{
	scanf("%d%d", &n, &m);
	build();
	while (m--)
	{
		char op[5];
		int x;
		scanf(" %s", op);
		if (*op == 'D')
		{
			scanf("%d", &x);
			stk[++top] = x, ds[x] = 1;
			++tag[belong[x]];
		}
		else if (*op == 'R')
		{
			if (top != 0)
			{
				ds[stk[top]] = 0;
				--tag[belong[stk[top--]]];
			}
		}
		else
		{
			scanf("%d", &x);
			printf("%d\n", query(x));
		}
	}
	return 0;
}