poj3667Hotel(线段树区间合并)

题目链接：http://poj.org/problem?id=3667

题目大意：给你一排n个房间，你有两种操作，1操作是占据x个房间，尽量往左占(也就是第一个编号尽可能小)，空房间不够输出0，2操作是让你释放从x到x+y-1的房间，让他们成为空房间。

这道题是线段树区间合并的典型例题，我为了解决这道题花费了两三天的时间(其实大部分时间都在摸鱼QAQ)，在此期间我找了很多的博客去学习，结果不尽人意，就在我苦思冥想该怎么办的时候，突发奇想去b站了搜了一波，结果发现了一个宝藏视频，视频链接（我在想有没有一种可能是我前几天看的博客，在今天晚上厚积薄发了，但这个视频雀氏不错），之后我在看完这个视频后就顿悟了，hh，挺开心的，我想，这就是算法竞赛的乐趣之一吧。

ac代码：

  1 #include
  2 #include
  3 #include
  4 #include
  5 #include
  6 #include
  7 #include<set>
  8 #include
  9 #include
 10 #include
 11 #include<string>
 12 #define ll long long
 13 #define ull unsigned long long
 14 #define inf 0x3f3f3f3f
 15 #define inff 0x7fffffff
 16 using namespace std;
 17 const int N = 50000 + 10;
 18 const int M = 1000000 + 10;
 19 const ll mod = 1e9 + 7;
 20 
 21 struct node {
 22     int lsum;
 23     int rsum;
 24     int sum;
 25     int lazy;
 26     int len;
 27 }tree[N << 2];
 28 
 29 void PushUp(int rt) {
 30 
 31     if (tree[rt << 1].sum == tree[rt << 1].len) {
 32         tree[rt].lsum = tree[rt << 1].sum + tree[rt << 1 | 1].lsum;
 33     }
 34     else {
 35         tree[rt].lsum = tree[rt << 1].lsum;
 36     }
 37     if (tree[rt << 1 | 1].sum == tree[rt << 1 | 1].len) {
 38         tree[rt].rsum = tree[rt << 1 | 1].sum + tree[rt << 1].rsum;
 39     }
 40     else {
 41         tree[rt].rsum = tree[rt << 1 | 1].rsum;
 42     }
 43     tree[rt].sum = tree[rt << 1].rsum + tree[rt << 1 | 1].lsum;
 44     tree[rt].sum = max(tree[rt << 1].sum, tree[rt].sum);
 45     tree[rt].sum = max(tree[rt << 1 | 1].sum, tree[rt].sum);
 46 
 47     return;
 48 }
 49 
 50 void Build(int l, int r, int rt) {
 51 
 52     tree[rt].len = r - l + 1;
 53     if (l == r) {
 54         tree[rt].sum = tree[rt].lsum = tree[rt].rsum = 1;
 55         return;
 56     }
 57     int mid = (l + r) >> 1;
 58     Build(l, mid, rt << 1);
 59     Build(mid + 1, r, rt << 1 | 1);
 60     PushUp(rt);
 61 
 62     return;
 63 }
 64 
 65 void PushDown(int l, int r, int rt) {
 66 
 67     if (tree[rt].lazy == 0) return;
 68     int mid = (l + r) >> 1;
 69     if (tree[rt].lazy == 1) {
 70         tree[rt << 1].sum = tree[rt << 1].lsum = tree[rt << 1].rsum = 0;
 71         tree[rt << 1 | 1].sum = tree[rt << 1 | 1].lsum = tree[rt << 1 | 1].rsum = 0;
 72         tree[rt << 1].lazy = tree[rt << 1 | 1].lazy = 1;
 73     }
 74     else {
 75         tree[rt << 1].sum = tree[rt << 1].lsum = tree[rt << 1].rsum = mid - l + 1;
 76         tree[rt << 1 | 1].sum = tree[rt << 1 | 1].lsum = tree[rt << 1 | 1].rsum = r - (mid + 1) + 1;
 77         tree[rt << 1].lazy = tree[rt << 1 | 1].lazy = 2;
 78     }
 79     tree[rt].lazy = 0;
 80 
 81     return;
 82 }
 83 
 84 void Update_in(int L, int R, int l, int r, int rt) {
 85 
 86     if (l >= L && r <= R) {
 87         tree[rt].sum = tree[rt].lsum = tree[rt].rsum = 0;
 88         tree[rt].lazy = 1;
 89         return;
 90     }
 91     PushDown(l, r, rt);
 92     int mid = (l + r) >> 1;
 93     if (L <= mid) Update_in(L, R, l, mid, rt << 1);
 94     if (R > mid) Update_in(L, R, mid + 1, r, rt << 1 | 1);
 95     PushUp(rt);
 96 
 97     return;
 98 }
 99 
