解題區/解題區 - 其他題目

ADA 2020 Fall P2. Bomb Game

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Algorithm Design and Analysis (NTU CSIE, Fall 2020)

Problem

有數名玩家依序抵達遊戲，並且落在位置 $c_i$，並且具有防禦力 $d_i$，過程中會有炸彈發生於 $[l_i, r_i]$，對防禦力小於等於 $p_i$ 造成 $k_i$ 點傷害。

回報遊戲最後每一名玩家所受的傷害總額。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
10 10
P 3 5
A 2 8 15 5
P 7 10
A 4 10 5 3
A 1 9 10 7
P 6 20
P 5 1
A 4 9 17 2
A 1 2 20 4
P 9 5

Sample Output

1
2
3
4
5
12
9
0
2
0

Solution

由於沒辦法參與課程，就測測自己產的測試資料，正確性有待確認。

如果這一題目強制在線對答，則需要一個樹套樹在 $\mathcal{O}(\log^2 n)$ 內回答每一個結果，需要一個動態開區間的實作方法。

如果採用離線處理，則可以透過逆序處理來回答，可以透過二維空間的 BIT 結構來完成，這時候空間上會是另一個問題，即使使用懶惰標記，預期可能會達到 $\mathcal{O}(C \; D)$，通常是不允許的。

從分治算法切入，預想防禦能力高影響不受到攻擊力低的炸彈影響，無論時間與否都不受到影響。接下來，對防禦能力和攻擊力統稱力量。在分治的時候，對力量低的累計出答案，在合併階段受時間順序的影響才能回答。最後：

  1. 對力量從小到大排序
  2. 分治算法
    1. 對左區間和右區間按照時間由大到小排序
    2. 對於每一個左區間的詢問，插入所有滿足的右區間

時間複雜度 $\mathcal{O}(n \log^2 n)$、空間複雜度 $\mathcal{O}(n)$ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include <bits/stdc++.h>
using namespace std;
// Algorithm Design and Analysis (NTU CSIE, Fall 2020)
// Problem 2. Bomb Game
const int MAXN = 200005;
struct BIT {
    int64_t a[MAXN];
    int l[MAXN];
    int cases = 0;
    void add(int x, int val, int n) {
        while (x <= n) {
            if (l[x] != cases)
                l[x] = cases, a[x] = 0;
            a[x] += val, x += x&(-x);
        }
    }
    int64_t sum(int x) {
        int64_t ret = 0;
        while (x) {
            if (l[x] != cases)
                l[x] = cases, a[x] = 0;
            ret += a[x], x -= x&(-x);
        }
        return ret;
    }
    void reset(int n) {
        cases++;
    }
    void add(int l, int r, int k, int n) {
        add(l, k, n);
        add(r+1, -k, n);
    }
} bit;
int n;
struct PEvent {
    int c, d, i;
};
struct AEvent {
    int l, r, p, k;
};
struct Event {
    int type; // 'P' 0 or 'A' 1
    int time; // input order
    union {
        PEvent p;
        AEvent a;
    } data;
    int power() {
        if (type == 0)
            return data.p.d;
        else
            return data.a.p;
    }
    void println() {
        if (type == 0)
            printf("P %d %d\n", data.p.c, data.p.d);
        else
            printf("A %d %d %d %d\n", data.a.l, data.a.r, data.a.p, data.a.k);
    }
} events[MAXN];
static bool cmp_p(Event &a, Event &b) {
    int pa = a.power();
    int pb = b.power();
    if (pa != pb)
        return pa < pb;
    return a.time < b.time;
}
static bool cmp_t(Event &a, Event &b) {
    return a.time > b.time;
}
int ret[MAXN];
void resolve(int l, int m, int r) {
    sort(events+l, events+m+1, cmp_t);
    sort(events+m+1, events+r+1, cmp_t);
    //	printf("resolve %d %d =========\n", l, r);
    //	for (int i = l; i <= m; i++)
    //		events[i].println();
    //	puts("---");
    //	for (int i = m+1; i <= r; i++)
    //		events[i].println();
    bit.reset(n);
    int j = m+1;
    for (int i = l; i <= m; i++) {
        if (events[i].type)
            continue;
        int qtime = events[i].time;
        while (j <= r && events[j].time > qtime) {
            if (events[j].type) {
                bit.add(events[j].data.a.l,
                        events[j].data.a.r,
                        events[j].data.a.k,
                        n);
                //				printf("add %d %d %d %d\n", events[j].data.a.l,
                //						events[j].data.a.r,
                //						events[j].data.a.p,
                //						events[j].data.a.k);
            }
            j++;
        }
        //		printf("%d --- %d\n", events[i].data.p.i, bit.sum(events[i].data.p.c));
        ret[events[i].data.p.i] += bit.sum(events[i].data.p.c);
    }
}
void divide(int l, int r) {
    if (l >= r)
        return;
    int m = (l+r)/2;
    divide(l, m);
    divide(m+1, r);
    resolve(l, m, r);
}
int main() {
    int m;
    char s[2];
    scanf("%d %d", &n, &m);
    int id = 0;
    for (int i = 0; i < m; i++) {
        scanf("%s", s);
        events[i].time = i;
        if (s[0] == 'P') {
            events[i].type = 0;
            events[i].data.p.i = id++;
            scanf("%d %d",
                    &events[i].data.p.c,
                    &events[i].data.p.d);
        } else {
            events[i].type = 1;
            scanf("%d %d %d %d",
                    &events[i].data.a.l, 
                    &events[i].data.a.r,
                    &events[i].data.a.p,
                    &events[i].data.a.k);
        }
    }
    sort(events, events+m, cmp_p);
    divide(0, m-1);
    for (int i = 0; i < id; i++)	
        printf("%d\n", ret[i]);
    return 0;
}