poj 2892 Tunnel Warfare（線段樹）

寫這道題其實是想實踐一下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;
}