思路
题目即要求删除区间中的一个或多个颜色。
考虑假如枚举删除颜色 \(k\)。
那么在 \(l,r\) 中的答案为：
\[\max_{i=1}^{m+1} a_i-a_{i-1}
\]
其中 \(a_i\) 为颜色 \(k\) 在 \(l\sim r\) 中的出现位置，\(a_{0}=l,a_{m+1}=r\)。
可以分类讨论。
-
答案为 \(a_1-l\)，那么只需要维护 \(l-r\) 中位置最小的 \(k\) 即可，对于所有颜色就是所有的位置的最大值，可以使用扫描线和线段树。
-
答案为 \(r-a_m\)，那么只需要维护 \(l-r\) 中位置最大的 \(k\) 即可，对于所有颜色就是所有的位置的最小值，仍然可以使用扫描线和线段树。
-
答案为 \(a_i-a_{i-1}\)，继续使用扫描线和线段树，每一次新加数时，在上一个位置记录此子区间的答案即可。
发现线段树只需要单点赋值，区间最值。
使用 zkw 线段树就非常方便啦。
Code
#include <bits/stdc++.h>
using namespace std;
#define fro(i, x, y) for(int i = (x);i <= (y);i++)
#define pre(i, x, y) for(int i = (x);i >= (y);i--)
const int N = 10000010;
int n, m, k, a[N], las[N];
int cnt, l[N], r[N], ans[N], head[N];
struct edge { int to, nxt; } e[N];
int t[N];
inline void upd(int x, int y)
{
t[x += k] = y;
for(x >>= 1; x; x >>= 1)
t[x] = max(t[x<<1], t[x<<1|1]);
}
inline int ask(int l, int r)
{
int res = -1e9;
for(l += k - 1, r += k + 1; l ^ r ^ 1;)
{
if((l & 1) == 0) res = max(res, t[l ^ 1]);
if((r & 1) == 1) res = max(res, t[r ^ 1]);
l >>= 1, r >>= 1;
}
return res;
}
inline void fill() { memset(t, -0x3f, sizeof t), memset(las, 0, sizeof las); }
inline void ckmax(int &x, int y) { x = max(x, y); }
inline void add(int x, int y) { e[++cnt] = {y, head[x]}, head[x] = cnt; }
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m, k = 1;
fro(i, 1, n) cin >> a[i];
fro(i, 1, m) cin >> l[i] >> r[i];
while(k <= n + 1) k <<= 1;
fro(i, 1, m) add(r[i], i);
fill();
fro(i, 1, n)
{
if(las[a[i]])
upd(las[a[i]], i - las[a[i]] - 1);
las[a[i]] = i;
for(int j = head[i]; j; j = e[j].nxt)
ckmax(ans[e[j].to], ask(l[e[j].to], r[e[j].to]));
}
fill();
fro(i, 1, n)
{
if(las[a[i]]) upd(las[a[i]], -1e9);
upd(i, -i), las[a[i]] = i;
for(int j = head[i]; j; j = e[j].nxt)
ckmax(ans[e[j].to], i + ask(l[e[j].to], r[e[j].to]));
}
fill();
memset(head, 0, sizeof head), cnt = 0;
fro(i, 1, m) add(l[i], i);
pre(i, n, 1)
{
if(las[a[i]]) upd(las[a[i]], -1e9);
upd(i, i), las[a[i]] = i;
for(int j = head[i]; j; j = e[j].nxt)
ckmax(ans[e[j].to], ask(l[e[j].to], r[e[j].to]) - i);
}
fro(i, 1, m) cout << ans[i] << "\n";
return 0;
}