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

柿子饼同学

问题描述

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


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


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


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

#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[N];

// 离散化
int toid[N];
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[5];
} t[N << 2];

void Up(Node & rt, Node & a, Node & b){
    for(int i = 0; i < 5; i++){
        rt.s[i] = a.s[i] + 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[u].s[1] += (ll)v*(ll)toid[L];
        t[u].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[u], t[lc], t[rc]);
}

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[0] != 's'){
            cin >> x;
            toid[++cnt] = x;
            if(s[0] == 'a') Q[i].type = 1;
            else Q[i].type = 2;
            Q[i].x = x;
            continue;
        }
        Q[i].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[i].type == 1){
            Modify(1, 1, cnt, id(Q[i].x), 1);
        }
        else if(Q[i].type == 2){
            Modify(1, 1, cnt, id(Q[i].x), -1);
        }
        else{
            cout << t[1].s[3] << '\n';
        }
    }

    return 0;
}

FishC

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

### 问题梳理：

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[i] = {3, 0};
        } else {
            cin >> x;
            toid.push_back(x);
            if (op == "add") {
                Q[i] = {1, x};
            } else if (op == "del") {
                Q[i] = {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[num];
                }
                ++idx;
            }
            cout << sum << endl;
        }
    }
    return 0;
}

### 代码解析：

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

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

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

某一个“天”

这麽好的东西必须支持