[cpp]
這題就491個accepted，還挺嚇人的，別被嚇住哈，其實我被嚇住了，嘻嘻，這泥瑪做也是悲劇，但看分類上說屬於中等題，我就猛憋一股氣，三A ，呵呵
這個題我們這需要在線段上用ml，mr，len表示左面有幾個連續空位，右面有幾個連續空位，中間有幾個連續空位
在和並的時候注意更新規則
[cpp]
a[i].len=max(a[i*2].mr+a[i*2+1].ml,max(a[i*2].len,a[i*2+1].len));//這個好想 更新中間len的值
if(a[i*2+1].ml==(a[i*2+1].r-a[i*2+1].l+1))//如果右面孩子的ml=線段長度，也就是說右面孩子是全空的，那a[i].ml就是a[i*2].mr+右邊整個長度
a[i].mr=a[i*2].mr+a[i*2+1].ml;
else
a[i].mr=a[i*2+1].mr;//如果說右面孩子是不是全空的，那a[i].mr久等於a[i*2+1].mr
if(a[i*2].mr==(a[i*2].r-a[i*2].l+1))//同上
a[i].ml=a[i*2+1].ml+a[i*2].mr;
else
a[i].ml=a[i*2].ml;//
還有就是懶惰標記啦，不標記就超時啦
[cpp]
#include<iostream>
#include<cstdio>
using namespace std;
#define N 16005
struct node{
int l,r,ml,mr,mm,len,sign;
}a[N*4];
void build(int i,int left,int right){
a[i].l=left;
a[i].r=right;
a[i].len=a[i].ml=a[i].mr=right-left+1;
a[i].mm=0;
a[i].sign=0;//表示這條邊是否被用過
if(left==right) return ;
int mid=(a[i].l+a[i].r)>>1;
build(i*2,left,mid);
build(i*2+1,mid+1,right);
}
void insert(int i,int left,int right,int sign){
// cout<<a[i].l<<" "<<a[i].r<<"****"<<left<<" "<<right<<endl;
if(a[i].l>=left&&a[i].r<=right){
a[i].sign=1;
if(sign==1){
a[i].len=a[i].ml=a[i].mr=0;
}else{
a[i].len=a[i].ml=a[i].mr=(a[i].r-a[i].l+1);
}
return ;
}
if(a[i].sign==1&&a[i].ml==0&&a[i].mr==0&&a[i].len==0){//懶惰標記
a[i*2+1].ml=a[i*2+1].mr=a[i*2+1].len=0;
a[i*2].ml=a[i*2].mr=a[i*2].len=0;
a[i*2+1].sign=a[i*2].sign=1;
a[i].sign=0;
}
if(a[i].sign==1&&a[i].ml==(a[i].r-a[i].l+1)&&a[i].mr==(a[i].r-a[i].l+1)&&a[i].len==(a[i].r-a[i].l+1)){//懶惰標記
a[i*2+1].ml=a[i*2+1].mr=a[i*2+1].len=(a[i*2+1].r-a[i*2+1].l+1);
a[i*2].ml=a[i*2].mr=a[i*2].len=(a[i*2].r-a[i*2].l+1);
a[i*2+1].sign=a[i*2].sign=1;
a[i].sign=0;
}
int mid=(a[i].l+a[i].r)>>1;
if(right<=mid) insert(i*2,left,right,sign);
else if(left>mid) insert(i*2+1,left,right,sign);
else{
insert(i*2,left,mid,sign);
insert(i*2+1,mid+1,right,sign);
}
a[i].len=max(a[i*2].mr+a[i*2+1].ml,max(a[i*2].len,a[i*2+1].len));
if(a[i*2+1].ml==(a[i*2+1].r-a[i*2+1].l+1))
a[i].mr=a[i*2].mr+a[i*2+1].ml;
else
a[i].mr=a[i*2+1].mr;
if(a[i*2].mr==(a[i*2].r-a[i*2].l+1))
a[i].ml=a[i*2+1].ml+a[i*2].mr;
else
a[i].ml=a[i*2].ml;
// cout<<"l="<<a[i].l<<" r="<<a[i].r<<" "<<a[i].ml<<" "<<a[i].len<<" "<<a[i].mr<<endl;
}
int main(){
int n,p,m,x,y;
while(~scanf("%d%d",&n,&p)){
build(1,1,n);
while(p--){
scanf("%d",&m);
if(m==1){
scanf("%d%d",&x,&y);
// cout<<"x+y-1="<<x+y-1<<endl;
insert(1,x,x+y-1,1);
}else if(m==2){
scanf("%d%d",&x,&y);
insert(1,x,x+y-1,0);
}
else
printf("%d\n",max(a[1].ml,max(a[1].len,a[1].mr)));
}
}
}
