set 与 map 家族

#include <bits/stdc++.h>
using namespace std;

int main() {
    set<int> s;
    s.insert(5);
    s.insert(3);
    s.insert(8);
    s.insert(3);          // 重复插入，被忽略
    s.insert(1);

    cout << "size = " << s.size() << "\n";   // 4

    // 方式一：范围 for（最推荐，C++11）
    for (int x : s) cout << x << " ";
    cout << "\n";                        // 1 3 5 8

    // 方式二：迭代器（要删除元素时只能用这种）
    for (auto it = s.begin(); it != s.end(); ++it)
        cout << *it << " ";
    cout << "\n";

    // 方式三：反向迭代器，从大到小
    for (auto it = s.rbegin(); it != s.rend(); ++it)
        cout << *it << " ";
    cout << "\n";                        // 8 5 3 1

    cout << "min = " << *s.begin() << ", max = " << *s.rbegin() << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    set<int> s = {2, 4, 6, 8, 10};

    // ① insert 的返回值：判断是不是新元素
    auto r1 = s.insert(6);    // 已存在
    auto r2 = s.insert(7);    // 新元素
    cout << "insert(6) 成功? " << r1.second
         << ", insert(7) 成功? " << r2.second << "\n";

    // ② count：判断存在性（最简洁）
    cout << "count(4) = " << s.count(4) << "\n";   // 1
    cout << "count(5) = " << s.count(5) << "\n";   // 0

    // ③ find：拿到迭代器才能取「前驱 / 后继」
    auto it = s.find(6);
    if (it != s.end()) {
        cout << "找到 " << *it;
        if (it != s.begin()) { auto p = it; --p; cout << "，前驱 = " << *p; }
        auto nx = it; ++nx;
        if (nx != s.end()) cout << "，后继 = " << *nx;
        cout << "\n";
    }

    // ④ lower_bound / upper_bound
    cout << "lower_bound(6) = " << *s.lower_bound(6) << "\n";  // 6
    cout << "upper_bound(6) = " << *s.upper_bound(6) << "\n";  // 7
    cout << "lower_bound(5) = " << *s.lower_bound(5) << "\n";  // 6

    // ⑤ erase 迭代器：O(1)，且返回下一个位置
    s.erase(s.find(6));

    // ⑥ erase 值：删除所有等于该值的元素
    s.erase(8);

    for (int x : s) cout << x << " ";
    cout << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

void show(multiset<int>& ms, string name) {
    cout << name << " : ";
    for (int x : ms) cout << x << " ";
    cout << " (size=" << ms.size() << ")\n";
}

int main() {
    multiset<int> ms = {1, 2, 2, 2, 3};
    show(ms, "初始");

    // 正确做法：删一个 2
    ms.erase(ms.find(2));
    show(ms, "erase(find(2)) 之后");

    // 危险做法：删所有 2
    ms.erase(2);
    show(ms, "erase(2) 之后");

    // count 在 multiset 里返回真实个数（这才是它该用的地方）
    ms.insert(9); ms.insert(9); ms.insert(9);
    cout << "count(9) = " << ms.count(9) << "\n";   // 3
    show(ms, "插入三个 9 之后");

    // 范围遍历：一次拿到所有等于 9 的元素
    auto rg = ms.equal_range(9);
    for (auto it = rg.first; it != rg.second; ++it) cout << *it << " ";
    cout << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    map<string, int> score;
    score["Alice"] = 95;
    score["Bob"]   = 88;
    cout << "size = " << score.size() << "\n";      // 2

    // ❌ 危险：只是想查一下 Carol 有没有分数
    if (score["Carol"] > 0) { /* ... */ }
    cout << "危险写法后 size = " << score.size() << "\n";  // 3！Carol 被凭空插入了

    // ✅ 正确：用 count 判断存在性
    cout << "count(\"Dave\") = " << score.count("Dave") << "\n";
    cout << "安全写法后 size = " << score.size() << "\n";  // 仍然是 3

    // 遍历时注意：it->first 是键，it->second 是值
    for (auto& kv : score)
        cout << kv.first << " -> " << kv.second << "\n";

    // 删除：erase(键) 和 erase(迭代器) 在 map 里等价（键唯一）
    score.erase("Carol");
    cout << "删除 Carol 后 size = " << score.size() << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    map<long long, int> cnt;      // 值 -> 出现次数
    for (int i = 0; i < n; i++) {
        long long x; cin >> x;
        cnt[x]++;                    // 一行完成「建键 + 计数」
    }

    // 自动按值升序输出（因为 map 按键有序）
    for (auto& kv : cnt)
        cout << kv.first << " 出现 " << kv.second << " 次\n";

    // 离散化：把大值域映射成 1..m 的小编号
    int id = 0;
    map<long long, int> disc;
    for (auto& kv : cnt) disc[kv.first] = ++id;

    cout << "离散化后：\n";
    for (auto& kv : disc)
        cout << "值 " << kv.first << " -> 编号 " << kv.second << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    multimap<string, int> mm;            // 姓名 -> 成绩（可以重名）
    mm.insert({"Zhang", 92});
    mm.insert({"Li",    85});
    mm.insert({"Zhang", 78});      // 又一个 Zhang
    mm.insert({"Wang",  90});
    mm.insert({"Zhang", 100});

    // 所有同名的人会被排在一起，且内部按插入顺序稳定排列
    for (auto& kv : mm)
        cout << kv.first << " : " << kv.second << "\n";

    // 取某个键的全部值：equal_range 返回 [first, second)
    cout << "--- 查 Zhang 的所有成绩 ---\n";
    auto rg = mm.equal_range("Zhang");
    int sum = 0, k = 0;
    for (auto it = rg.first; it != rg.second; ++it) {
        cout << it->second << " ";
        sum += it->second; k++;
    }
    cout << "\n共 " << k << " 人，平均 " << sum / k << " 分\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    set<string> roll;                 // 初始名单
    for (int i = 0; i < n; i++) {
        string name; cin >> name;
        roll.insert(name);
    }

    set<string> called;               // 记录已经被点到过的名字
    int m; cin >> m;
    while (m--) {
        string name; cin >> name;
        if (!roll.count(name)) {           // ① 不在名单里
            cout << "WRONG\n";
        } else if (called.count(name)) {    // ② 已点过
            cout << "REPEAT\n";
        } else {                            // ③ 首次点到
            called.insert(name);
            cout << "OK\n";
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int a[105];

int main() {
    int n; cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    sort(a, a + n);                        // 第一步：排序
    int m = unique(a, a + n) - a;          // 第二步：把相邻重复项挤到末尾

    cout << m << "\n";
    for (int i = 0; i < m; i++) cout << a[i] << " ";
    cout << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    set<int> s;                       // 一步到位：有序 + 去重
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        s.insert(x);                   // 重复的自动被丢弃
    }
    cout << s.size() << "\n";
    for (int x : s) cout << x << " ";   // 遍历即升序
    cout << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    map<string, int> cnt;

    for (int i = 0; i < n; i++) {
        string w; cin >> w;
        cnt[w]++;                         // 一行完成建键 + 计数
    }

    // map 已按键升序，顺序遍历即为字典序
    for (auto& kv : cnt) {
        if (kv.second >= 2)
            cout << kv.first << " " << kv.second << "\n";
    }

    // 顺便求出现最多的单词（众数）
    string best; int mx = 0;
    for (auto& kv : cnt)
        if (kv.second > mx) { mx = kv.second; best = kv.first; }
    cout << "最高频：" << best << " (" << mx << " 次)\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int q; cin >> q;
    multiset<long long> ms;

    while (q--) {
        int op; cin >> op;
        if (op == 1) {
            long long x; cin >> x;
            ms.insert(x);                          // O(log n)
        } else if (op == 2) {
            long long x; cin >> x;
            auto it = ms.find(x);
            if (it != ms.end()) ms.erase(it);      // ★ 只删一个，绝不能写 ms.erase(x)
        } else {
            long long mn = *ms.begin();             // 最小值，O(1)
            long long mx = *ms.rbegin();            // 最大值，O(1)
            cout << mx - mn << "\n";
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    set<int> s;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        s.insert(x);                  // 自动去重 + 自动排序
    }
    cout << s.size() << endl;
    bool first = true;
    for (int x : s) {
        if (!first) cout << " ";
        cout << x; first = false;
    }
    cout << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;
    map<int, long long>    sumStu;   // 学号 -> 总分
    map<string, long long> sumCou;   // 课程名 -> 总分
    map<string, int>       bestCou;  // 课程名 -> 最高分

    for (int i = 0; i < n * m; i++) {
        int id, sc; string cou;
        cin >> id >> cou >> sc;
        sumStu[id] += sc;                 // 计数型用法，[] 是安全的
        sumCou[cou] += sc;
        bestCou[cou] = max(bestCou[cou], sc);
    }

    // ① 按学号升序（map 已排好）
    for (auto& kv : sumStu)
        cout << kv.first << " " << kv.second << "\n";

    cout << "\n";

    // ② 按课程名字典序输出平均分
    for (auto& kv : sumCou) {
        cout << kv.first << " "
             << fixed << setprecision(1)
             << (double)kv.second / n << "\n";
    }

    // ③ 找最高分课程（并列取字典序最小，因为遍历是有序的，用 > 即可）
    string bestName; int bestVal = -1;
    for (auto& kv : bestCou)
        if (kv.second > bestVal) { bestVal = kv.second; bestName = kv.first; }

    cout << "最高：" << bestName << " " << bestVal << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
long long a[MAXN];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    map<long long, int> cnt;   // 值 -> 在当前窗口内的出现次数
    int distinct = 0;             // 当前窗口内不同值的个数

    for (int i = 1; i <= n; i++) {
        // 右端点进入窗口
        if (cnt[a[i]]++ == 0) distinct++;

        // 窗口已满 k 个，输出答案，然后收缩左端点
        if (i >= k) {
            cout << distinct << " ";
            int lv = a[i - k + 1];
            if (--cnt[lv] == 0) distinct--;
        }
    }
    cout << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

// ============ 一、set 模板 ============
void setTemplate() {
    set<int> s;
    s.insert(5);                       // O(log n)
    s.erase(5);                          // 删所有 5（set 中最多 1 个）
    s.erase(s.find(5));                 // 删迭代器指向的那个
    bool has = s.count(5) > 0;         // 存在性
    auto it = s.lower_bound(5);         // 第一个 >= 5
    auto it2 = s.upper_bound(5);        // 第一个 > 5
    if (it2 != s.begin()) { auto p = it2; --p; /* p 指向 <= 5 的最大值 */ }
    if (!s.empty()) { int mn = *s.begin(), mx = *s.rbegin(); }
    for (int x : s) { /* 升序 */ }
}

// ============ 二、multiset 模板（重点在删除）============
void multisetTemplate() {
    multiset<int> ms;
    ms.insert(2); ms.insert(2); ms.insert(2);
    cout << ms.count(2);                // 3，真实个数
    auto it = ms.find(2);
    if (it != ms.end()) ms.erase(it);    // ✅ 只删一个
    // ms.erase(2);                      // ❌ 三个全删
    auto rg = ms.equal_range(2);          // 一次拿到所有 2
}

// ============ 三、map 模板 ============
void mapTemplate() {
    map<string, int> cnt;
    cnt["apple"]++;                     // ✅ 计数场景放心用
    if (cnt.count("pear")) { }          // ✅ 只读查询用 count
    auto it = cnt.find("pear");
    if (it != cnt.end()) cout << it->second;
    for (auto& kv : cnt) { /* kv.first 键，kv.second 值，按键升序 */ }
    cnt.erase("apple");                    // 键唯一，删一个就是删全部

    // 离散化：大值域 -> 1..m 编号
    map<long long, int> disc;
    int id = 0;
    for (auto& kv : cnt) disc[kv.first] = ++id;
}

// ============ 四、multimap 模板 ============
void multimapTemplate() {
    multimap<string, int> mm;
    mm.insert({"Zhang", 90});
    mm.insert({"Zhang", 80});
    auto rg = mm.equal_range("Zhang");
    for (auto it = rg.first; it != rg.second; ++it)
        cout << it->second << " ";
}

// ============ 五、自定义排序（set 存结构体）============
struct Node { int x, y; };
struct Cmp { bool operator()(const Node& a, const Node& b) const {
    return a.x != b.x ? a.x < b.x : a.y < b.y;   // 严格弱序！
} };
// set<Node, Cmp> ns;

#include <bits/stdc++.h>
using namespace std;

multiset<long long> lo, hi;   // lo 是较小的一半，hi 是较大的一半

void add(long long x) {
    if (lo.empty() || x <= *lo.rbegin()) lo.insert(x);
    else hi.insert(x);

    // 让 |lo.size() - hi.size()| <= 1，且 lo 不少于 hi
    while (lo.size() > hi.size() + 1) {
        auto it = prev(lo.end());      // lo 的最大值
        long long v = *it;
        lo.erase(it);
        hi.insert(v);
    }
    while (hi.size() > lo.size()) {
        auto it = hi.begin();          // hi 的最小值
        long long v = *it;
        hi.erase(it);
        lo.insert(v);
    }
}

long long median() { return *lo.rbegin(); }

int main() {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        long long x; cin >> x;
        add(x);
        cout << median() << " ";
    }
    cout << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    set<long long> s;
    for (int i = 0; i < n; i++) {
        long long x; cin >> x;

        if (i == 0) { s.insert(x); cout << 0 << " "; continue; }

        long long best = LLONG_MAX;

        // 后继：第一个 >= x 的数
        auto up = s.lower_bound(x);
        if (up != s.end()) best = min(best, *up - x);

        // 前驱：第一个 <= x 的数（用 upper_bound 再回退一步）
        auto low = s.upper_bound(x);
        if (low != s.begin()) { --low; best = min(best, x - *low); }

        if (s.count(x)) best = 0;    // 已经出现过相同的数

        s.insert(x);
        cout << best << " ";
    }
    cout << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    string t; cin >> t;
    map<int, long long> cnt;
    cnt[0] = 1;             // 空前缀和出现过 1 次

    int s = 0; long long ans = 0;
    for (char c : t) {
        s += (c == '1') ? 1 : -1;
        ans += cnt[s];            // 之前出现过几次 s，就有几个合法子串
        cnt[s]++;                 // 计数场景，[] 安全
    }
    cout << ans << "\n";          // 注意 ans 会超 int，用 long long
    return 0;
}