为什么这个代码在我本地跑样例跑出来是
8
9
9
16
16
但是洛谷IDE ATcoder 和 Loj 判的样例都是AC??
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n, q;
int x[N], t[N], m;
struct Query {
int l, r, id;
} Q[N];
int pos[N], L[N], R[N], sz, tot;
int cnt[N], __cnt[N];
ll ans[N];
inline bool cmp(const Query &A, const Query &B) {
if (pos[A.l] == pos[B.l])
return A.r < B.r;
return pos[A.l] < pos[B.l];
}
void build() {
sz = sqrt(n);
tot = n / sz;
for (int i = 1; i <= tot; i++) {
L[i] = (i - 1) * sz + 1;
R[i] = i * sz;
}
if (R[tot] < n) {
++tot;
L[tot] = R[tot - 1] + 1;
R[tot] = n;
}
}
inline void Add(int v, ll &Ans) {
++cnt[v];
Ans = max(Ans, 1LL * cnt[v] * t[v]);
}
inline void Del(int v) {
--cnt[v];
}
int main() {
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; i++)
scanf("%d", &x[i]), t[++m] = x[i];
for (int i = 1; i <= q; i++)
scanf("%d %d", &Q[i].l, &Q[i].r), Q[i].id = i;
build();
// 对询问进行排序
for (int i = 1; i <= tot; i++)
for (int j = L[i]; j <= R[i]; j++)
pos[j] = i;
sort(Q + 1, Q + 1 + q, cmp);
// 离散化
sort(t + 1, t + 1 + m);
m = unique(t + 1, t + 1 + m) - (t + 1);
for (int i = 1; i <= n; i++)
x[i] = lower_bound(t + 1, t + 1 + m, x[i]) - t;
int l = 1, r = 0, last_block = 0, __l;
ll Ans = 0, tmp;
for (int i = 1; i <= q; i++) {
// 询问的左右端点同属于一个块则暴力扫描回答
if (pos[Q[i].l] == pos[Q[i].r]) {
for (int j = Q[i].l; j <= Q[i].r; j++)
++__cnt[x[j]];
for (int j = Q[i].l; j <= Q[i].r; j++)
ans[Q[i].id] = max(ans[Q[i].id], 1LL * t[x[j]] * __cnt[x[j]]);
for (int j = Q[i].l; j <= Q[i].r; j++)
--__cnt[x[j]];
continue;
}
// 访问到了新的块则重新初始化莫队区间
if (pos[Q[i].l] != last_block) {
while (r > R[pos[Q[i].l]])
Del(x[r]), --r;
while (l < R[pos[Q[i].l]] + 1)
Del(x[l]), ++l;
Ans = 0;
last_block = pos[Q[i].l];
}
// 扩展右端点
while (r < Q[i].r)
++r, Add(x[r], Ans);
__l = l;
tmp = Ans;
// 扩展左端点
while (__l > Q[i].l)
--__l, Add(x[__l], tmp);
ans[Q[i].id] = tmp;
// 回滚
while (__l < l)
Del(x[__l]), ++__l;
}
for (int i = 1; i <= q; i++)
printf("%lld\n", ans[i]);
return 0;
}