【題意】：有一塊面積為h*w的通知欄，往上面貼一些1*wi的通知上去，貼的位置總是選擇可以貼的最高位置的最左端，且通知不能重疊。給出n個(gè)通知，并詢問(wèn)它們分別貼在第幾行。
【題解】：線段樹(shù)，維護(hù)線段樹(shù)的區(qū)間為[1, min(h,n)]，因?yàn)樽顗那闆r也就一行貼一個(gè)，所以后面的是多余的。
因?yàn)椴樵兒透率峭瑫r(shí)的，所以我寫在一起了。
【代碼】：
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; // 找到最優(yōu)位置并更新
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