1823.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"stdio.h"
#include"memory.h"
const int L=2048*16;
short left[L],right[L],max[L];char stop[L];
#define bigger(a,b) (((a)>(b))?(a):(b))
//inline short bigger(short a,short b)
//{return a>b?a:b;}
short a,b,key;
void insert(short root,short begin,short end)
{
	if(begin>end||b<begin||end<a)return;
	short l1,l2,*l=&left[root],*r=&right[root]; 
	if(a<=begin&&end<=b)
	{
		stop[root]=1;
		if(key==1)
		{
			(*l)=(*r)=max[root]=0;
		}
		
		else 
		{
			(*l)=(*r)=max[root]=end-begin+1;
		}
		return;
	}

	l1=(begin+end)/2-begin+1;
	l2=end-(begin+end)/2;

	short ji=root*2+1,ou=root*2+2;
	if(stop[root])
	{
		stop[root]=0;stop[ji]=1;stop[ou]=1;

		if(max[root]>0)
		{
			left[ji]=right[ji]=max[ji]=l1;
			left[ou]=right[ou]=max[ou]=l2;
		}
		else
		{
			left[ji]=right[ji]=max[ji]=0;
			 left[ou]=right[ou]=max[ou]=0;
		}
	}
	insert(ji,begin,(begin+end)/2);
	insert(ou,(begin+end)/2+1,end);
	if(left[ji]==l1)(*l)=left[ji]+left[ou];
	else (*l)=left[ji];
	if(right[ou]==l2)(*r)=right[ou]+right[ji];
	else (*r)=right[ou];
	max[root]=bigger(bigger(max[ji],max[ou]),left[ou]+right[ji]);

}
int main()
{short n,ppp;
long p;
scanf("%d%d",&n,&p);
memset(stop,0,L*sizeof(char));
stop[0]=1;max[0]=left[0]=right[0]=n;
while(p--)
{scanf("%d",&ppp);
if(ppp==3)printf("%d\n",max[0]);
else {scanf("%d%d",&a,&b);b+=a-1;a--;b--;key=ppp;insert(0,0,n-1);}
}
return 0;
}