题目描述
难度分:$1500$
输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$,$m$之和$\leq 2 \times 10^5$。
每组数据输入$n(1 \leq n \leq 2 \times 10^5)$,$m(1 \leq m \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq n+m)$,下标从$1$开始。
然后输入$m$个修改操作,每个操作输入$p(1 \leq p \leq n)$和$v(1 \leq v \leq n+m)$,表示把$a[p]$改成$v$。修改操作是永久的。
保证初始数组,以及每次修改后的数组,都不包含重复元素。
定义如下$m+1$个数组:
$A_0=a$。
$A_1=$第一次修改后的数组$a$。
$A_2=$第二次修改后的数组$a$。
$A_m=$第$m$次修改后的数组$a$。
定义$f(i,j)$为$A_i + A_j$(这是一个长为$2n$的数组)中的不同元素个数。输出所有$f(i,j)$之和,其中$0 \leq i \lt j \leq m$。
输入样例
3
3 2
1 2 3
1 4
2 5
1 1
1
1 1
10 10
4 6 9 12 16 20 2 10 19 7
1 3
5 4
2 17
2 18
6 11
7 1
8 17
5 5
5 5
2 2
输出样例
13
1
705
算法
贡献法
答案$ans$首先一定会包括一部分$\frac{n \times (m+1) \times m}{2}$,这是每个$A_{i}+A_{j}$前一半$n$个不同的数对答案做出的贡献,$A_{0}$会跟$A_{1}$到$A_{m}$产生$m$个$n$,$A_{1}$会跟$A_{2}$到$A_m$产生$m-1$个$n$的贡献……$A_{m-1}$会跟$A_{m}$产生$1$个$n$的贡献,高斯求和就能得到。接下来考虑后一半的贡献,对于某一个版本$i$的$p$索引位置数值$v=A_i[p]$,它会跟所有在$p$位置$\neq v$的$A_j[p]$产生$1$贡献,因此我们只需要知道每个数值$val$在$[0,m]$中几个版本的数组中出现过,存入在频数表$counter$中。
对于一个位置$p$,我们记录下它的值被修改的关键点(如果没有修改不算关键点),存在$pos2pir[p]$中,$pos2pir[p]$是个二元组数组,存的二元组是(这个值是在哪个版本的$A_i$出现的,被修改成的值)。然后遍历$pos2pir$中的所有位置$i \in [1,n]$,对于固定的$i$,遍历二元组列表$pos2pir[i]$,$pos2pir[i][j].second$的出现次数应该是$pos2pir[i][j+1].first-pos2pir[i][j].first$,即从$pos2pir[i][j].first$开始一直到下一个不一样的值出现的版本$pos2pir[i][j+1].first$之前,将其累加到$counter[pos2pir[i][j].second]$上。
最后遍历一下$counter$表,对于一个数值$k$,如果它出现了$v$次,那么就有$m+1-v$个数组是没有它的,将这两部分交叉组合,可以为答案贡献$(m+1-v) \times v$。所以后一半对答案的贡献就是$\frac{\Sigma_{k}(m + 1-counter[k]) \times counter[k]}{2}$,全部累加到$ans$上就能得到最终答案。
复杂度分析
时间复杂度
预处理出$pos2pir$的时间复杂度为$O(n+m)$。遍历$pos2pir$计算答案需要遍历$n$个索引位置中的$O(m)$个关键点,所以时间复杂度还是$O(n+m)$。整个算法的时间复杂度为$O(n+m)$。
空间复杂度
空间消耗主要是$pos2pir$数组,其中存了$O(m)$个关键点,一共开了$O(n)$个索引的二元组列表,所以空间复杂度为$O(n+m)$。以及各个数值的频数统计表$counter$,在最差情况下要存$O(n+m)$个数值的频数,空间复杂度还是$O(n+m)$。因此,整个算法的额外空间复杂度为$O(n+m)$。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 200010;
int T, n, m, a[N];
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
vector<PII> pos2pir[n + 1];
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
pos2pir[i].push_back({0, a[i]});
}
for(int i = 1; i <= m; i++) {
int p, v;
scanf("%d%d", &p, &v);
if(a[p] != v) {
a[p] = v;
pos2pir[p].push_back({i, a[p]});
}
}
LL ans = n * (1LL + m) * m / 2, delta = 0;
unordered_map<int, int, custom_hash> counter;
for(int i = 1; i <= n; i++) {
int len = pos2pir[i].size();
for(int j = 0; j < len; j++) {
int start = pos2pir[i][j].first, val = pos2pir[i][j].second;
if(j < len - 1) {
int end = pos2pir[i][j + 1].first;
counter[val] += end - start;
}else {
counter[val] += m + 1 - start;
}
}
}
for(auto&[k, v]: counter) {
delta += 1LL * (m + 1 - v) * v;
}
ans += delta>>1;
printf("%lld\n", ans);
}
return 0;
}