【题意】：有一块面积为h*w的通知栏，往上面贴一些1*wi的通知上去，贴的位置总是选择可以贴的最高位置的最左端，且通知不能重叠。给出n个通知，并询问它们分别贴在第几行。
【题解】：线段树，维护线段树的区间为[1, min(h,n)]，因为最坏情况也就一行贴一个，所以后面的是多余的。
因为查询和更新是同时的，所以我写在一起了。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 using namespace std;
11 #define pb push_back
12 #define lc(x) (x << 1)
13 #define rc(x) (x << 1 | 1)
14 #define lowbit(x) (x & (-x))
15 #define ll long long
16 #define MAX 200050
17 int sum[MAX<<2];
18 int h, w, n;
19
20 void pushup(int p) {
21 sum[p] = max(sum[lc(p)], sum[rc(p)]);
22 }
23
24 void build(int l, int r, int p) {
25 sum[p] = w;
26 if(l == r) return;
27 int mid = (l + r) >> 1;
28 build(l, mid, lc(p));
29 build(mid + 1, r, rc(p));
30 }
31
32 int query(int L, int l, int r, int p) {
33 if(l == r) {
34 sum[p] -= L; // 找到最优位置并更新
35 return l;
36 }
37 int mid = (l + r) >> 1, ans = -1;
38 if(L <= sum[lc(p)]) ans = query(L, l, mid, lc(p));
39 else ans = query(L, mid + 1, r, rc(p));
40 pushup(p);
41 return ans;
42 }
43
44 int main() {
45 int L;
46 while(~scanf("%d%d%d", &h, &w, &n)) {
47 if(h > n) h = n;
48 build(1, h, 1);
49 for(int i = 0; i < n; i++) {
50 scanf("%d", &L);
51 if(sum[1] < L) printf("-1\n");
52 else printf("%d\n", query(L, 1, h, 1));
53 }
54 }
55 return 0;
56 }
57