Hotel （线段树求解连续区间）

题目链接：https://vjudge.net/problem/POJ-3667

题目大意：n个连续的房间m个操作。操作分两种，

第一种以1 x形式给出，找到最左的能连续容下x个人的连续房间，并输出左端点的编号，如果找不到就输出0.

第二种以2 l x的形式给出，表示以l为起点的x个房间都清空。

思路：

采用线段树去维护最大连续区间。具体的讲解可以看：https://www.cnblogs.com/lonely-wind-/p/11667471.html

  1 #include <math.h>
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 #include <iostream>
  5 #include <algorithm>
  6 #include <string>
  7 #include <string.h>
  8 #include <vector>
  9 #include <map>
 10 #include <stack>
 11 #include <set>
 12 //#include <random>
 13 
 14 #define ll long long
 15 #define ls nod<<1
 16 #define rs (nod<<1)+1
 17 const int maxn = 1e5 + 10;
 18 
 19 
 20 struct segment_tree {
 21     int l,r;
 22     int lsum,rsum,sum;
 23     int lazy;
 24 }tree[maxn<<2];
 25 
 26 void pushup(int nod) {
 27     int l = tree[nod].l,r = tree[nod].r;
 28     int mid = (l + r) >> 1;
 29     tree[nod].sum = std::max(std::max(tree[ls].sum,tree[rs].sum),tree[ls].rsum + tree[rs].lsum);
 30     tree[nod].lsum = tree[ls].lsum;
 31     tree[nod].rsum = tree[rs].rsum;
 32     if (tree[ls].lsum == (mid-l+1))
 33         tree[nod].lsum = tree[ls].sum + tree[rs].lsum;
 34     if (tree[rs].rsum == (r-mid))
 35         tree[nod].rsum = tree[rs].sum + tree[ls].rsum;
 36 }
 37 
 38 void pushdown(int nod) {
 39     int l = tree[nod].l,r = tree[nod].r;
 40     int mid = (l + r ) >> 1;
 41     tree[ls].sum = tree[ls].rsum = tree[ls].lsum = tree[nod].lazy * (mid-l+1);
 42     tree[rs].sum = tree[rs].rsum = tree[rs].lsum = tree[nod].lazy * (r-mid);
 43     tree[ls].lazy = tree[rs].lazy = tree[nod].lazy;
 44     tree[nod].lazy = -1;
 45 }
 46 
 47 void build(int l,int r,int nod) {
 48     tree[nod].l = l;
 49     tree[nod].r = r;
 50     tree[nod].lazy = -1;
 51     tree[nod].lsum = tree[nod].rsum = tree[nod].sum = (r - l + 1);
 52     if (l == r)
 53         return ;
 54     int mid = (l + r ) >> 1;
 55     build(l,mid,ls);
 56     build(mid+1,r,rs);
 57 }
 58 
 59 void modify(int x,int y,int z,int nod=1) {
 60     int l = tree[nod].l,r = tree[nod].r;
 61     if (x <= l && y >= r) {
 62         tree[nod].lsum = tree[nod].rsum = tree[nod].sum = (r-l+1)*z;
 63         tree[nod].lazy = z;
 64         return ;
 65     }
 66     if (tree[nod].lazy != -1) {
 67         pushdown(nod);
 68     }
 69     int mid = (l + r) >> 1;
 70     if (x <= mid) {
 71         modify(x,y,z,ls);
 72     }
 73     if (y > mid) {
 74         modify(x,y,z,rs);
 75     }
 76     pushup(nod);
 77 }
 78 
 79 int query(int siz,int nod=1) {
 80     int l = tree[nod].l,r = tree[nod].r;
 81     int mid = (l + r) >> 1;
 82     if (l == r && siz == 1)
 83         return l;
 84     if (tree[nod].lazy != -1)
 85         pushdown(nod);
 86     if (tree[nod].sum >= siz) {
 87         if (tree[ls].sum >= siz)
 88             return query(siz,ls);
 89         else if (tree[ls].rsum + tree[rs].lsum >= siz) {
 90             return mid + 1 - tree[ls].rsum;
 91         }
 92         else
 93             return query(siz,rs);
 94     }
 95     return 0;
 96 }
 97 
 98 int main() {
 99     int n,m;
100     scanf("%d%d",&n,&m);
101     build(1,n,1);
102     while (m--) {
103         int opt;
104         scanf("%d",&opt);
105         if (opt == 1) {
106             int x;
107             scanf("%d",&x);
108             int temp = query(x,1);
109             printf("%d\n",temp);
110             if (!temp) {
111                 continue;
112             }
113             modify(temp,temp+x-1,0);
114         }
115         else {
116             int x,y;
117             scanf("%d%d",&x,&y);
118             modify(x,x+y-1,1);
119         }
120     }
121     return 0;
122 }