Dr.Kong有一个容量为N MB (1 <= N <= 50,000)的存储磁盘,不妨设地址空间编号为1到N。现在他需要安装一些软件， 每个软件要占用一定大小的容量且必须装在连续的地址空间里。比如发出指令“1 100”，表示需要申请100 MB的存储空间。如果有多个满足条件的连续空间，则选择起始地址最小的一个进行分配。若没有足够的连续空间，将不安装此软件（即使有足够多的不连续存储空间）。
系统可以不定时的卸载软件，释放磁盘的空间。比如：发出“2 23 100”，表示释放起始地址为23的连续100MB大小的容量。释放时，不需要考虑这些空间里是否安装过软件。
请你编写一个程序，帮助Dr.Kong处理M (1 <= M <= 50,000)个按指令次序请求的任务。第一个请求到来前，磁盘是空的。
输入格式:
第1行: N M
第2..M+1行: 每行描述了一个请求，如果是申请，则用2个数字 1 Mi 表示；
如果是释放，则用3个数字 2 Di Mi表示。数据之间用一个空格隔开
（1<=Di ,Mi<= 50,000）
输出格式:
对于每个申请指令，输出1行。如果请求能被满足，输出满足条件的最小起始地址；如果请求无法被满足，输出0。
输入样例 :
10 6
1 3
1 3
1 3
1 3
2 5 5
1 6
输出样例 :
1
4
7
0
5
题解：
线段树维护区间最长空闲段
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn=100000+10; int maxx[maxn*4],lsum[maxn*4],rsum[maxn*4]; int lr[maxn*4],tag[maxn*4]; int ql,qr; int n; inline void pushup(int o,int l,int r){ int mid=(l+r)>>1; lsum[o]=lsum[o<<1]; rsum[o]=rsum[o<<1|1]; if(rsum[o<<1|1]==r-mid&&rsum[o<<1]) rsum[o]=r-mid+rsum[o<<1]; if(lsum[o<<1]==mid-l+1&&lsum[o<<1|1]) lsum[o]=mid-l+1+lsum[o<<1|1]; if(maxx[o<<1]>=maxx[o<<1|1]){ maxx[o]=maxx[o<<1]; lr[o]=lr[o<<1]; } else { maxx[o]=maxx[o<<1|1]; lr[o]=lr[o<<1|1]; } if(rsum[o<<1]&&lsum[o<<1|1]){ int tot=rsum[o<<1]+lsum[o<<1|1]; if(tot>maxx[o]||(tot==maxx[o]&&mid-rsum[o<<1]+1<lr[o])){ maxx[o]=tot; lr[o]=mid-rsum[o<<1]+1; } } } inline void pushdown(int o,int l,int r){ if(tag[o]==-1) return ; int mid=(l+r)>>1; if(tag[o]==0){ maxx[o<<1]=lsum[o<<1]=rsum[o<<1]=0; lr[o<<1]=l; tag[o<<1]=0; maxx[o<<1|1]=lsum[o<<1|1]=rsum[o<<1|1]=0; lr[o<<1|1]=mid+1; tag[o<<1|1]=0; } else { maxx[o<<1]=lsum[o<<1]=rsum[o<<1]=mid-l+1; lr[o<<1]=l; tag[o<<1]=1; maxx[o<<1|1]=lsum[o<<1|1]=rsum[o<<1|1]=r-mid; lr[o<<1|1]=mid+1; tag[o<<1|1]=1; } tag[o]=-1; } inline void change(int o,int l,int r){ pushdown(o,l,r); if(ql<=l&&r<=qr){ maxx[o]=lsum[o]=rsum[o]=r-l+1; tag[o]=1; lr[o]=l; return ; } else if(l!=r){ int mid=(l+r)>>1; if(mid>=ql) change(o<<1,l,mid); if(mid<qr) change(o<<1|1,mid+1,r); pushup(o,l,r); } } inline void add(int o,int l,int r){ pushdown(o,l,r); if(ql<=l&&r<=qr){ maxx[o]=lsum[o]=rsum[o]=0; tag[o]=0; lr[o]=l; return ; } else if(l!=r){ int mid=(l+r)>>1; if(mid>=ql) add(o<<1,l,mid); if(mid<qr) add(o<<1|1,mid+1,r); pushup(o,l,r); } } inline void build(int o,int l,int r){ if(l==r){ maxx[o]=lsum[o]=rsum[o]=r-l+1; tag[o]=-1; lr[o]=l; return ; } else { tag[o]=-1; int mid=(l+r)>>1; build(o<<1,l,mid); build(o<<1|1,mid+1,r); pushup(o,l,r); } } /*inline int query(int x){ int now=1,l=1,r=n; if(maxx[now]<x) return 0x7fffffff; while(1){ int mid=(l+r)>>1; if(maxx[now<<1]>=x){ r=mid; now=now<<1; continue; } if(rsum[now<<1]&&lsum[now<<1|1]&&rsum[now<<1]+lsum[now<<1|1]>=x&&mid-rsum[now<<1]+1<lr[now]) return mid-rsum[now<<1]+1; if(maxx[now<<1|1]>=x&&lr[now<<1|1]<lr[now]){ l=mid+1; now=now<<1|1; continue; } return lr[now]; } }*/ inline int query(int o,int l,int r,int x){ pushdown(o,l,r); if(l==r&&maxx[o]<x) return 0x7fffffff; int mid=(l+r)>>1; if(maxx[o<<1]>=x) return query(o<<1,l,mid,x); if(rsum[o<<1]+lsum[o<<1|1]>=x) return mid-rsum[o<<1]+1; return query(o<<1|1,mid+1,r,x); } int main(){ freopen("haoi13t4.in","r",stdin); freopen("haoi13t4.out","w",stdout); int m; scanf("%d %d",&n,&m); int x,y,z; build(1,1,n); while(m--){ scanf("%d",&x); if(x==1){ scanf("%d",&y); int ans=query(1,1,n,y); if(ans!=0x7fffffff) printf("%d\n",ans); else puts("0"); ql=ans,qr=ans+y-1; add(1,1,n); } else { scanf("%d %d",&y,&z); ql=y; qr=y+z-1; change(1,1,n); } } return 0; } upd:注释掉的查询错误在于如果最长段与右儿子重合 并且右儿子段中有比右儿子最长段小但比查询段大 且在右儿子最长段左边 会返回右儿子最长段