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
| class Solution {
public:
vector<int> subarrayMajority(vector<int>& nums,
vector<vector<int>>& queries) {
uint n = nums.size();
uint q = queries.size();
vector<int> ans(q);
auto a = nums;
ranges::sort(a);
a.erase(unique(a.begin(), a.end()), a.end());
vector<uint> index_to_value(n);
for (uint i = 0; i < n; ++i) {
index_to_value[i] = ranges::lower_bound(a, nums[i]) - a.begin();
}
uint blockSize = ceil(n / sqrt(q));
uint blockNum = (n - 1) / blockSize + 1;
vector<vector<tuple<uint, uint, uint, uint>>> blocks(blockNum);
for (uint i = 0; i < q; ++i) {
auto& _q = queries[i];
blocks[_q[0] / blockSize].emplace_back(_q[0], _q[1], _q[2], i);
}
vector<uint> cnt(a.size());
uint minx = -1, maxcnt = 0;
auto add = [&](uint j) {
uint x = nums[j];
uint c = ++cnt[index_to_value[j]];
if (c > maxcnt) {
maxcnt = c;
minx = x;
} else if (c == maxcnt) {
minx = min(minx, x);
}
};
for (int blockId = 0; blockId < blockNum; ++blockId) {
auto& block = blocks[blockId];
if (block.empty()) {
continue;
}
ranges::sort(block, {}, [](auto& ele) { return get<1>(ele); });
uint R = (blockId + 1) * blockSize;
uint _r = R;
for (auto& [l, r, threshold, i] : block) {
if (blockId == r / blockSize) {
uint prev_minx = minx, prev_maxcnt = maxcnt;
for (uint j = l; j <= r; ++j) {
add(j);
}
ans[i] = maxcnt >= threshold ? minx : -1;
minx = prev_minx, maxcnt = prev_maxcnt;
for (uint j = l; j <= r; ++j) {
--cnt[index_to_value[j]];
}
} else {
while (_r <= r) {
add(_r++);
}
uint prev_minx = minx, prev_maxcnt = maxcnt;
for (uint j = l; j < R; ++j) {
add(j);
}
ans[i] = maxcnt >= threshold ? minx : -1;
minx = prev_minx, maxcnt = prev_maxcnt;
for (uint j = l; j < R; ++j) {
--cnt[index_to_value[j]];
}
}
}
minx = -1, maxcnt = 0;
for (uint j = R; j < _r; ++j) {
--cnt[index_to_value[j]];
}
}
return ans;
}
};
|