和前面的hotel类似，就是多了一个前缀和后缀；
#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define maxn 111111 int sum[maxn<<2],lsum[maxn<<2],rsum[maxn<<2],col[maxn<<2]; void pushdown(int rt,int m) { if(col[rt]!=-1) { col[rt<<1]=col[rt<<1|1]=col[rt]; sum[rt<<1]=lsum[rt<<1]=rsum[rt<<1]=col[rt]?0:(m-(m>>1)); sum[rt<<1|1]=lsum[rt<<1|1]=rsum[rt<<1|1]=col[rt]?0:(m>>1); col[rt]=-1; } } void pushup(int rt,int m) { lsum[rt]=lsum[rt<<1]; if(lsum[rt]==(m-(m>>1))) lsum[rt]+=lsum[rt<<1|1]; rsum[rt]=rsum[rt<<1|1]; if(rsum[rt]==(m>>1)) rsum[rt]+=rsum[rt<<1]; sum[rt]=max(max(sum[rt<<1],sum[rt<<1|1]),rsum[rt<<1]+lsum[rt<<1|1]); } void build(int l,int r,int rt) { sum[rt]=lsum[rt]=rsum[rt]=r-l+1; if(l==r) return ; int m=(l+r)>>1; build(lson); build(rson); } void update(int L,int R,int add,int l,int r,int rt) { if(L<=l&&R>=r) { sum[rt]=lsum[rt]=rsum[rt]=add?0:r-l+1;//add为1，把数组清空 col[rt]=add; return ; } pushdown(rt,r-l+1); int m=(l+r)>>1; if(L<=m) update(L,R,add,lson); if(R>m) update(L,R,add,rson); pushup(rt,r-l+1); } int query(int key,int l,int r,int rt) { if(l==r) return l; int m=(l+r)>>1; pushdown(rt,r-l+1); if(sum[rt<<1]>=key) return query(key,lson); else if(rsum[rt<<1]+lsum[rt<<1|1]>=key) return m-rsum[rt<<1]+1; else return query(key,rson); } int main() { int c,n,d; int m,a,b; int q[maxn],q1[maxn];//q数组保存每次停车的起点，q1保存车子的长度 scanf("%d%d%d",&n,&c,&d); build(1,c+n+d,1); scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); if(a==1) { if(c+b+d>sum[1])//如果剩余长度小于所需，输出-1 { printf("-1\n"); continue; } int pos=query(c+b+d,1,c+n+d,1); printf("%d\n",pos-1); update(c+pos,c+pos+b-1,1,1,c+n+d,1);//停完车后注意更新状态 q[i]=pos;q1[i]=b; } else { update(c+q[b],c+q[b]+q1[b]-1,0,1,c+n+d,1); } } return 0; }