[心之碎片][0701] - F 集合操作

柿子饼同学

问题描述

给出有序的初始为空的集合, 维护操作
add x 把 x 插入
del x 把 x 删除
sum 求所有 下标 % 5 == 2 的数字的和
操作次数 n < 1e5, x < 1e9


错误原因
思路错误
没有想到权值线段树的权值有序性, 没有思考出左边区间的变化对右边区间下标的影响
反解下标出错了


解题思路
离线, 建立权值线段树, 每个节点存 % 5 的答案和区间长
因为每个数字是唯一的, add 就是 +, del 就是 -, 答案就是根节点的 s[3]


总结
在线题目先想离线怎么做, 一般会好些
看到想一直有序的序列, 或者数字重复次数不多, 值域大时想到权值线段树

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. typedef long long ll;
   
5. const int N = 1e5 + 5;
   
6. 
   
7. // 离线操作
   
8. // 1add 2del 3sum
   
9. struct Quest{
   
10.     int type, x;
    
11. } Q[N];
    
12. 
    
13. // 离散化
    
14. int toid[N];
    
15. int cnt;
    
16. int id(int x){
    
17.     return (lower_bound(toid + 1, toid + cnt + 1, x) - toid);
    
18. }
    
19. 
    
20. int n;
    
21. 
    
22. #define lc u<<1
    
23. #define rc u<<1|1
    
24. 
    
25. // 区间里数字个数, 每个下标 %5 的和
    
26. struct Node{
    
27.     ll siz, s[5];
    
28. } t[N << 2];
    
29. 
    
30. void Up(Node & rt, Node & a, Node & b){
    
31.     for(int i = 0; i < 5; i++){
    
32.         rt.s[i] = a.s[i] + b.s[((i - a.siz) % 5 + 5) % 5];
    
33.     }
    
34.     rt.siz = a.siz + b.siz;
    
35. }
    
36. 
    
37. // +/- 一个数字在 p 位置
    
38. void Modify(int u, int L, int R, int p, int v){
    
39.     if(L == p && R == p){
    
40.         t[u].s[1] += (ll)v*(ll)toid[L];
    
41.         t[u].siz += v;
    
42.         return ;
    
43.     }
    
44. 
    
45.     int mid = (L + R) >> 1;
    
46.     if(p <= mid) Modify(lc, L, mid, p, v);
    
47.     if(p > mid) Modify(rc, mid + 1, R, p, v);
    
48.     Up(t[u], t[lc], t[rc]);
    
49. }
    
50. 
    
51. int main(){
    
52.     ios::sync_with_stdio(0);
    
53.     cin.tie(0);
    
54. 
    
55.     cin >> n;
    
56.     for(int i = 1; i <= n; i++){
    
57.         string s;
    
58.         ll x;
    
59.         cin >> s;
    
60.         if(s[0] != 's'){
    
61.             cin >> x;
    
62.             toid[++cnt] = x;
    
63.             if(s[0] == 'a') Q[i].type = 1;
    
64.             else Q[i].type = 2;
    
65.             Q[i].x = x;
    
66.             continue;
    
67.         }
    
68.         Q[i].type = 3;
    
69.     }
    
70. 
    
71.     sort(toid + 1, toid + cnt + 1);
    
72.     int c = unique(toid + 1, toid + cnt + 1) - toid - 1;
    
73.     cnt = c;
    
74. 
    
75.     for(int i = 1; i <= n; i++){
    
76.         if(Q[i].type == 1){
    
77.             Modify(1, 1, cnt, id(Q[i].x), 1);
    
78.         }
    
79.         else if(Q[i].type == 2){
    
80.             Modify(1, 1, cnt, id(Q[i].x), -1);
    
81.         }
    
82.         else{
    
83.             cout << t[1].s[3] << '\n';
    
84.         }
    
85.     }
    
86. 
    
87.     return 0;
    
88. }

复制代码

FishC

好吧，这道题目确实有点复杂，不过没关系，鱼油，让我们一起来看看这道涉及集合操作的问题，看看怎么解决吧！

