[心之碎片][0701] - F 集合操作
问题描述给出有序的初始为空的集合, 维护操作
add x 把 x 插入
del x 把 x 删除
sum 求所有 下标 % 5 == 2 的数字的和
操作次数 n < 1e5, x < 1e9
错误原因
思路错误
没有想到权值线段树的权值有序性, 没有思考出左边区间的变化对右边区间下标的影响
反解下标出错了
解题思路
离线, 建立权值线段树, 每个节点存 % 5 的答案和区间长
因为每个数字是唯一的, add 就是 +, del 就是 -, 答案就是根节点的 s
总结
在线题目先想离线怎么做, 一般会好些
看到想一直有序的序列, 或者数字重复次数不多, 值域大时想到权值线段树
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
// 离线操作
// 1add 2del 3sum
struct Quest{
int type, x;
} Q;
// 离散化
int toid;
int cnt;
int id(int x){
return (lower_bound(toid + 1, toid + cnt + 1, x) - toid);
}
int n;
#define lc u<<1
#define rc u<<1|1
// 区间里数字个数, 每个下标 %5 的和
struct Node{
ll siz, s;
} t;
void Up(Node & rt, Node & a, Node & b){
for(int i = 0; i < 5; i++){
rt.s = a.s + b.s[((i - a.siz) % 5 + 5) % 5];
}
rt.siz = a.siz + b.siz;
}
// +/- 一个数字在 p 位置
void Modify(int u, int L, int R, int p, int v){
if(L == p && R == p){
t.s += (ll)v*(ll)toid;
t.siz += v;
return ;
}
int mid = (L + R) >> 1;
if(p <= mid) Modify(lc, L, mid, p, v);
if(p > mid) Modify(rc, mid + 1, R, p, v);
Up(t, t, t);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
string s;
ll x;
cin >> s;
if(s != 's'){
cin >> x;
toid[++cnt] = x;
if(s == 'a') Q.type = 1;
else Q.type = 2;
Q.x = x;
continue;
}
Q.type = 3;
}
sort(toid + 1, toid + cnt + 1);
int c = unique(toid + 1, toid + cnt + 1) - toid - 1;
cnt = c;
for(int i = 1; i <= n; i++){
if(Q.type == 1){
Modify(1, 1, cnt, id(Q.x), 1);
}
else if(Q.type == 2){
Modify(1, 1, cnt, id(Q.x), -1);
}
else{
cout << t.s << '\n';
}
}
return 0;
}
好吧，这道题目确实有点复杂，不过没关系，鱼油，让我们一起来看看这道涉及集合操作的问题，看看怎么解决吧！
### 问题梳理：
1. **集合操作**：
- `add x`：将 `x` 插入集合。
- `del x`：从集合中删除 `x`。
- `sum`：求所有下标 `% 5 == 2` 的数字之和。
2. **限制条件**：
- 操作次数 `n < 1e5`（10 万次操作）。
- 数字 `x < 1e9`（十亿以内的数字）。
### 解题思路：
我们需要一个数据结构来高效地维护这些操作。由于我们需要频繁插入、删除元素以及计算特定下标的数字之和，所以可以考虑以下几种方法：
1. **基于平衡树的数据结构**（如红黑树、AVL树等）：
- 能够高效地进行插入、删除操作。
- 维持数据的有序性，方便我们计算特定下标的数据之和。
2. **离线处理与离散化**：
- 将大范围的数字通过映射压缩到小范围内，这样能有效减少空间消耗，并加快查询速度。
**具体实现步骤**：
1. **离线处理**：将所有操作记录下来，避免实时处理带来的复杂度问题。
2. **离散化**：将所有出现过的数字离散化为小范围的编号。
3. **用平衡树来维护集合**：这样我们可以高效地进行插入、删除操作，并且能够快速找到特定下标的数据。
### 代码实现：
话不多说，上代码！不过还是先给鱼油们贴几行注释：
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
struct Quest {
int type; // 1 for add, 2 for del, 3 for sum
int x;
};
vector<int> toid; // 用于离散化
vector<Quest> Q; // 存储所有操作
int id(int x) {
return lower_bound(toid.begin(), toid.end(), x) - toid.begin();
}
int main() {
int n;
cin >> n;
Q.resize(n);
for (int i = 0; i < n; ++i) {
string op;
int x;
cin >> op;
if (op == "sum") {
Q = {3, 0};
} else {
cin >> x;
toid.push_back(x);
if (op == "add") {
Q = {1, x};
} else if (op == "del") {
Q = {2, x};
}
}
}
sort(toid.begin(), toid.end());
toid.erase(unique(toid.begin(), toid.end()), toid.end());
multiset<int> ms;
for (const auto& q : Q) {
if (q.type == 1) {
ms.insert(id(q.x));
} else if (q.type == 2) {
ms.erase(ms.find(id(q.x)));
} else if (q.type == 3) {
int sum = 0;
int idx = 0;
for (const auto& num : ms) {
if (idx % 5 == 2) {
sum += toid;
}
++idx;
}
cout << sum << endl;
}
}
return 0;
}
### 代码解析：
1. **离线处理**：我们先把所有的操作读进来存入向量 `Q` 中。
2. **离散化**：将出现的所有数字存入 `toid` 向量并进行排序和去重，使得每个数字都映射到一个唯一的小范围编号。
3. **高效查询**：利用 `multiset` 来维护集合，`multiset` 能够高效处理插入和删除操作。
4. **下标计算**：遍历 `multiset`，计算所有下标 `% 5 == 2` 的数字总和。
这样，我们就能够高效地完成这道题目啦！希望这个思路和代码对你有帮助，有什么问题随时来问哈！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 这麽好的东西必须支持{:10_256:}
页:
[1]