除了几个TLE的,剩下的都是RE。
#include <bits/stdc++.h>
using namespace std;
map <int, int> mp, mp2;
int cnt_mp;
vector <int> v;
int sum[205][40005], zs[205][40005], a[40005], tong[40005];
// sum[i][j] 第i个块编号j的前缀和 zs[i][j] 第i个块到第j个块的众数
int main() {
//freopen("P4168_1.in", "r", stdin);
//freopen("P4168_1.out", "w", stdout);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (!mp[a[i]]) {
mp[a[i]] = ++cnt_mp;
mp2[cnt_mp] = a[i];
}
//v[mp[a[i]]].push_back(i);
}
for (int i = 1; i <= 200; i++) {
for (int j = 1; j <= 40000; j++) sum[i][j] = sum[i - 1][j];
for (int j = (i-1) * 200 + 1; j <= i * 200; j++) sum[i][mp[a[j]]] ++;
}
for (int i = 1; i <= 200; i++)
for (int j = i + 1; j <= 200; j++) {
int maxx = zs[i][j - 1];
for (int k = (j-1)*200 + 1; k <= 200 * j; k++)
if ((sum[j][a[k]]-sum[i - 1][a[k]] > sum[j][maxx]-sum[i - 1][maxx]) || (sum[j][a[k]]-sum[i-1][a[k]] == sum[j][maxx]-sum[i-1][maxx] && a[k] < maxx))
maxx = a[k];
zs[i][j] = maxx;
}
for (int i = 1; i <= m; i++) {
int l, r;
cin >> l >> r;
int kl = (l/200 + 1), kr = (r/200 + 1);
if (kr - kl <= 1) {
int maxx = 0;
memset(tong, 0, sizeof(tong));
for (int j = l; j <= r; j++) {
if ((++tong[mp[a[j]]] > tong[maxx]) || (tong[mp[a[j]]] == tong[maxx] && a[j] < maxx)) maxx = j;
}
cout << a[maxx] << "\n";
} else {
memset(tong, 0, sizeof(tong));
v.clear();
int maxx = 0;
for (int i = l; i <= (kl + 1) * 200; i++) {
if (!tong[mp[a[i]]]) v.push_back(mp[a[i]]);//
tong[mp[a[i]]] ++;
}
for (int i = (kr - 1)*200+1; i <= r; i++) {
if (!tong[mp[a[i]]]) v.push_back(mp[a[i]]);
tong[mp[a[i]]] ++;
}
int zhs = zs[kl+1][kr-1];
for (int i = 0; i < v.size(); i++) {
int pre = tong[v[i]] + sum[kr-1][v[i]] - sum[kl][v[i]], now = sum[kr-1][zhs] - sum[kl][zhs] + tong[zhs];
if ((pre > now) || (pre == now && mp2[v[i]] < mp2[zhs]))
zhs = mp[v[i]];
}
cout << mp2[zhs] << "\n";
}
}
return 0;
}
这个代码哪里可能会RE?QWQ?