### 问题梳理：

1. **集合操作**：
    - `add x`：将 `x` 插入集合。
    - `del x`：从集合中删除 `x`。
    - `sum`：求所有下标 `% 5 == 2` 的数字之和。

2. **限制条件**：
    - 操作次数 `n < 1e5`（10 万次操作）。
    - 数字 `x < 1e9`（十亿以内的数字）。

### 解题思路：

我们需要一个数据结构来高效地维护这些操作。由于我们需要频繁插入、删除元素以及计算特定下标的数字之和，所以可以考虑以下几种方法：

1. **基于平衡树的数据结构**（如红黑树、AVL树等）：
    - 能够高效地进行插入、删除操作。
    - 维持数据的有序性，方便我们计算特定下标的数据之和。

2. **离线处理与离散化**：
    - 将大范围的数字通过映射压缩到小范围内，这样能有效减少空间消耗，并加快查询速度。

**具体实现步骤**：

1. **离线处理**：将所有操作记录下来，避免实时处理带来的复杂度问题。
2. **离散化**：将所有出现过的数字离散化为小范围的编号。
3. **用平衡树来维护集合**：这样我们可以高效地进行插入、删除操作，并且能够快速找到特定下标的数据。

### 代码实现：

话不多说，上代码！不过还是先给鱼油们贴几行注释：

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. #include <set>
   
5. 
   
6. using namespace std;
   
7. 
   
8. struct Quest {
   
9.     int type; // 1 for add, 2 for del, 3 for sum
   
10.     int x;
    
11. };
    
12. 
    
13. vector<int> toid; // 用于离散化
    
14. vector<Quest> Q; // 存储所有操作
    
15. 
    
16. int id(int x) {
    
17.     return lower_bound(toid.begin(), toid.end(), x) - toid.begin();
    
18. }
    
19. 
    
20. int main() {
    
21.     int n;
    
22.     cin >> n;
    
23. 
    
24.     Q.resize(n);
    
25. 
    
26.     for (int i = 0; i < n; ++i) {
    
27.         string op;
    
28.         int x;
    
29.         cin >> op;
    
30.         if (op == "sum") {
    
31.             Q[i] = {3, 0};
    
32.         } else {
    
33.             cin >> x;
    
34.             toid.push_back(x);
    
35.             if (op == "add") {
    
36.                 Q[i] = {1, x};
    
37.             } else if (op == "del") {
    
38.                 Q[i] = {2, x};
    
39.             }
    
40.         }
    
41.     }
    
42. 
    
43.     sort(toid.begin(), toid.end());
    
44.     toid.erase(unique(toid.begin(), toid.end()), toid.end());
    
45. 
    
46.     multiset<int> ms;
    
47. 
    
48.     for (const auto& q : Q) {
    
49.         if (q.type == 1) {
    
50.             ms.insert(id(q.x));
    
51.         } else if (q.type == 2) {
    
52.             ms.erase(ms.find(id(q.x)));
    
53.         } else if (q.type == 3) {
    
54.             int sum = 0;
    
55.             int idx = 0;
    
56.             for (const auto& num : ms) {
    
57.                 if (idx % 5 == 2) {
    
58.                     sum += toid[num];
    
59.                 }
    
60.                 ++idx;
    
61.             }
    
62.             cout << sum << endl;
    
63.         }
    
64.     }
    
65.     return 0;
    
66. }

复制代码

### 代码解析：

1. **离线处理**：我们先把所有的操作读进来存入向量 `Q` 中。
2. **离散化**：将出现的所有数字存入 `toid` 向量并进行排序和去重，使得每个数字都映射到一个唯一的小范围编号。
3. **高效查询**：利用 `multiset` 来维护集合，`multiset` 能够高效处理插入和删除操作。
4. **下标计算**：遍历 `multiset`，计算所有下标 `% 5 == 2` 的数字总和。

这样，我们就能够高效地完成这道题目啦！希望这个思路和代码对你有帮助，有什么问题随时来问哈！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

某一个“天”

这麽好的东西必须支持