考虑分块: 记(Ans[i][j]) 表示第i到第j块的答案, (cnt[i][j])表示第(j)种颜色的块前缀和.
那么就可以直接处理了, (Ans[i][j])可以通过扫描一整个块来处理, 查询的时候直接先询问大块答案, 然后小块扫描.
因为大块里面的答案它不会受到小块的影响, 而大块里面的答案小块探测不到, 所以这样做反而是可以的.
考虑分块的一般思想:块之间要支持下列操作,
- 快速合并信息
- 记住相应的信息.
这就要求信息要么是可以直接利用的答案, 要么是可以快速维护和计算的信息.
如果要有修改操作, 要么要兹词快速重构块,还可以兹词快速打标记, 想题目就可以向这一方面考虑.
Code
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(s) debug("The massage in line %d, Function %s: %s
", __LINE__, __FUNCTION__, s)
typedef long long LL;
typedef long double LD;
const int BUF_SIZE = (int)2e6 + 10;
struct fastIO {
char buf[BUF_SIZE], buf1[BUF_SIZE]; int cur, cur1; FILE *in, *out;
fastIO() { cur = BUF_SIZE, in = stdin, out = stdout; cur1 = 0; }
inline char getchar() { if(cur == BUF_SIZE) fread(buf, BUF_SIZE, 1, in), cur = 0; return *(buf + (cur++)); }
inline void putchar(char ch) { *(buf1 + (cur1++)) = ch; if (cur1 == BUF_SIZE) fwrite(buf1, BUF_SIZE, 1, out), cur1 = 0; }
inline void flush() { if (cur1 > 0) fwrite(buf1, cur1, 1, out); cur1 = 0; }
}IO;
LL read() {
char ch = IO.getchar();
LL x = 0, flag = 1;
for(;!isdigit(ch); ch = IO.getchar()) if(ch == '-') flag *= -1;
for(;isdigit(ch); ch = IO.getchar()) x = x * 10 + ch - 48;
return x * flag;
}
void write(LL x) {
if(x < 0) x = -x, IO.putchar('-');
if(x >= 10) write(x / 10);
IO.putchar(x % 10 + 48);
}
const int Maxn = 1e5 + 9, Maxb = 209;
int n, q, a[Maxn], Temp[Maxn], len;
namespace Bl {
int Block[Maxn], Begin[Maxn], End[Maxn], cnt[Maxb][Maxn], Lim, tot, tmp[Maxn];
LL ans[Maxb][Maxb];
void init() {
Lim = 700, tot = (n - 1) / Lim + 1;
rep (i, 1, n) {
Block[i] = (i - 1) / Lim + 1;
++cnt[Block[i]][a[i]];
}
rep (i, 1, tot) Begin[i] = End[i - 1] + 1, End[i] = End[i - 1] + Lim;
End[tot] = min(End[tot], n);
rep (i, 1, tot)
rep (j, 1, len) cnt[i][j] += cnt[i - 1][j];
rep (i, 1, tot)
rep (j, i, tot) {
ans[i][j] = ans[i][j - 1];
rep (k, Begin[j], End[j])
ans[i][j] = max(ans[i][j], 1ll * (cnt[j][a[k]] - cnt[i - 1][a[k]]) * Temp[a[k]]);
}
}
LL query(int l, int r) {
if(Block[l] == Block[r]) {
LL res = 0;
rep (i, l, r) ++tmp[a[i]];
rep (i, l, r) res = max(res, 1ll * tmp[a[i]] * Temp[a[i]]);
rep (i, l, r) --tmp[a[i]];
return res;
}
LL res = ans[Block[End[Block[l]] + 1]][Block[Begin[Block[r]] - 1]];
rep (i, l, End[Block[l]]) ++tmp[a[i]];
rep (i, Begin[Block[r]], r) ++tmp[a[i]];
rep (i, l, End[Block[l]]) res = max(res, 1ll * Temp[a[i]] * (cnt[Block[Begin[Block[r]] - 1]][a[i]] - cnt[Block[End[Block[l]] + 1] - 1][a[i]] + tmp[a[i]]));
rep (i, Begin[Block[r]], r) res = max(res, 1ll * Temp[a[i]] * (cnt[Block[Begin[Block[r]] - 1]][a[i]] - cnt[Block[End[Block[l]] + 1] - 1][a[i]] + tmp[a[i]]));
rep (i, l, End[Block[l]]) --tmp[a[i]];
rep (i, Begin[Block[r]], r) --tmp[a[i]];
return res;
}
}
void discrete() {
rep (i, 1, n) Temp[i] = a[i];
sort(Temp + 1, Temp + n + 1);
len = unique(Temp + 1, Temp + n + 1) - Temp - 1;
rep (i, 1, n) a[i] = lower_bound(Temp + 1, Temp + len + 1, a[i]) - Temp;
}
void init() {
n = read(); q = read();
rep (i, 1, n) a[i] = read();
discrete();
Bl :: init();
}
void solve() {
while(q--) {
LL l = read(), r = read();
printf("%lld
", Bl :: query(l, r));
}
}
int main() {
freopen("photo.in", "r", stdin);
freopen("photo.out", "w", stdout);
init();
solve();
#ifdef Qrsikno
debug("
Running time: %.3lf(s)
", clock() * 1.0 / CLOCKS_PER_SEC);
#endif
return 0;
}