多筆測資，給一個$N\times N$的矩陣，每格有數字$a_{i,j}$，還有$Q$筆詢問。
對於每筆詢問，給定一個子矩陣範圍，輸出該子矩陣內的絕對多數或告知不存在。
絕對多數的定義是出現次數嚴格大於子矩陣大小的一半。
$N\le 2000, \sum N^2\le 1.25\times 10^7, \sum Q\le 70, a_{i, j}\le 10^9$
首先觀察到Q很小，雖然$N$真的很大，不過$\mathcal{O}(QN^2)$的複雜度其實是可行的。
所以對於每筆詢問，我們可以暴力跑遍一次子矩陣。
然而空間很緊，就算離散化再額外開個$4\times 10^6$的陣列都會MLE。
不過有個很經典的手段可以用$\mathcal{O}(1)$的空間找出絕對多數。
想像在一個擂台上，台上站著一個元素，這時加進一個新元素，如果該元素跟擂台上的元素一樣，就把血量給+1，否則血量-1。
如果血量已經歸零就下台，加進的那個元素上來，同時hp設為1。如果存在絕對多數，那最後站在擂台上的元素肯定會是絕對多數。
至於不存在絕對多數呢?既然已經知道了”可能的答案”，就再遍歷一次，計算那個答案的出現次數是否嚴格大於子矩陣大小的一半。
複雜度$\mathcal{O}(Q\sum N^2)$，空間複雜度$\mathcal{O}(N^2)$。
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
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
int arr[2000][2000];
signed main() { EmiliaMyWife
int n;
while(cin >> n, n) {
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
cin >> arr[i][j];
int q;
cin >> q;
while(q--) {
int r1, r2, c1, c2;
cin >> r1 >> r2 >> c1 >> c2;
r2++; c2++;
int cur = 0, hp = 0;
for(int i = r1; i < r2; i++)
for(int j = c1; j < c2; j++) {
if(cur == arr[i][j])
hp++;
else {
if(hp)
hp--;
else
cur = arr[i][j], hp = 1;
}
}
int cnt = 0;
for(int i = r1; i < r2; i++)
for(int j = c1; j < c2; j++)
cnt += arr[i][j] == cur;
if(cnt > (r2 - r1) * (c2 - c1) / 2)
cout << cur << '\n';
else
cout << "-1\n";
}
}
}
|