Educational Codeforces Round 165 (Rated for Div. 2) E. Unique Array 贪心+线段树

Unique Array

题目描述

给你一个长度为 $n$ 的整数数组 $a$ 。 $a$ 的子数组是其连续的子序列之一（即数组 $[a_l,a_{l+1},\dots ,a_r]$ 中的某个整数 $l$ 和 $r$ 的子数组 $1\le l<r\le n$ ）。如果一个整数在子数组中出现的次数正好是一次，那么这个子数组就是唯一的。

您可以执行以下操作任意多次（可能为零）：从数组中选择一个元素，然后用任意整数替换它。

你的任务是计算上述操作的最少次数，以使数组 $a$ 的所有子数组都是唯一的。

输入描述

第一行包含一个整数 $t$ ( $1\le t\le 10^4$ ) - 测试用例数。

每个测试用例的第一行包含一个整数 $n$ ( $1\le n\le 3\cdot 10^5$ )。

第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$ ( $1\le a_i\le n$ )。

所有测试用例中 $n$ 的总和不超过 $3\cdot 10^5$ 。

输出描述

对于每个测试用例，打印一个整数 - 为了使数组 $a$ 的所有子数组都是唯一的，上述操作的最少次数。

样例输入

4
3
2 1 2
4
4 4 4 4
5
3 1 2 1 2
5
1 3 2 1 2

样例输出

0
2
1
0

原题

CF——传送门

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// 线段树维护idx+1到i中的每个l对应的[l,i]的总和
vector<int> tr, p; // tr为线段树数组，p为懒标记

void pushdown(int v) // 向下更新
{
    if (v * 2 + 2 >= int(tr.size()))
        return;
    // 更新子节点
    tr[v * 2 + 1] += p[v];
    tr[v * 2 + 2] += p[v];
    // 下传懒标记
    p[v * 2 + 1] += p[v];
    p[v * 2 + 2] += p[v];
    p[v] = 0; // 清空懒标记
}

void updata(int v, int l, int r, int L, int R, int x) // 区间更新
{
    if (L >= R)
        return;
    if (l == L && r == R)
    {
        tr[v] += x;
        p[v] += x; // 打上懒标记
        return;
    }
    int m = (l + r) / 2;
    pushdown(v);
    updata(v * 2 + 1, l, m, l, min(m, R), x);
    updata(v * 2 + 2, m, r, max(m, L), R, x);
    tr[v] = min(tr[v * 2 + 1], tr[v * 2 + 2]);
}

int query(int v, int l, int r, int L, int R) // 区间询问
{
    if (L >= R) // 只有一个数，则不可能为非唯一子数组
        return 1e9;
    if (l == L && r == R)
        return tr[v];
    int m = (l + r) / 2;
    pushdown(v);
    return min(
        query(v * 2 + 1, l, m, l, min(m, R)),
        query(v * 2 + 2, m, r, max(m, L), R));
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            a[i]--;
        }
        tr = vector<int>(4 * n, 0);
        p = vector<int>(4 * n, 0);
        vector<vector<int>> pos(n); // 当前某个值对应的全部位置
        int cnt = 0;                // 最少修改次数
        int idx = -1;               // 维护替换的最后一个元素的索引idx，初始化为-1
        for (int i = 0; i < n; i++)
        {
            int x = a[i];
            pos[x].push_back(i);
            int k = pos[x].size();
            if (k > 0)
                updata(0, 0, n, idx + 1, pos[x][k - 1] + 1, 1); // 当前位置向左遍历第一次出现的位置赋值为1
            if (k > 1)
                updata(0, 0, n, idx + 1, pos[x][k - 2] + 1, -2); // 当前位置向左遍历第二次出现的位置赋值为-1
            if (k > 2)
                updata(0, 0, n, idx + 1, pos[x][k - 3] + 1, 1); // 当前位置向左遍历出现第三次即以上的位置赋值为0
            if (query(0, 0, n, idx + 1, i + 1) == 0)            // 如果在这个范围内找到非唯一子数组，修改i位置，答案++
            {
                cnt++;
                idx = i;
            }
        }
        cout << cnt << '\n';
    }

    return 0;
}