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

[Tmt514] Beverage Cup 2 Warmup B - The Brush

contents

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

Problem

給一個 $N \times N$ 的棋盤，放置城堡 (rook)，城堡只能攻擊同行同列，這裡更特別一些，只能攻擊右下角位置。

下方是一個 $5 \times 5$ 範例，其中 R 表示城堡的位置，* 表示城堡可攻擊的格子，也就是範例的第三組測資。

1
2
3
4
5
6
7
8
9
10
11
12
+-+-+-+-+-+
| | | | |R| 1
+-+-+-+-+-+ 
| | |R|*|*| 2
+-+-+-+-+-+
| |R|*|*|*| 3
+-+-+-+-+-+
|R|*|*|*|*| 4
+-+-+-+-+-+
|*|*|*|R|*| 5
+-+-+-+-+-+
 1 2 3 4 5

保證輸入中城堡不會出現在同行同列，請問可攻擊的格子有多少個 (意即計算 * 的數量)。

Sample Input

1
2
3
4
5
6
7
3
3
1 2 3
5
5 4 3 2 1
5
5 3 2 1 4

Sample Output

1
2
3
6
10
13

Solution

很明顯地發現，答案是 所有城堡可攻擊數量總和 扣除 交集點數量 ，兩兩城堡最多一個交集點，並且交集點不會重疊 (不同行列的關係)，而交集點只發生在逆序對中。因此找到逆序對總數，可以利用 D&C 的 merge sort 算法，或者套用 Binary indexed tree，利用掃描線思路找到逆序對。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int n, A[131072];
int BIT[131072];
void modify(int x, int val) {
    while (x <= n) {
        BIT[x] += val;
        x += x&(-x);
    }
}
int query(int x) {
    int ret = 0;
    while (x) {
        ret += BIT[x];
        x -= x&(-x);
    }
    return ret;
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n); 
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        
        for (int i = 0; i <= n; i++)
            BIT[i] = 0;
        long long ret = 0;
        for (int i = 0; i < n; i++) {
            ret += n - A[i];
            ret += n - i - 1;
            ret -= i - query(A[i]-1);
            modify(A[i], 1);
        }
        printf("%lld\n", ret);
    }
    return 0;
}
/*
3
3
1 2 3
5
5 4 3 2 1
5
5 3 2 1 4
*/