欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

Tunnel Warfare(树状数组+二分)

程序员文章站 2022-03-12 09:18:09
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 vi...
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