我寫這道提真是元氣大傷，一開始寫完，自己寫幾組數據都過不了，在網上看別人的解題報告，總是感覺代碼太復雜，都不願意看，還是改自己的吧，後來就有重寫的欲望，刪了一百多行，在寫，有寫測試數據的生成程序測，最後又寫了一個暴力程序對拍，擦擦！！斷斷續續的整了兩天，現在看自己的代碼也很亂，我估計誰也看不進去
我就說一下大概思想吧，用mm表示中間連續最大值 mr表示右邊連續 ml表示左邊邊連續 len表示整個線段連續
都不願意寫了，總之大部分設計 查找和刪除都要lazy一下，
鼓勵大家堅持自己的做，這種題看別人代碼都感覺代碼很惡心，看上去很復雜的樣子
[cpp]
#include<iostream>
#include<cstdio>
using namespace std;
#define N 60005
struct node{
int l,r,ml,mr,mm,len;
}a[N*4];
int n;
void build(int i,int left,int right){
a[i].l=left;
a[i].r=right;
a[i].ml=a[i].mr=a[i].mm=a[i].len=(right-left+1);
if(left==right) return ;
int mid=(left+right)>>1;
build(i*2,left,mid);
build(i*2+1,mid+1,right);
}
int p;
void lazy(int i){
if(a[i].mr==a[i].r-a[i].l+1&&a[i].l!=a[i].r){
a[i*2].ml=a[i*2].mr=a[i*2].mm=a[i*2].len=(a[i*2].r-a[i*2].l+1);
a[i*2+1].ml=a[i*2+1].mr=a[i*2+1].mm=a[i*2+1].len=(a[i*2+1].r-a[i*2+1].l+1);
}
if(a[i].ml==a[i].mr&&a[i].mr==a[i].mm&&a[i].mr==0){
a[i*2].ml=a[i].ml;
a[i*2].mr=a[i].mr;
a[i*2].mm=a[i].mm;
a[i*2].len=a[i].len;
a[i*2+1].ml=a[i].ml;
a[i*2+1].mr=a[i].mr;
a[i*2+1].mm=a[i].mm;
a[i*2+1].len=a[i].len;
}
}
void deal(int i,int left,int right){
lazy(i);
if(a[i].l==left&&a[i].r==right){
a[i].ml=a[i].mr=a[i].mm=a[i].len=0;
return ;
}
int mid=(a[i].l+a[i].r)>>1;
if(right<=mid) deal(i*2,left,right);
else if(left>mid) deal(i*2+1,left,right);
else{
deal(i*2,left,mid);
deal(i*2+1,mid+1,right);
}
if(a[i*2].ml==(a[i*2].r-a[i*2].l+1))
a[i].mm=a[i].ml=a[i*2].ml+a[i*2+1].ml;
else a[i].ml=a[i*2].ml;
if(a[i*2+1].ml==(a[i*2+1].r-a[i*2+1].l+1))
a[i].mm=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].ml!=(a[i*2].r-a[i*2].l+1)&&a[i*2+1].mr!=(a[i*2+1].r-a[i*2+1].l+1))
a[i].mm=max(a[i*2].mr+a[i*2+1].ml,max(a[i*2].mm,a[i*2+1].mm));
a[i].len=max(a[i].mm,max(a[i].ml,a[i].mr));
}
void insert(int i,int k){
lazy(i);
if(a[i].len>=k){
if(a[i].ml>=k&&a[i*2].len<k&&a[i*2+1].len<k){
p=a[i].l;
deal(1,a[i].l,a[i].l+k-1);////////////////////////////////////
return ;
}else if(a[i].mm>=k&&(a[i*2].mr+a[i*2+1].ml>=k)&&a[i*2].len<k){//&&a[i*2+1].len<k
int temp=a[i*2].r-a[i*2].mr+1;
int tmr=a[i*2].mr;
if(a[i*2].mr==0) deal(1,a[i*2].r-a[i*2].mr+1,a[i*2].r+1);///////0///////這個邊界文題，當a[i*2].mr==0時要特殊處理
else deal(1,a[i*2].r-a[i*2].mr+1,a[i*2].r);
deal(1,a[i*2+1].l,a[i*2+1].l+k-tmr-1);////////////////////////////
p=temp;
return ;
}else if(a[i].mr>=k&&a[i*2].len<k&&a[i*2+1].len<k){
int temp=a[i].r-a[i].mr+1;
deal(1,a[i].r-a[i].mr+1,a[i].r-a[i].mr+k);
p=temp;
return ;
}
}
int mid=(a[i].l+a[i].r)>>1;
if(a[i*2].len>=k) insert(i*2,k);
else if(a[i*2+1].len>=k) insert(i*2+1,k);
}
void del(int i,int left,int right){
if(left<1) left=1;
if(right>n) right=n;
if(a[i].l==left&&a[i].r==right){
a[i].ml=a[i].mr=a[i].mm=a[i].len=(right-left+1);
return ;
}
lazy(i);
int mid=(a[i].l+a[i].r)>>1;
if(left>mid) del(i*2+1,left,right);
else if(right<=mid) del(i*2,left,right);
else{
del(i*2,left,mid);
del(i*2+1,mid+1,right);
}
if(a[i*2].ml==(a[i*2].r-a[i*2].l+1))
a[i].mm=a[i].ml=a[i*2].ml+a[i*2+1].ml;
else a[i].ml=a[i*2].ml;
if(a[i*2+1].ml==(a[i*2+1].r-a[i*2+1].l+1))
a[i].mm=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].ml!=(a[i*2].r-a[i*2].l+1)&&a[i*2+1].mr!=(a[i*2+1].r-a[i*2+1].l+1))
a[i].mm=max(a[i*2].mr+a[i*2+1].ml,max(a[i*2].mm,a[i*2+1].mm));
a[i].len=max(a[i].mm,max(a[i].ml,a[i].mr));
}
int main(){
// freopen("in.txt","r",stdin);
int m,x,y,t;
while(~scanf("%d%d",&n,&m)){
build(1,1,n);
while(m--){
scanf("%d",&t);
if(t==2){
scanf("%d%d",&x,&y);
del(1,x,x+y-1);
}else{ www.2cto.com
scanf("%d",&x);
p=0;
insert(1,x);
printf("%d\n",p);
}
}
}
return 0;
}
作者：youngyangyang04
