再发个题给大家娱乐下
谁第一个找出下面代码的那处错误（就一处错误，且是个很白痴的错误) 就得100分^_^希望大家以后不要范同样的错误， 写程序一定要养成仔细再仔细的习惯啊，不然后果很痛苦啊。
这个错误我搞了2个多小时才发现了， 发现后 诶～～～ 苦笑不得啊。
题目OJ ：http://
代码：
#include<iostream>
#include<cstdio>
using namespace std;
int lmax[300000]; //当前区间包含最左边的房间的最长空房间数
int rmax[300000]; //当前区间包含最右边的房间的最长空房间数
int maxlen[300000]; //当前区间连续空房间的最大长度
int flag[300000]; //标记当前区间的状态，0表示没人住，1表示有人住， -1表示有些房间有人住有些房间没人住
// rt<<1 等价于rt*2;
// rt<<1|1 等价于 rt*2+1;
void pushUp(int rt,int l,int r){
int len=r-l+1;
lmax[rt] = lmax[rt<<1];
rmax[rt] = rmax[rt<<1|1];
if(lmax[rt] == len -len/2 ) lmax[rt]+=lmax[rt<<1|1];
if(rmax[rt] == len/2) rmax[rt]+=rmax[rt<<1];
int temp = maxlen[rt<<1] > maxlen[rt<<1|1] ? maxlen[rt<<1] : maxlen[rt<<1|1];
maxlen[rt] = temp > (rmax[rt<<1] + lmax[rt<<1|1]) ? temp : (rmax[rt<<1]+lmax[rt<<1|1]);
}
void pushDown( int rt, int l, int r ){
int len = r - l +1;
if( flag[rt] != -1 ){
flag[rt<<1] = flag[rt];
flag[rt<<1|1] = flag[rt];
maxlen[rt<<1] = lmax[rt<<1] = rmax[rt<<1] = (flag[rt]? 0:len-len/2);
maxlen[rt<<1|1] = lmax[rt<<1|1] = rmax[rt<<1|1] = (flag[rt] ? 0:len);
flag[rt] = -1;
}
}
void buildTree(int l, int r, int rt){
flag[rt]=-1;
lmax[rt] = rmax[rt] = maxlen[rt]=r-l+1;
if( l == r ) return;
int mid = (l+r) >> 1;
buildTree(l,mid,rt<<1);
buildTree(mid+1,r,rt<<1|1);
}
void add(int l,int r,int c,int L,int R,int rt){
if( l<= L && r>=R ){
maxlen[rt] = lmax[rt] = rmax[rt] = c? 0: R-L+1;
flag[rt]=c;
return;
}
pushDown(rt,L,R);
int mid = (L+R) >> 1;
if( l <= mid ) add(l,r,c,L,mid,rt<<1 );
if( r > mid ) add(l,r,c,mid+1,R, rt<<1|1 );
pushUp(rt,L,R);
}
int query(int len, int l , int r, int rt){
if(l==r) return l;
pushDown(rt,l,r);
int mid = (l+r) >> 1;
if(maxlen[rt<<1] >= len ) return query(len,l,mid,rt<<1);
else if( rmax[rt<<1]+lmax[rt<<1|1] >=len ) return mid - rmax[rt<<1]+1;
else return query(len,mid+1,r,rt<<1|1);
}
int main(){
int n,m;
scanf("%d%d",&n,&m);{
buildTree(1,n,1);
for(int i=0; i<m; ++i ){
int t;
scanf("%d",&t);
if(t==1){
int len;
cin >> len;
if(len > maxlen[1] ) puts("0");
else{
int temp = query(len,1,n,1);
printf("%d\n",temp);
add(temp,temp+len-1,1,1,n,1);
}
}else {
int l,r;
scanf("%d%d",&l,&r);
add(l,l+r-1,0,1,n,1);
}
}
}
return 0;
}
[ 本帖最后由 草狼 于 2011-8-22 09:38 编辑 ]
