# Poj Solution 1823

```http://poj.org/problem?id=1823

#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("%dn",max[0]);
else {scanf("%d%d",&a,&b);b+=a-1;a--;b--;key=ppp;insert(0,0,n-1);}
}
return 0;
}
```
This entry was posted in poj. Bookmark the permalink.