Unique Array
题目描述
给你一个长度为 n n n 的整数数组 a a a 。 a a a 的子数组是其连续的子序列之一(即数组 [ a l , a l + 1 , … , a r ] [a_l, a_{l+1}, \dots, a_r] [al,al+1,…,ar] 中的某个整数 l l l 和 r r r 的子数组 1 ≤ l < r ≤ n 1 \le l < r \le n 1≤l<r≤n )。如果一个整数在子数组中出现的次数正好是一次,那么这个子数组就是唯一的。
您可以执行以下操作任意多次(可能为零):从数组中选择一个元素,然后用任意整数替换它。
你的任务是计算上述操作的最少次数,以使数组 a a a 的所有子数组都是唯一的。
输入描述
第一行包含一个整数 t t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1≤t≤104 ) - 测试用例数。
每个测试用例的第一行包含一个整数 n n n ( 1 ≤ n ≤ 3 ⋅ 1 0 5 1 \le n \le 3 \cdot 10^5 1≤n≤3⋅105 )。
第二行包含 n n n 个整数 a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1,a2,…,an ( 1 ≤ a i ≤ n 1 \le a_i \le n 1≤ai≤n )。
所有测试用例中 n n n 的总和不超过 3 ⋅ 1 0 5 3 \cdot 10^5 3⋅105 。
输出描述
对于每个测试用例,打印一个整数 - 为了使数组 a a 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
原题
代码
#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;
}