poj 2892 Tunnel Wa易做图re（线段树）

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

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

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

#include<stdio.h>
#include<string.h>
#include<stack>
using namespace std;
#define N 50005
struct node
{
	int x,y;
	int ll,rr;
}a[N*3];
int Min(int x,int y)
{
	if(x<y)
		return x;
	return y;
}
void CreatTree(int t,int x,int y)
{
	a[t].x=x;
	a[t].y=y;
	a[t].ll=y-x+1;
	a[t].rr=y-x+1;
	if(x==y)
		return ;
	int temp=t*2;
	int mid=(x+y)/2;
	CreatTree(temp,x,mid);
	CreatTree(temp+1,mid+1,y);
	return ;
}
void InsertTree(int t,int x,int k)
{
	if(a[t].x==a[t].y)
	{
		a[t].ll=a[t].rr=k;
		return ;
	}
	int temp=t*2;
	int mid=(a[t].x+a[t].y)/2;
	if(x<=mid)
		InsertTree(temp,x,k);
	else
		InsertTree(temp+1,x,k);
	if(a[temp].ll==a[temp].y-a[temp].x+1)
		a[t].ll=a[temp].ll+a[temp+1].ll;
	else
		a[t].ll=a[temp].ll;
	if(a[temp+1].rr==a[temp+1].y-a[temp+1].x+1)
		a[t].rr=a[temp+1].rr+a[temp].rr;
	else
		a[t].rr=a[temp+1].rr;
	return ;
}
int findTree(int t,int x,int y)
{
	if(a[t].x==x&&a[t].y==y)
		return a[t].ll;
	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,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;
		stack<int>q;
		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;
}

补充：软件开发 , C++ ,

上一个：NYOJ 16 矩形嵌套（动态规划）
下一个：hdu3368之DFS