poj 2892 Tunnel Warfare（线段树）

写这道题其实是想实践一下stack的使用。

思路还需要特别想一下，在这道题里面，对于x，它所连的最长的村子数可以分为两部分来求，从1到x-1这部分右边最长的连续序列，从x到n的左边最长的连续序列。 想明白这一点之后，这道题就变成了一个比较裸的区间合并。不过这还是我第一次求区间的边界值，还真遇到了点儿麻烦。

因为没注意x-1的时候有可能越界，RE了一次。话说这几天好像都很少1A来着。

#include
#include
#include
using namespace std;
#define N 50005
struct node
{
	int x,y;
	int ll,rr;
}a[N*3];
int Min(int x,int y)
{
	if(xmid)
		return findTree(temp+1,x,y);
	else
	{
		int a1,a2;
		a2=findTree(temp,x,mid);
		if(a2==mid-x+1)
		{
			a1=Min(a[temp+1].ll,y-mid);
			return a1+a2;
		}
		else
			return a2;
	}
}
int FindTree(int t,int x,int y)
{
	if(a[t].x==x&&a[t].y==y)
		return a[t].rr;
	int temp=t*2;
	int mid=(a[t].x+a[t].y)/2;
	if(y<=mid)
		return FindTree(temp,x,y);
	else if(x>mid)
		return FindTree(temp+1,x,y);
	else
	{
		int a1,a2;
		a2=FindTree(temp+1,mid+1,y);
		if(a2==y-mid)
		{
			a1=Min(a[temp].rr,mid-x+1);
			return a1+a2;
		}
		else
			return a2;
	}
}
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		CreatTree(1,1,n);
		char s[5];
		int x;
		stackq;
		while(m--)
		{
			scanf("%s",s);
			if(s[0]=='D')
			{
				scanf("%d",&x);
				getchar();
				q.push(x);
				InsertTree(1,x,0);
			}
			else if(s[0]=='R')
			{
				int temp;
				temp=q.top();
				q.pop();
				InsertTree(1,temp,1);
			}
			else
			{
				int a1,a2;
				scanf("%d",&x);
				getchar();
				a1=findTree(1,x,n);//左
				if(a1==0)
				{
					printf("0\n");
					continue;
				}
				if(x>1)
					a2=FindTree(1,1,x-1);//右
				else
					a2=0;
				printf("%d\n",a1+a2);
			}
		}
	}
	return 0;
}