题目描述

难度分:$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;
}