P9991 [Ynoi Easy Round 2023] TEST_107 题解

· · 题解

思路

题目即要求删除区间中的一个或多个颜色。

考虑假如枚举删除颜色 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。

可以分类讨论。

  1. 答案为 a_1-l，那么只需要维护 l-r 中位置最小的 k 即可，对于所有颜色就是所有的位置的最大值，可以使用扫描线和线段树。

  2. 答案为 r-a_m，那么只需要维护 l-r 中位置最大的 k 即可，对于所有颜色就是所有的位置的最小值，仍然可以使用扫描线和线段树。

  3. 答案为 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;
}