P12568 An Array and Range Additions 题解

· · 题解

P12568 [UOI 2023] An Array and Range Additions

题目大意：

给定一个长度为 n 的整数数组 a。每次操作可以选择一个区间加上任意整数。求使数组 a 中所有元素两两不同的最小操作次数。

首先我们先考虑本题的弱化版本：你需要保证 选择的区间两两不交。

这时问题变成了一个简单的贪心。我们从左至右扫描整个序列，每次遇到一个重复的数字，就把序列从这里断开，然后新开一段。最后，我们保留第一段不变，后面每一段加上一个互不相同的数字。容易证明最优性。

如果区间可以重叠呢？我们先钦定 序列中的所有数字必须至少改变一次，考虑如下 n=3 的情形：

1 1 1

容易发现如下的操作方案：

x+1 x+y+1 y+1

其中 x 远大于 a_i，y 远大于 x。

考虑如下 n=5 的情形：

1 1 1 1 1

下面是一种合理的操作方案：

x+1 x+y+1 x+y+z+1 y+z+1 z+1

其中 x 远大于 a_i，y 远大于 x，z 远大于 y。

由此推广，我们可以得到如下一般结论：

现在考虑更一般的情形。我们可能会面对答案由若干段的改变构成的情况。下面是一个例子。

原序列 1 1 3 2 2 1 2 3 3
答案序列 1 x+1 x+3 x+2 2 y+1 y+2 y+3 3

这样的答案很难求解。但我们发现：我们可以把两个相邻的两个操作区间合并，如下所示：

原序列 1 1 3 2 2 1 2 3 3
新答案序列 1 x+1 x+3 x+2 x+y+2 y+1 y+2 y+3 3

把中间的无关数字也“带上”操作，容易发现这样的构造也符合要求。于是存在一种合法的构造方案，只有最前面和最后面的一些位置不改变，中间的数字都要改变。

回到本题。我们首先预处理出 每一个点右侧第一次出现重复数字的位置，记为 nxt_i。容易以线性对数的复杂度求出。

然后，我们对于每一个合法的前缀 [1,l]，找出一个极长的合法后缀 [r,n]。这可以双指针动态维护，总情况数不超过 n。我们令这些数字不变。

剩下的就只有求出 [l+1,r-1] 中的最少操作数。这转化为上面 序列中的所有数字必须至少改变一次 的情况。由于我们已经求出了 nxt 数组，我们可以从 l+1 开始，在 nxt 上暴力往后跳直至超过 r-1，这样单次查询复杂度是 \mathcal O(n) 的。

而上面的跳跃操作是可以倍增优化的，于是我们可以在 \mathcal O(n\log n) 的时间复杂度内求出每对前后缀的答案。把所有情况的答案取最小值即可。

注意特判不需要操作的情形。

AC 代码：

int n, a[maxn], cnt;
int nxt[maxn][20], ans = 0x3f3f3f3f;
map<int, int> mp;
int query(int l, int r) {
    int res = 1;
    for (int j = 19; j >= 0; j--) {
        if (nxt[l][j] <= r) l = nxt[l][j], res += (1 << j);
    }
    return res / 2 + 1;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    nxt[n + 1][0] = n + 1;
    for (int i = n; i >= 1; i--) {
        nxt[i][0] = nxt[i + 1][0];
        if (mp[a[i]]) nxt[i][0] = min(nxt[i][0], mp[a[i]]);
        mp[a[i]] = i;
    }
    for (int i = 1; i <= 19; i++) {
        for (int j = 1; j <= n + 1; j++) 
            nxt[j][i] = nxt[nxt[j][i - 1]][i - 1];
    }
    mp.clear(); int l, r;
    for (r = n; r >= 1; r--) {
        if (!mp[a[r]]) mp[a[r]]++;
        else break;
    }
    if (!r) return 0 * puts("0");
    ans = min(ans, query(1, r)); r++;
    for (l = 1; l <= n; l++) {
        while (mp[a[l]] && r <= n) {
            mp[a[r]]--; r++;
        }
        if (mp[a[l]]) break;
        mp[a[l]] = 1;
        ans = min(ans, query(l + 1, r - 1));
    }
    printf("%d", ans);
    return 0;
}