poj 3667 Hotel 线段树 内存分配问题
我写这道提真是元气大伤，一开始写完，自己写几组数据都过不了，在网上看别人的解题报告，总是感觉代码太复杂，都不愿意看，还是改自己的吧，后来就有重写的欲望，删了一百多行，在写，有写测试数据的生成程序测，最后又写了一个暴力程序对拍，擦擦！！断断续续的整了两天，现在看自己的代码也很乱，我估计谁也看不进去
我就说一下大概思想吧，用mm表示中间连续最大值 mr表示右边连续 ml表示左边边连续 len表示整个线段连续
都不愿意写了，总之大部分设计 查找和删除都要lazy一下，
鼓励大家坚持自己的做，这种题看别人代码都感觉代码很恶心，看上去很复杂的样子
#include<iostream>#include<cstdio>using namespace std;#define N 60005struct 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{ scanf("%d",&x); p=0; insert(1,x); printf("%d\n",p); } } } return 0;}