题意

You are given an array a consisting of n elements, and q queries. There are two types of queries, as follow:

  • “1 p v” – An update query asks to change the value at position p in array a to v.
  • “2” – A query asks to print the minimum number of required operations to convert array a to a zero array.

A zero array is defined as an array which all its elements are zeros. There is only one allowed operation to convert an array to a zero array. At each operation, you can choose a value x and subtract it from all non-zero elements in the array, such that no element will be negative after the operation.

输入格式

The first line contains an integer T (1 ≤ T ≤ 100), in which T is the number of test cases.

The first line of each test case consists of two integers n and q (1 ≤ n, q ≤ 10^5), in which n is the size of the array a, and q is the number of queries.

Then a line follows containing n elements a1, a2, …, an (0 ≤ ai ≤ 10^9), giving the array a.

Then q lines follow, each line containing a query in the format described in the problem statement. It is guaranteed that the following constraints hold for the first type of queries: 1 ≤ p ≤ n, 0 ≤ v ≤ 10^9.

The sum of n and q overall test cases does not exceed 10^6 for each.

输出格式

For each query of the second type, print the minimum number of required operations to convert array a to a zero array. The queries must be answered in the order given in the input.

样例1

Input Output
1
5 5
3 2 1 5 4
1 2 3
2
1 3 2
1 4 1
2		 4
4

思路

这个题的难点（个人理解），在对p位置的数进行更新的时候，还实时记录新数组有几个不同的数（非零的）
题比较好理解（纯英文题面有点长 ），把问题分解一下
1.利用a[]数组来记录存进去的数，下标i来记录位置信息，对p位置的数进行更新也要用到这个数组
2.利用map函数，来记录每个数出现的频率，对于第一次出现的数，就代表着来了个新数。
下面附上代码。
————————————————
版权声明：本文为CSDN博主「佐鼬Jun」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_54699118/article/details/114945453

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5+1e5;

map<int, int> mp;
int a[N];

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        mp.clear(); // 格式化，避免下一个测试数据出问题
        int n, q;
        scanf("%d%d", &n, &q);
        int cnt = 0; // 用来标记有几个不同的数的（不包括0），因为题意是问把某个数变成0，所以0不考虑
        for (int i = 1; i <= n; i++) {
            int num;
            scanf("%d", &num);
            a[i] = num;
            if (num && mp[num]==0) // 如果这个数第一次出现，说明输入了一个新的数，所以conut+1
                cnt++;
            mp[num]++; // 用mp来储存该数出现的次数
        }
        while (q--) {
            int x;
            scanf("%d", &x);
            if (x == 1) {
                int p, v;
                scanf("%d%d", &p, &v); // 把第p个数，变成v
                int y = a[p]; // 先把第p个数记下来（这个数是还没改动之前的） ，记下来是为了下面，删掉时，这个数对应出现的次数-1
                if (v && mp[v]==0) // 如果新加的数，是之前没出现过的，就count+1，出现过的话，就没必要了
                    cnt++;
                mp[v]++; // v这个数出现次数+1
                a[p] = v; // 更新p位置的数为v
                mp[y]--; // 这是把之前那个旧的数，删掉
                if (y && mp[y]==0) // 如果旧的那个数完全没了，说明有个种类的数完全没了，conut-1
                    cnt--;
            }
            else {
                printf("%d\n", cnt); // count就是要输出的答案，即有几个不同的数（非零）
            }
        }
    }
    return 0;
}