保存距离区间左端最近的被destory的村庄和距离区间右端最近的被destory的村庄


#include<iostream>
using namespace std;

#define maxn 50010

int n, m, lst;
int dest[maxn], last[maxn];

struct Node {
	int rt, l, r, lmin, rmax;
}cover[maxn << 2];

void build(int rt, int l, int r)
{
	cover[rt].l = l;
	cover[rt].r = r;
	if (l == r) return;
	int m = (l + r) >> 1;
	build(rt << 1, l, m);
	build(rt << 1 | 1, m + 1, r);
}

void pushup(int rt)
{
	if (cover[rt << 1].lmin && !cover[rt << 1 | 1].lmin)
	{
		cover[rt].lmin = cover[rt << 1].lmin;
		cover[rt].rmax = cover[rt << 1].rmax;
		return;
	}
	if (!cover[rt << 1].lmin && cover[rt << 1 | 1].lmin)
	{
		cover[rt].lmin = cover[rt << 1 | 1].lmin;
		cover[rt].rmax = cover[rt << 1 | 1].rmax;
		return;
	}
	cover[rt].lmin = cover[rt << 1].lmin;
	cover[rt].rmax = cover[rt << 1 | 1].rmax;
}

void update(int rt, int pos, int flag)
{
	if (cover[rt].l == cover[rt].r)
	{
		if (flag == 1)    //flag==1 是Destory
		{
			cover[rt].lmin = cover[rt].l;
			cover[rt].rmax = cover[rt].r;
		}
		else
		{
			cover[rt].lmin = 0;
			cover[rt].rmax = 0;
		}
		return;
	}
	int m = (cover[rt].l + cover[rt].r) >> 1;
	if (pos <= m) update(rt << 1, pos, flag);
	else update(rt << 1 | 1, pos, flag);
	pushup(rt);
}

int query(int rt, int pos, int flag)
{
	if (cover[rt].l == cover[rt].r) return 0;
	int len = 0, m = (cover[rt].l + cover[rt].r) >> 1;
	if (flag != 2)
	{
		if (pos <= m)
		{
			if (cover[rt << 1].lmin > pos || !cover[rt << 1].lmin)
			{
				len += pos - cover[rt << 1].l;
			}
			else
			{
				len += query(rt << 1, pos, 1);
			}
		}
		else
		{
			if (cover[rt << 1 | 1].lmin > pos || !cover[rt << 1 | 1].lmin)
			{
				len += pos - cover[rt << 1 | 1].l;
				if (!cover[rt << 1].rmax) len += cover[rt << 1].r - cover[rt << 1].l + 1;
				else len += cover[rt << 1].r - cover[rt << 1].rmax;
			}
			else
			{
				len += query(rt << 1 | 1, pos, 1);
			}
		}
	}
	if (flag != 1)
	{
		if (pos <= m)
		{
			if (cover[rt << 1].rmax < pos || !cover[rt << 1].rmax)
			{
				len += cover[rt << 1].r - pos;
				if (!cover[rt << 1 | 1].lmin) len += cover[rt << 1 | 1].r - cover[rt << 1 | 1].l + 1;
				else len += cover[rt << 1 | 1].lmin - cover[rt << 1 | 1].l;
			}
			else
			{
				len += query(rt << 1, pos, 2);
			}
		}
		else
		{
			if (cover[rt << 1 | 1].rmax < pos || !cover[rt << 1 | 1].rmax)
			{
				len += cover[rt << 1 | 1].r - pos;
			}
			else
			{
				len += query(rt << 1 | 1, pos, 2);
			}
		}
	}
	return len;
}

int main()
{

	ios::sync_with_stdio(false);

	cin >> n >> m;
	build(1, 1, n);
	int a;
	char c;
	for (int i = 1; i <= m; i++)
	{
		cin >> c;
		if (c == 'D')
		{
			cin >> a;
			dest[a] = 1;
			last[++lst] = a;
			update(1, a, 1);
		}
		else
		{
			if (c == 'Q')
			{
				cin >> a;
				if (!dest[a]) cout << query(1, a, 0) + 1 << endl;
				else cout << 0 << endl;
			}
			else
			{
				dest[last[lst]] = 0;
				update(1, last[lst--], 0);
			}
		}
	}
    return 0;
}