HDU1540-线段树

题目链接

Tunnel Warfare

题目描述

在抗日战争期间，华北平原广大地区进行了大规模的隧道战。 一般来说，通过隧道连接的村庄排成一列。 除了两端，每个村庄都与两个相邻的村庄直接相连。
入侵者经常对一些村庄发动袭击并摧毁其中的部分隧道。 八路军指挥官要求最新的隧道和村庄连接状态。 如果某些村庄严重隔离，必须立即恢复连接！
输入的第一行包含两个正整数n和m（n，m≤50,000），表示村庄和事件的数量。 接下来的m行中的每一行描述一个事件。
以下所示的不同格式描述了三种不同的事件：
D x：第x个村庄被毁。
Q x：指挥官询问第x个村庄与其直接或间接相关的村庄数量。
R：最后毁坏的村庄被重建了。

思路

用线段树来维护连续区间的模型，把每个村庄看成一个节点，存在的权为1，毁坏的为0；
那么问题就转化成为求当前位置最长连续1的个数。
对每一个区间[l,r]维护从l位置起始的最长连续1的长pre，以及以r为结尾的最长连续1的长suf，以及当前区间最大的连续长度sum。
更新sum[rt]的值时实际上等于左区间的最大值或者右区间的最大值，或者左右区间连接起来，也就是
sum[rt]=max(sum[rt<<1],sum[rt<<1|1],pre[rt<<1]+suf[rt<<1|1]);
更新pre时只需要考虑左区间是否全为1，是的话就把左区间和右区间的pre合并
pre[rt]=pre[rt<<1]+pre[rt<<1|1]
否则直接等于左区间的pre。
更新suf时与更新pre雷同，但是是考虑右区间是否全部为1,如果全部为1就连接起来
suf[rt]=suf[rt<<1]+suf[rt<<1|1];
否则直接等于右区间的suf。
查询的时候，若查询的最长长度在两个节点中间，直接返回suf[rt<<1|1]+pre[rt<<1]
否则继续查找。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 5e4+10;
int a[maxn];
struct node
{
	int pre;
	int suf;
	int sum;
}tree[maxn*4];
void pushup(int rt,int len)
{
	tree[rt].pre=tree[rt<<1].pre;
	tree[rt].suf=tree[rt<<1|1].suf;
	if(tree[rt<<1].pre==(len-(len>>1)))tree[rt].pre=tree[rt<<1|1].pre+tree[rt<<1].pre;//若左区间全为1 
	if(tree[rt<<1|1].suf==(len>>1))tree[rt].suf=tree[rt<<1|1].suf+tree[rt<<1].suf;//若右区间全为1 
	tree[rt].sum=max(tree[1<<1].suf+tree[1<<1|1].pre,max(tree[rt<<1].sum,tree[rt<<1|1].sum));
}
void build(int l,int r,int rt)
{
	if(l==r)
	{
		tree[rt].pre=tree[rt].suf=tree[rt].sum=1;
		return ;
	}
	int mid = (l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	pushup(rt,r-l+1);
}
void Update(int pos,int c,int l,int r,int rt)
{
	if(l==r)
	{
	   tree[rt].pre=tree[rt].suf=tree[rt].sum=c;
	   return ;
	}
	int mid = (l+r)>>1;
	if(pos<=mid)Update(pos,c,l,mid,rt<<1);
	else Update(pos,c,mid+1,r,rt<<1|1);
	pushup(rt,r-l+1);
}
int query(int pos,int l,int r,int rt)
{
	if(l==r)return tree[rt].sum;
	int mid = (l+r)>>1;
	if(pos<=mid)
	{
		if(pos+tree[rt<<1].suf>mid)return tree[rt<<1].suf+tree[rt<<1|1].pre;//最大值为左右区间相连接 
		else return query(pos,l,mid,rt<<1);
	}
	else
	{
		if(mid+tree[rt<<1|1].pre>=pos)return tree[rt<<1|1].pre+tree[rt<<1].suf;
		else return query(pos,mid+1,r,rt<<1|1);
	}
}
int main()
{
	int n,m,x,tot;
	char op[2];
	while(~scanf("%d %d",&n,&m))
	{
		build(1,n,1);
		tot=0;
		while(m--)
		{
			scanf("%s",op);
			if(op[0]=='Q')
			{
				scanf("%d",&x);
				printf("%d\n",query(x,1,n,1));
			}
			else if(op[0]=='D')
			{
				scanf("%d",&x);
				a[++tot]=x;
				Update(x,0,1,n,1);
			}
			else
			{
				x=a[tot--];
				Update(x,1,1,n,1);
			}
		}
	}
}