Tunnel Warfare HDU 1540 区间合并+最大最小值

题意

D x是破坏这个点，Q x是表示查询以x所在的最长的连续的点的个数，R是恢复上一次破坏的点。

题解思路

参考的大佬博客

这里巧妙使用了最大值最小值来进行区间的查找。上一行是大佬的详细题解，真的很妙啊。

代码实现

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<stack>

#define ls (rt<<1)

#define rs (rt<<1|1)

#define mid ((t[rt].l+t[rt].r)>>1)

using namespace std;

const int maxn=5e4+7;

struct node{

	int l, r, maxx, minn; //维护区间内的最大最小值

}t[maxn<<2];

stack<int> des;

int n, m;

void pushup(int rt)

{

	t[rt].maxx=max(t[ls].maxx, t[rs].maxx);

	t[rt].minn=min(t[ls].minn, t[rs].minn);

}

void build(int rt, int l, int r)

{

	t[rt].l=l;

	t[rt].r=r;

	if(l==r)

	{

		t[rt].maxx=0; //最大值默认都是0

		t[rt].minn=n+1; //最小值默认都是n+1

		return ;

	}

	build(ls, l, mid);

	build(rs, mid+1, r);

	//pushup(rt);

	t[rt].maxx=max(t[ls].maxx, t[rs].maxx);

	t[rt].minn=min(t[ls].minn, t[rs].minn);

}

void destory(int rt, int x)

{

	if(t[rt].l==t[rt].r)

	{

		t[rt].maxx=t[rt].l;

		t[rt].minn=t[rt].l;

		return ;

	}

	if(x<=mid) destory(ls, x);

	else destory(rs, x);

	//pushup(rt);

	t[rt].maxx=max(t[ls].maxx, t[rs].maxx);

	t[rt].minn=min(t[ls].minn, t[rs].minn);

}

void rebuild(int rt, int x)

{

	if(t[rt].l==t[rt].r)

	{

		t[rt].maxx=0;

		t[rt].minn=n+1;

		return ;

	}

	if(x<=mid) rebuild(ls, x);

	else rebuild(rs, x);

	//pushup(rt);

	t[rt].maxx=max(t[ls].maxx, t[rs].maxx);

	t[rt].minn=min(t[ls].minn, t[rs].minn);

}

int query_max(int rt, int l, int r)

{

	if(l<=t[rt].l && t[rt].r <= r)

	{

		return t[rt].maxx;

	}

	int ans=0;

	if(l<=mid) ans=max(ans, query_max(ls, l, r));

	if(r>mid) ans=max(ans, query_max(rs, l, r));

	return ans;

}

int query_min(int rt, int l, int r)

{

	if(l<=t[rt].l && t[rt].r <= r)

	{

		return t[rt].minn;

	}

	int ans=0x3f3f3f3f;

	if(l<=mid) ans=min(ans, query_min(ls, l, r));

	if(r>mid) ans=min(ans, query_min(rs, l, r));

	return ans;

}

int main()

{

	char op[3];

	int x;

	while( scanf("%d%d", &n, &m)!=EOF)

	{

		while(!des.empty()) des.pop();

		build(1, 1, n);

		for(int i=1; i<=m; i++)

		{

			scanf("%s", op);

			if(op[0]=='D')

			{

				scanf("%d", &x);

				des.push(x);

				destory(1, x);

			}

			else if(op[0]=='Q')

			{

				scanf("%d", &x);

				int maxx=query_max(1, 1, x);

				int minn=query_min(1, x, n);

				if(maxx==minn)

					printf("0\n");

				else printf("%d\n", minn-maxx-1);

			}

			else {

				x=des.top();

				des.pop();

				rebuild(1, x);

			}

		}

	}

	return 0;

 }

巴特西

Tunnel Warfare HDU 1540 区间合并+最大最小值

Tunnel Warfare HDU 1540 区间合并+最大最小值

题意

题解思路

代码实现

最新文章

热门文章