计蒜客：公告板（线段树）

 难点在于要把模型抽象出来。

第一眼看到题面，想到的是以公告板的高度作为线段树的区间，但看到h<=10^9以后，感觉又开不了这么大的数组。但实际上，最多只有n块公告，所以最极端的情况下不过只有n行，所以区间的真正大小是[1,min(n,h)]。

解决了区间的问题，再来考虑每个节点要维护的信息。我们希望从线段树中获得的是在区间[1,min(n,h)]中能放置新公告的最小下标，所以我们维护节点信息的可以是该区间已使用的最小宽度或者剩余的最大宽度，其中剩余的最大宽度更适合我们正向思考。

区间和节点信息的意义确认之后，我们就要为如何快速得到结果进行准备了。考虑到我们要获得的是最小下标，所以我们优先向左边的区间进行遍历，即当左子树代表的区间内有可以容纳该公告的行时就直接往左遍历。遍历优先级确认后，就可以写代码了。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int h,w,n;
 4 vector<int> rest(200000 * 4, 0); //rest[p]表示p结点对应区间内的最大剩余宽度
 5 
 6 void modify(int p, int left, int right, int x, int y) {
 7     if (left == right) { //更新第x行的最大剩余宽度
 8         rest[p] += y;
 9         return;
10     }
11     int mid = (left + right) / 2;
12     if (x <= mid) {
13         modify(p * 2, left, mid, x, y);
14     } else {
15         modify(p * 2 + 1, mid + 1, right, x, y);
16     }
17     rest[p] = max(rest[p * 2], rest[p * 2 + 1]);
18 }
19 int query(int p, int left, int right , int x) {
20     if (rest[p] < x){
21         return -1;
22     }
23     if (left == right) {
24         return left;
25     }
26     int mid = (left + right) / 2;
27     if (x <= rest[p * 2]) { //优先往左遍历
28         return query(p * 2, left, mid, x);
29     }
30     if (x <= rest[p * 2 + 1]) {
31         return query(p * 2 + 1, mid + 1, right, x);
32     }
33 }
34 int main(){
35     cin >> h >> w >> n;
36     int len = min(h, n), temp;
37     for (int i = 1; i <= len; ++i) { //初始化剩余宽度
38         modify(1 , 1, len, i, w);
39     }
40     for (int i = 1; i <= n; ++i) {
41         scanf("%d", &temp);
42         int res = query(1, 1, len, temp);
43         if (res != -1)
44             modify(1, 1, len, res, -temp);
45         printf("%d\n", res);
46     }
47 }