★★☆ 输入文件：haoi13t4.in 输出文件：haoi13t4.out 简单对比
时间限制：1 s 内存限制：128 MB
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 <cstdio> #define N 50005 int n,M,m[N<<2|1],f[N<<2|1],lm[N<<2|1],rm[N<<2|1],siz[N<<2|1]; inline int min(int a,int b) {return a>b?b:a;} inline int max(int a,int b) {return a>b?a:b;} void pushup(int k) { m[k]=max(m[k<<1],max(m[k<<1|1],rm[k<<1]+lm[k<<1|1])); if(m[k<<1]==siz[k<<1]) lm[k]=siz[k<<1]+lm[k<<1|1]; else lm[k]=lm[k<<1]; if(m[k<<1|1]==siz[k<<1|1]) rm[k]=siz[k<<1|1]+rm[k<<1]; else rm[k]=rm[k<<1|1]; } void build(int k,int l,int r) { f[k]=-1; m[k]=lm[k]=rm[k]=siz[k]=r-l+1; if(l==r) return; int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); } inline void pushdown(int k) { if(siz[k]==1) return; f[k<<1]=f[k]; f[k<<1|1]=f[k]; lm[k<<1]=rm[k<<1]=m[k<<1]=siz[k<<1]*f[k]; lm[k<<1|1]=rm[k<<1|1]=m[k<<1|1]=siz[k<<1|1]*f[k]; f[k]=-1; } void modify(int k,int l,int r,int x,int y,int v) { if(l>=x&&r<=y) { lm[k]=rm[k]=m[k]=siz[k]*v; f[k]=v; return; } if(f[k]!=-1) pushdown(k); int mid=(l+r)>>1; if(x<=mid) modify(k<<1,l,mid,x,y,v); if(y>mid) modify(k<<1|1,mid+1,r,x,y,v); pushup(k); } int query(int k,int l,int r,int x) { if(m[k]==x&&lm[k]==x) return l; if(f[k]!=-1) pushdown(k); int mid=(l+r)>>1; if(m[k<<1]>=x) return query(k<<1,l,mid,x); if(rm[k<<1]+lm[k<<1|1]>=x) return mid-rm[k<<1]+1; if(m[k<<1|1]>=x) return query(k<<1|1,mid+1,r,x); pushup(k); } int Main() { freopen("haoi13t4.in","r",stdin); freopen("haoi13t4.out","w",stdout); scanf("%d%d",&n,&M); build(1,1,n); for(int opt,di,mi,p;M--;) { scanf("%d",&opt); if(opt==1) { scanf("%d",&mi); if(m[1]<mi) {puts("0");goto flag;} p=query(1,1,n,mi); modify(1,1,n,p,p+mi-1,0); printf("%d ",p); } else { scanf("%d%d",&di,&mi); modify(1,1,n,di,min(di+mi-1,n),1); } flag:; } fclose(stdin); fclose(stdout); return 0; } int sb=Main(); int main(int argc,char *argv[]){;}