POJ 3667 Hotel（线段树+区间合并）-白红宇

POJ 3667 Hotel（线段树+区间合并）

阅读量：4709 次

发布时间：2019-06-10

本文共 2550 字，大约阅读时间需要 8 分钟。

题意：

有N个房间，M次操作。有两种操作（1）"1a"，表示找到连续的长度为a的空房间，如果有多解，优先左边的，即表示入住。（2）"2 b len"，把起点为b长度的len的房间清空，即退房。

思路：

区间合并的线段树题。

其实如果单点更新和区间更新做得多了的话，区间合并也就不难了。

对于这道题，我们用线段树维护三个值，从左端开始的连续空房间数，从右边开始的连续空房间数，以及整个区间内最大的连续空房间数。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 #include
            
              9 #include
              10 #include
              
                11 using namespace std; 12 typedef long long ll; 13 const int INF = 0x3f3f3f3f; 14 const int maxn=50000+5; 15 16 int n, m; 17 18 struct node //维护从左端开始的最大连续空房间，从右端开始的最大连续空房间，总的最大连续空房间 19 { 20 int l,r; 21 int ls,rs,sum; 22 }t[maxn<<2]; 23 24 int lazy[maxn<<2]; 25 26 27 void PushUp(int o) 28 { 29 t[o].ls=t[o<<1].ls; 30 t[o].rs=t[o<<1|1].rs; 31 int mid=(t[o].l+t[o].r)>>1; 32 if(t[o].ls==mid-t[o].l+1) t[o].ls+=t[o<<1|1].ls; //如果左半部分都是空房间，那么可以与右半部分的左边空房间连起来 33 if(t[o].rs==t[o].r-mid) t[o].rs+=t[o<<1].rs; 34 t[o].sum=max(max(t[o<<1].sum,t[o<<1|1].sum),t[o<<1].rs+t[o<<1|1].ls); 35 } 36 37 void PushDonw(int o) 38 { 39 if(lazy[o]!=-1) 40 { 41 lazy[o<<1]=lazy[o<<1|1]=lazy[o]; 42 if(lazy[o]) //为1的话要将该区间置满 43 { 44 t[o<<1].ls=t[o<<1].rs=t[o<<1].sum=0; 45 t[o<<1|1].ls=t[o<<1|1].rs=t[o<<1|1].sum=0; 46 } 47 else //为0的话要将该区间置空 48 { 49 t[o<<1].ls=t[o<<1].rs=t[o<<1].sum=t[o<<1].r-t[o<<1].l+1; 50 t[o<<1|1].ls=t[o<<1|1].rs=t[o<<1|1].sum=t[o<<1|1].r-t[o<<1|1].l+1; 51 } 52 lazy[o]=-1; 53 } 54 } 55 56 void build(int l, int r, int o) 57 { 58 lazy[o]=-1; 59 t[o].l=l; 60 t[o].r=r; 61 t[o].ls=t[o].rs=t[o].sum=r-l+1; 62 if(l==r) return; 63 int mid=(l+r)>>1; 64 build(l,mid,o<<1); 65 build(mid+1,r,o<<1|1); 66 } 67 68 69 void update(int ql, int qr, int l, int r, int flag, int o) 70 { 71 if(ql<=l && qr>=r) 72 { 73 if(flag) t[o].ls=t[o].rs=t[o].sum=0; 74 else t[o].ls=t[o].rs=t[o].sum=r-l+1; 75 lazy[o]=flag; 76 return; 77 } 78 PushDonw(o); 79 int mid=(l+r)>>1; 80 if(ql<=mid) update(ql,qr,l,mid,flag,o<<1); 81 if(qr>mid) update(ql,qr,mid+1,r,flag,o<<1|1); 82 PushUp(o); 83 } 84 85 int query(int l, int r, int num, int o) 86 { 87 if(l==r) return l; 88 PushDonw(o); 89 int mid=(l+r)>>1; 90 if(t[o<<1].sum>=num) return query(l,mid,num,o<<1); 91 else if(t[o<<1].rs+t[o<<1|1].ls>=num) return mid-t[o<<1].rs+1; 92 else return query(mid+1,r,num,o<<1|1); 93 } 94 95 int main() 96 { 97 //freopen("in.txt","r",stdin); 98 scanf("%d%d",&n,&m); 99 build(1,n,1);100 while(m--)101 {102 int op;103 scanf("%d",&op);104 if(op==1)105 {106 int x;107 scanf("%d",&x);108 if(t[1].sum

转载于:https://www.cnblogs.com/zyb993963526/p/7452142.html

你可能感兴趣的文章