Tunnel Warfare(树状数组+二分)

const int N =5e4+5;
int t;int n, m;int tree[N];
void add(int k, int num) 
{
	for (int i = k;i <= n; i += i & -i)
		tree[i] += num;

}
int read(int k)
{
	int sum = 0;
	for (int i = k;i > 0; i -= i & -i)
		sum += tree[i];
	return sum;
}
bool vis[N];
int main()
{	
	ios::sync_with_stdio(false);cin.tie(0);
	//freopen("in.txt", "r", stdin);
	while (cin >> n >> m)
	{
		memset(tree, 0, sizeof tree);
		f(i, 1, n)add(i, 1);
		string op;int x;
		stack<int> st;
		memset(vis, false, sizeof vis);
		while (m--)
		{
			cin >> op;
			if (op == "D")
			{
				cin >> x;
				if (!vis[x])
				{
					add(x, -1);
					st.push(x);
					vis[x] = true;
				}
			}
			else if (op == "R")
			{
				if (st.empty())continue;
				int now = st.top();st.pop();
				if (vis[now])
				{
					vis[now] = false;
					add(now, 1);
				}
			}
			else
			{
				cin >> x;
				if (vis[x])printf("0\n");
				else
				{
					int le, re;
					int l = 1, r = x;
					while (l <= r)
					{
						int mid = l + r >> 1;
						if (read(x) - read(mid-1) == x - mid+1) { le = mid;r = mid - 1; }
						else l = mid + 1;
					}
					l = x, r = n;
					while (l <= r)
					{
						int mid = l + r >> 1;
						if (read(mid) - read(x - 1) == mid - x + 1) { re = mid;l = mid + 1; }
						else r = mid - 1;
					}
					printf("%d\n", re - le + 1);
				}
			}
		}
	}
	return 0;
}

本文地址：https://blog.csdn.net/qq_43543086/article/details/107120762