设计操作:
- 区间众数。
解题思路:
我摊牌了,我看的这篇题解:https://www.cnblogs.com/acfunction/p/10051345.html
写的太好了!!
主要操作:
- \(p_{i,j}\):第 \(i\) 块到第 \(j\) 块的(最小的)众数;
- \(s_{i,j}\):类似前缀和,在前 \(i\) 个块中 \(j\)(离散化的值)出现了几次。
如何预处理:
- 对于 \(s\):直接每个块扫一遍,复杂度 \(O(n \sqrt n)\);
- 对于 \(p\):双重循环枚举 \(i,j\),开一个数组暴力统计每个数出现了多少次。复杂度 \(O(n \sqrt n)\)
88分程序(有一部分超时了):
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, blo, bl[maxn], m, // m表示不同的数值个数
s[505][maxn], // s[i][j]: 前i个块中数字j出现了几次
p[505][505], // p[i][j]: 第 [i,j] 块中最小的众数
a[maxn];
map<int, int> mp;
vector<int> vec;
inline int getid(int val) {
return lower_bound(vec.begin(), vec.end(), val) - vec.begin() + 1;
}
void _test(int a, int b) {
cout << "[^] " << a << " : " << b << endl;
}
int query(int l, int r) {
mp.clear();
if (bl[l]+1 >= bl[r]) {
int res, mx = 0;
for (int i = l; i <= r; i ++) {
int id = getid(a[i]);
int t = ++ mp[id];
if (t > mx || t == mx && id < res) {
mx = t;
res = id;
}
}
return vec[res-1];
}
else {
// 至少2个分块
for (int i = l; i <= bl[l]*blo; i ++)
mp[getid(a[i])] ++;
for (int i = (bl[r]-1)*blo+1; i <= r; i ++)
mp[getid(a[i])] ++;
int res = p[bl[l]+1][bl[r]-1], mx = mp[res] + s[bl[r]-1][res] - s[bl[l]][res];
for (auto pi : mp) {
int x = pi.first, y = pi.second;
int tmp = y + s[bl[r]-1][x] - s[bl[l]][x];
if (tmp > mx || tmp == mx && x < res) {
res = x;
mx = tmp;
}
}
return vec[res-1];
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
blo = sqrt(n);
for (int i = 1; i <= n; i ++) {
cin >> a[i];
bl[i] = (i - 1) / blo + 1;
vec.push_back(a[i]);
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
m = vec.size();
// 求 p[i][j] : 第 i 个块到第 j 个块中的最小的众数
for (int i = 1; i <= bl[n]; i ++) {
mp.clear();
int res, mx = 0;
for (int j = i; j <= bl[n]; j ++) {
for (int k = (j-1)*blo+1; k <= min(j*blo, n); k ++) {
int val = getid(a[k]);
mp[val] ++;
if (mp[val] > mx || mp[val] == mx && val < res) {
res = val;
mx = mp[val];
}
}
p[i][j] = res;
}
}
// 求 s[i][j] : 前 i 个块中数字 j(离散化后的值)出现的次数
mp.clear();
for (int i = 1; i <= bl[n]; i ++) {
for (int j = (i-1)*blo+1; j <= min(i*blo,n); j ++) {
mp[getid(a[j])] ++;
}
for (int j = 1; j <= m; j ++) s[i][j] = mp[j];
}
for (int i = 0; i < n; i ++) {
int l, r;
cin >> l >> r;
cout << query(l, r) << endl;
}
return 0;
}
然后看了一下原作者的解法,原作者只开了上述的 \(p\) 数组,没有开 \(s\) 数组,而是使用了一个 vector 数组 \(ve[i]\) 保存数值 \(i\) 对应的坐标,而后通过二分找区间范围内有多少 \(i\)。
注:这题分块大小为 \(\sqrt n\) 会超时,将分块大小调整为 \(200\) 可过本题。
100分程序:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, blo, id, a[maxn], bl[maxn], p[505][505];
map<int, int> mp;
int val[maxn], cnt[maxn];
vector<int> g[maxn];
void pre(int x) {
memset(cnt, 0, sizeof(cnt));
int res = 0, mx = 0;
for (int i = (x-1)*blo+1; i <= n; i ++) {
cnt[a[i]] ++;
int t = bl[i];
if (cnt[a[i]] > mx || cnt[a[i]] == mx && val[a[i]] < val[res]) {
res = a[i];
mx = cnt[a[i]];
}
p[x][t] = res;
}
}
int mycount(int l, int r, int x) {
return upper_bound(g[x].begin(), g[x].end(), r) - lower_bound(g[x].begin(), g[x].end(), l);
}
int query(int l, int r) {
int res = p[bl[l]+1][bl[r]-1], mx = mycount(l, r, res);
for (int i = l; i <= min(bl[l]*blo, r); i ++) {
int t = mycount(l, r, a[i]);
if (t > mx || t == mx && val[a[i]] < val[res]) {
res = a[i];
mx = t;
}
}
if (bl[l] != bl[r]) {
for (int i = (bl[r]-1)*blo+1; i <= r; i ++) {
int t = mycount(l, r, a[i]);
if (t > mx || t == mx && val[a[i]] < val[res]) {
res = a[i];
mx = t;
}
}
}
return res;
}
int main() {
ios::sync_with_stdio(0);
cin >> n;
blo = 200;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
bl[i] = (i - 1) / blo + 1;
if (!mp[a[i]]) {
mp[a[i]] = ++id;
val[id] = a[i];
}
a[i] = mp[a[i]];
g[a[i]].push_back(i);
}
for (int i = 1; i <= bl[n]; i ++)
pre(i);
for (int i = 1; i <= n; i ++) {
int l, r;
cin >> l >> r;
if (l > r) swap(l, r);
cout << val[query(l, r)] << endl;
}
return 0;
}