100 void Update_out(int L, int R, int l, int r, int rt) {
101 
102     if (l >= L && r <= R) {
103         tree[rt].sum = tree[rt].lsum = tree[rt].rsum = r - l + 1;
104         tree[rt].lazy = 2;
105         return;
106     }
107     PushDown(l, r, rt);
108     int mid = (l + r) >> 1;
109     if (L <= mid) Update_out(L, R, l, mid, rt << 1);
110     if (R > mid) Update_out(L, R, mid + 1, r, rt << 1 | 1);
111     PushUp(rt);
112 
113     return;
114 }
115 
116 //void PointUpdate(int L, int l, int r, int rt) {
117 //
118 //    if (l == r) {
119 //        sum[rt]++;
120 //        return;
121 //    }
122 //    int mid = (l + r) >> 1;
123 //    if (L <= mid) PointUpdate(L, l, mid, rt << 1);
124 //    else PointUpdate(L, mid + 1, r, rt << 1 | 1);
125 //    PushUp(rt);
126 //
127 //    return;
128 //}
129 
130 int Query(int len, int l, int r, int rt) {
131 
132     if (l == r) return l;
133     int mid = (l + r) >> 1;
134     PushDown(l, r, rt);
135     if (tree[rt << 1].sum >= len) {
136         return Query(len, l, mid, rt << 1);
137     }
138     if (tree[rt << 1].rsum + tree[rt << 1 | 1].lsum >= len) {
139         return mid - tree[rt << 1].rsum + 1;
140     }
141     if (tree[rt << 1 | 1].sum >= len) {
142         return Query(len, mid + 1, r, rt << 1 | 1);
143     }
144 
145     return 0;
146 }
147 
148 //int Query(int L, int R, int l, int r, int rt) {
149 //
150 //    if (l >= L && r <= R) {
151 //        return sum[rt];
152 //    }
153 //    int mid = (l + r) >> 1;
154 //
155 //    int ans = 0;
156 //    if (L <= mid) ans += Query(L, R, l, mid, rt << 1);
157 //    if (R > mid) ans += Query(L, R, mid + 1, r, rt << 1 | 1);
158 //
159 //    return ans;
160 //}
161 
162 int main() {
163 
164     ios::sync_with_stdio(false);
165     cin.tie(0);
166     int n, m;
167     cin >> n >> m;
168     Build(1, n, 1);
169     for (int i = 1; i <= m; i++) {
170         int op, x, y;
171         cin >> op;
172         if (op == 1) {
173             cin >> x;
174             int pos = Query(x, 1, n, 1);
175             if (pos != 0) Update_in(pos, pos + x - 1, 1, n, 1);
176             cout << pos << "\n";
177         }
178         else {
179             cin >> x >> y;
180             Update_out(x, x + y - 1, 1, n, 1);
181         }
182     }
183 
184     return 0;
185 }

线段树

poj3667Hotel(线段树区间合并)

相关

#直径，线段树#51nod 1766 树上的最远点对

「NOI2020」命运（树形DP+线段树合并）

线段树学习笔记 1

关于线段树的一些认识

线段树

[NOI2015]软件包管理器（巧用线段树）

P6242 【模板】线段树 3

P5494 【模板】线段树分裂

CF1557D Ezzat and Grid（线段树）

cf739 C. Alyona and towers（线段树）

可持久化线段树

Codeforces Round #625 Div1 C,二维偏序，排序+线段树

标签