题解：CF1684F Diverse Segments

modfish_ · 2025-01-21 22:26:04 · 题解

思路

让我们把所有相同的数单拉出来，以 t 为例，令 b_i 表示所有 t 的下标集合，即 a_{b_i}=t。

考虑枚举一个位置 b_i。找出最小的 j，满足存在 k 满足 l_k\le b_j<b_i\le r_k，即 [b_j,b_i] 被某个给出的区间包含。寻找 j 是容易的。令 mx_i=\max_{l_k\le i}r_k，那么 j 应满足 mx_{b_{j}}\ge b_i。mx 容易处理。因为 mx 单调递增，所以在枚举 i 时动态移动 j 即可。

那么显然，我们修改的区间必须包含 b_j,b_{j+1},\dots,b_{i-1} 或者 b_{j+1},b_{j+2},\dots,b_i，也就是说至少修改掉其中的 i-j 个。换句话说，选择的区间 [L,R] 满足：L\le b_j 且 R\ge b_{i-1}，或者 L\le b_{j+1} 且 R\ge b_i。这看起来令人摸不着头脑，怎么办呢？

考虑维护 f_i 表示：当 L=i 时，R 的最小值为 f_i。于是对上面的 b_j 和 b_i 进行讨论：

• 无论如何都有 R\ge b_{i-1}，因此 f_1,\dots,f_n 全局对 b_{i-1} 取 \max。

• 当 L>b_j 时，必定有 R\ge b_i。因此 f_{b_j+1},\dots,f_n 对 b_i 取 \max。

• 当 L>b_{j+1} 时，已经不合法了，令 f_{b_{j+1}+1},\dots,f_n 变为 +\infty。

所以只需要支持后缀取 \max 操作即可。容易维护。

对于每一种数都进行如上操作。最后枚举 L，答案即为 \min_{i=1}^nf_i-i+1。

时间复杂度为 O(n\log n)。复杂度瓶颈在于离散化。可以使用较快的哈希表优化至 O(n) 左右。

代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 5;

int n, m;
int a[maxn], a1[maxn];
vector<int> V[maxn];

int mx[maxn], minR[maxn];

int main(){
    int T;
    scanf("%d", &T);
    while(T --){
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; i ++){
            scanf("%d", &a[i]);
            a1[i] = a[i];
        }
        sort(a1 + 1, a1 + n + 1);
        int k = unique(a1 + 1, a1 + n + 1) - a1 - 1;
        for(int i = 1; i <= n; i ++){
            a[i] = lower_bound(a1 + 1, a1 + k + 1, a[i]) - a1;
            V[a[i]].push_back(i);
        }
        for(int i = 1; i <= m; i ++){
            int l, r;
            scanf("%d %d", &l, &r);
            mx[l] = max(mx[l], r);
        }
        for(int i = 1; i <= n; i ++) mx[i] = max(mx[i - 1], mx[i]);
        for(int i = 1; i <= k; i ++){
            int l = 0;
            for(int j = 0; j < V[i].size(); j ++){
                while(l < j && mx[V[i][l]] < V[i][j]) l ++;
                if(l == j || mx[V[i][l]] < V[i][j]) continue;
                int x = V[i][l], y = V[i][j], z = V[i][l + 1], w = V[i][j - 1];
                minR[0] = max(minR[0], w);
                minR[x + 1] = max(minR[x + 1], y);
                minR[z + 1] = n + 1;
            }
        }
        int len = n + 1;
        for(int i = 1; i <= n; i ++){
            minR[i] = max(minR[i], max(minR[i - 1], i - 1));
            if(minR[i] > n) break;
            len = min(len, minR[i] - i + 1);
        }
        printf("%d\n", len);
        for(int i = 0; i <= n; i ++) mx[i] = minR[i] = 0, V[i].clear();
    }
    return 0;
}