Hotel

区间和并

#include<iostream>
#include<cstdio>
#include<cstring>
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define ls p<<1
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int maxn=5e4+5;
int n,m,a,b,c;
struct Node{
  int lsum,rsum,sum,add;                        //前缀长、后缀长、最长、 add：0（空）,1（满）,-1（初始化不向下传递标记）
}tr[maxn<<2];
void pushUp(int p,int l,int r,int mid){
  tr[p].sum=max(max(tr[ls].sum,tr[rs].sum),tr[ls].rsum+tr[rs].lsum);     //max（左或右区间内的最长，左区间的后缀和加上右区间的前缀和）
  tr[p].lsum=tr[ls].lsum;
  tr[p].rsum=tr[rs].rsum;
  if(tr[p].lsum==mid-l+1)tr[p].lsum+=tr[rs].lsum;                        //如果左区间的前缀和（1~mid）全是0，累计右区间的前缀和
  if(tr[p].rsum==r-mid)tr[p].rsum+=tr[ls].rsum;
}
void build(int p,int l,int r){
  tr[p].add=-1;
  tr[p].lsum=tr[p].rsum=tr[p].sum=r-l+1;
  if(l==r)return;
  int mid=l+r>>1;
  build(lson);
  build(rson);
}
void pushDown(int p,int l,int r,int mid){     //下传
  if(tr[p].add!=-1){
    tr[ls].add=tr[rs].add=tr[p].add;
    int flag=(tr[p].add?0:1);                //逻辑非
    tr[ls].sum=tr[ls].lsum=tr[ls].rsum=(flag?mid-l+1:0);                //如果空返回mid-l+1
    tr[rs].sum=tr[rs].lsum=tr[rs].rsum=(flag?r-mid:0);
    tr[p].add=-1;
}
}
void change(int p,int l,int r,int L,int R,int val){
  if(L<=l&&r<=R){
    tr[p].lsum=tr[p].rsum=tr[p].sum=(val?0:(r-l+1));                   //区间sum住人或者退房
    tr[p].add=val;                          //标记区间满房或者空房
    return;
  }
  int mid=l+r>>1;
  pushDown(p,l,r,mid);
  if(L<=mid)change(lson,L,R,val);
  if(R>mid)change(rson,L,R,val);
  pushUp(p,l,r,mid);
}
int query(int p,int l,int r,int val){
  if(l==r&&val==1)return l;
  int mid=l+r>>1;
  pushDown(p,l,r,mid);
  if(tr[ls].sum>=val)return query(lson,val);                          //左儿子的空房满足入住人数
  else if(tr[ls].rsum+tr[rs].lsum>=val)return mid-tr[ls].rsum+1;      //左儿子的右区间接壤右儿子的左区间
  else if(tr[rs].sum>=val)return query(rson,val);
  else return 0;
}
int main(){
  /*cin，cout效率低的原因是因为先存入缓冲区，再输出，导致效率降低，而这段代码可以来打消iostream的输入 输出缓存，可以节省许多时间，使效率与scanf与printf相差无几.*/
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin>>n>>m;                              //房间数量、操作次数
  build(1,1,n);                           //建树
  for(int i=1;i<=m;++i){
    cin>>a;
    if(a==2){                            //退房
     cin>>b>>c;
     change(1,1,n,b,b+c-1,0);
    }else{
      cin>>b;                            //入住
      int tmp=query(1,1,n,b);
      cout<<tmp<<"\n";
      if(tmp)change(1,1,n,tmp,tmp+b-1,1);
    }
  }
  return 0;
}

笔记：使用线段树求出最大连续区间的长度，一直维护前缀和后缀和与最长区间长度。使用两行代码提高scanf的运行效率