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

int main() {
    // 对向量排序——升序（默认）
    vector<int> v = {5, 2, 8, 1, 9, 3};
    sort(v.begin(), v.end());
    // v 现在是：{1, 2, 3, 5, 8, 9}

    for (int x : v) cout << x << " ";
    cout << "\n";

    // 降序排序
    sort(v.begin(), v.end(), greater<int>());
    // v 现在是：{9, 8, 5, 3, 2, 1}

    // 对数组排序
    int arr[] = {4, 2, 7, 1, 5};
    int n = 5;
    sort(arr, arr + n);  // 排序 arr[0..n-1]
    // arr 现在是：{1, 2, 4, 5, 7}

    return 0;
}

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

int main() {
    // 创建 pair
    pair<int, int> point = {3, 5};         // (x, y)
    pair<string, int> student = {"Alice", 95};  // (姓名, 成绩)

    // 访问元素：.first 和 .second
    cout << point.first << " " << point.second << "\n";    // 3 5
    cout << student.first << ": " << student.second << "\n"; // Alice: 95

    // pair 支持比较：先比较 .first，相同时比较 .second
    pair<int,int> a = {1, 3};
    pair<int,int> b = {1, 5};
    cout << (a < b) << "\n";   // 1（真）—— .first 相同，比较 .second：3 < 5

    // 非常常见的模式：用 pair 按第二元素排序
    vector<pair<int,int>> v = {{3,9},{1,2},{4,1},{1,5}};
    sort(v.begin(), v.end());     // 先按 .first 排序，再按 .second 排序
    // 结果：{1,2}, {1,5}, {3,9}, {4,1}

    return 0;
}

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

int main() {
    map<string, int> phoneBook;

    // 插入键值对
    phoneBook["Alice"] = 555001;
    phoneBook["Bob"] = 555002;
    phoneBook["Charlie"] = 555003;

    // 按键查找
    cout << phoneBook["Alice"] << "\n";  // 555001

    // 遍历（始终按键的**排序顺序**！）
    for (auto& entry : phoneBook) {
        cout << entry.first << " -> " << entry.second << "\n";
    }
    // 打印：
    // Alice -> 555001
    // Bob -> 555002
    // Charlie -> 555003

    // 删除键
    phoneBook.erase("Charlie");
    cout << phoneBook.size() << "\n";  // 2

    return 0;
}

map<string, int> freq;

// 危险：访问不存在的键会以值 0 创建它！
cout << freq["apple"] << "\n";  // 打印 0，但现在 "apple" 已经在 map 里了！
cout << freq.size() << "\n";    // 1——即使我们只是「查了一下」，并没有「插入」！

// 安全方式一：先检查 count
if (freq.count("apple") > 0) {
    cout << freq["apple"] << "\n";  // 安全——键已存在
}

// 安全方式二：用 .find()
auto it = freq.find("apple");
if (it != freq.end()) {          // .end() 表示「未找到」
    cout << it->second << "\n";  // it->second 是值
}

vector<string> words = {"apple", "banana", "apple", "cherry", "banana", "apple"};
map<string, int> freq;

for (const string& w : words) {
    freq[w]++;  // 如果 "w" 不存在，以 0 创建，然后递增为 1
}

// freq: apple→3, banana→2, cherry→1
for (auto& p : freq) {
    cout << p.first << " 出现了 " << p.second << " 次\n";
}

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

int main() {
    set<int> s;

    s.insert(5);
    s.insert(2);
    s.insert(8);
    s.insert(2);   // 重复——被忽略！set 仍是 {2, 5, 8}
    s.insert(1);

    // s 现在是：{1, 2, 5, 8}（自动排序，无重复）

    // 检查成员资格
    cout << s.count(2) << "\n";   // 1（存在）
    cout << s.count(7) << "\n";   // 0（不存在）

    // 删除
    s.erase(2);   // s = {1, 5, 8}

    // 遍历（始终排序）
    for (int x : s) cout << x << " ";
    cout << "\n";   // 1 5 8

    // 最小值和最大值
    cout << *s.begin() << "\n";   // 1（最小；* 解引用迭代器）
    cout << *s.rbegin() << "\n";  // 8（最大；r = 反向）

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

    return 0;
}

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

int main() {
    stack<int> st;

    st.push(1);    // [1]         （顶部在右侧）
    st.push(2);    // [1, 2]
    st.push(3);    // [1, 2, 3]

    cout << st.top() << "\n";   // 3（查看顶部，不移除）
    st.pop();                    // 移除顶部 → [1, 2]
    cout << st.top() << "\n";   // 2

    cout << st.size() << "\n";  // 2
    cout << st.empty() << "\n"; // 0（不为空）

    return 0;
}

string expr = "((a+b)*(c-d))";
stack<char> parens;
bool balanced = true;

for (char ch : expr) {
    if (ch == '(') {
        parens.push(ch);         // 开括号：压栈
    } else if (ch == ')') {
        if (parens.empty()) {    // 闭括号但没有对应的开括号
            balanced = false;
            break;
        }
        parens.pop();            // 找到匹配：弹出开括号
    }
}

if (!parens.empty()) balanced = false;  // 还有未匹配的开括号

cout << (balanced ? "匹配" : "不匹配") << "\n";

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

int main() {
    queue<int> q;

    q.push(10);   // [10]
    q.push(20);   // [10, 20]
    q.push(30);   // [10, 20, 30]

    cout << q.front() << "\n";  // 10（排在最前——最先离开）
    cout << q.back() << "\n";   // 30（排在最后——最后离开）

    q.pop();                     // 从前面移除 → [20, 30]
    cout << q.front() << "\n";  // 20

    cout << q.size() << "\n";   // 2

    return 0;
}

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

int main() {
    // 最大堆：始终给你最大值
    priority_queue<int> maxPQ;

    maxPQ.push(5);
    maxPQ.push(1);
    maxPQ.push(8);
    maxPQ.push(3);

    // 按降序弹出
    while (!maxPQ.empty()) {
        cout << maxPQ.top() << " ";  // 始终是当前最大值
        maxPQ.pop();
    }
    cout << "\n";  // 打印：8 5 3 1

    return 0;
}

// 最大堆（默认）——优先给最大值
priority_queue<int> maxPQ;

// 最小堆——优先给最小值（注意额外的模板参数！）
priority_queue<int, vector<int>, greater<int>> minPQ;

minPQ.push(5);
minPQ.push(1);
minPQ.push(8);
minPQ.push(3);

while (!minPQ.empty()) {
    cout << minPQ.top() << " ";
    minPQ.pop();
}
// 打印：1 3 5 8（最小值优先）

unordered_map<string, int> freq;
freq["apple"]++;
freq["banana"]++;
freq["apple"]++;

cout << freq["apple"] << "\n";   // 2（与 map 接口相同）

unordered_set<int> seen;
seen.insert(5);
seen.insert(10);
cout << seen.count(5) << "\n";   // 1（找到）
cout << seen.count(7) << "\n";   // 0（未找到）

vector<int> nums = {10, 20, 30, 40, 50};

// 只读遍历（复制每个元素——对 int 没问题，对 string 浪费）
for (int x : nums) {
    cout << x << " ";
}

// 引用：不复制，可修改元素
for (int& x : nums) {
    x *= 2;   // 就地翻倍每个元素
}

// const 引用：不复制，只读（大类型的最佳方式）
for (const auto& x : nums) {
    cout << x << " ";
}

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

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

    // 升序排序
    sort(v.begin(), v.end());
    // v = {1, 1, 2, 3, 4, 5, 6, 9}

    // 二分查找（只能用于**已排序**的序列！）
    cout << binary_search(v.begin(), v.end(), 5) << "\n";  // 1（找到）
    cout << binary_search(v.begin(), v.end(), 7) << "\n";  // 0（未找到）

    // lower_bound：第一个 >= 目标值的位置
    auto it = lower_bound(v.begin(), v.end(), 4);
    cout << *it << "\n";   // 4
    cout << (it - v.begin()) << "\n";  // 下标：3

    // upper_bound：第一个 > 目标值的位置
    auto it2 = upper_bound(v.begin(), v.end(), 4);
    cout << (it2 - v.begin()) << "\n";  // 下标：4（第一个 > 4 的元素）
    // [lo, hi] 范围内的元素个数：upper_bound(hi+1) - lower_bound(lo)

    // 最小值和最大值
    cout << *min_element(v.begin(), v.end()) << "\n";  // 1
    cout << *max_element(v.begin(), v.end()) << "\n";  // 9

    // 所有元素之和
    long long total = accumulate(v.begin(), v.end(), 0LL);
    cout << total << "\n";  // 31

    // 统计出现次数
    cout << count(v.begin(), v.end(), 1) << "\n";  // 2

    // 反转
    reverse(v.begin(), v.end());

    // 用一个值填充
    fill(v.begin(), v.end(), 0);  // 全为零

    return 0;
}

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // 第一步：用 map 统计词频
    map<string, int> freq;
    for (int i = 0; i < n; i++) {
        string word;
        cin >> word;
        freq[word]++;   // 如果 word 是新的，以 0 创建，然后递增
    }

    // 第二步：按字母顺序打印所有单词（map 按键有序迭代）
    cout << "所有单词：\n";
    for (auto& entry : freq) {
        // entry.first = 单词，entry.second = 计数
        cout << entry.first << ": " << entry.second << "\n";
    }

    // 第三步：找最频繁的单词
    // 对 map 用 max_element：按值（.second）比较
    auto best = max_element(
        freq.begin(),
        freq.end(),
        [](const pair<string,int>& a, const pair<string,int>& b) {
            return a.second < b.second;  // 按计数比较
        }
    );

    cout << "\n最频繁的：\"" << best->first << "\"（出现了 "
         << best->second << " 次）\n";

    return 0;
}

思路： 把 N 个整数存入集合，对每个查询检查 s.count(x)。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    set<int> s;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);
    }

    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        cout << (s.count(x) ? "YES" : "NO") << "\n";
    }

    return 0;
}

关键点：

• s.count(x) 找到时返回 1，未找到时返回 0
• while (q--) 是常见惯用法：循环执行 q 次（每次 q 递减）
• 使用 set 每次查询 O(log N)，比线性搜索 O(N) 快得多

思路： 用 map<char, int> 统计字符频率，遍历 map 自动按字母顺序输出。

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

int main() {
    string s;
    cin >> s;

    map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }

    for (auto& entry : freq) {
        cout << entry.first << ": " << entry.second << "\n";
    }

    return 0;
}

关键点：

• for (char c : s) 遍历字符串中的每个字符
• freq[c]++ 第一次访问时以值 0 创建条目，然后递增
• map 遍历始终按键有序——字符自动按字母顺序输出

思路： 把每个字符压栈，然后全部弹出——LIFO 顺序正好是倒序。

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

int main() {
    string s;
    cin >> s;

    stack<char> st;
    for (char c : s) {
        st.push(c);
    }

    while (!st.empty()) {
        cout << st.top();
        st.pop();
    }
    cout << "\n";

    return 0;
}

关键点：

• 栈的 LIFO 特性：最后压入的最先弹出 = 反转
• 访问 st.top() 或调用 st.pop() 前始终检查 !st.empty()
• 注意：reverse(s.begin(), s.end()); cout << s; 更简单——但用栈实现能理解概念

思路： 把所有名字加入队列，然后逐一弹出并打印直到队列为空。

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

int main() {
    queue<string> line;
    line.push("Alice");
    line.push("Bob");
    line.push("Charlie");
    line.push("Dave");
    line.push("Eve");

    while (!line.empty()) {
        cout << "Serving: " << line.front() << "\n";
        line.pop();
    }

    return 0;
}

关键点：

• queue.front() 不移除地访问第一个元素
• queue.pop() 移除队首元素（无返回值——如需值，在 pop() 前用 front()）
• 队列保持插入顺序——先压入的先弹出

思路： 全部压入最大堆优先队列，弹出 3 次得到最大的 3 个。

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

int main() {
    int n;
    cin >> n;

    priority_queue<int> pq;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pq.push(x);
    }

    for (int i = 0; i < 3 && !pq.empty(); i++) {
        cout << pq.top() << "\n";
        pq.pop();
    }

    return 0;
}

关键点：

• priority_queue<int> 是最大堆——top() 始终给出最大值
• 弹出 3 次按顺序得到最大的 3 个值
• && !pq.empty() 防卫处理 N < 3 的边界情况

思路： 用 unordered_set 追踪已见过的值。对每个元素，只有还没见过时才打印。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    unordered_set<int> seen;
    bool first = true;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (seen.count(x) == 0) {   // 还没见过 x
            seen.insert(x);
            if (!first) cout << " ";
            cout << x;
            first = false;
        }
    }
    cout << "\n";

    return 0;
}

关键点：

• 不能用普通 set，因为 set 会排序输出——我们要保持原始顺序
• unordered_set 提供 O(1) 均摊查找：比搜索向量快得多
• first 标志处理间隔（不打印前导/尾随空格）

思路： 用 map 统计计数，然后找最大计数。在所有出现该最大计数的单词中，取字典序最小的（map 遍历自然给出）。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    map<string, int> freq;
    for (int i = 0; i < n; i++) {
        string w;
        cin >> w;
        freq[w]++;
    }

    string bestWord;
    int bestCount = 0;

    // map 按字母顺序迭代——最先见到的达到最大计数的单词胜出
    for (auto& entry : freq) {
        if (entry.second > bestCount) {
            bestCount = entry.second;
            bestWord = entry.first;
        }
    }

    cout << bestWord << "\n";
    return 0;
}

关键点：

• 用 >（严格大于）意味着我们保留第一个达到最大计数的单词
• 由于 map 按字母顺序迭代，第一个见到的最大计数单词就是字典序最小的
• 得益于 map 的有序特性，平局处理自动完成

思路： 对每个元素 x，检查 T - x 是否已在已见元素的集合中。如果是，找到了一对。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, t;
    cin >> n >> t;

    set<int> seen;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    for (int i = 0; i < n; i++) {
        int complement = t - arr[i];  // 需要 arr[i] + complement = t
        if (seen.count(complement)) {
            // complement 在 arr[i] 之前，按顺序打印：complement arr[i]
            cout << complement << " " << arr[i] << "\n";
        }
        seen.insert(arr[i]);
    }

    return 0;
}

关键点：

• 对每个元素 x，需要的「补数」是 T - x
• 如果补数已在「已见」集合中，它在数组前面出现 → 有效的对
• 这是用 set 的 O(N log N)（或用 unordered_set 的 O(N)），优于暴力 O(N²)
• 先打印 complement（它在输入中较早），再打印 arr[i]

思路： 用栈。压入开括号；见到闭括号时，检查栈顶是否是对应的开括号。

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

int main() {
    string s;
    cin >> s;

    stack<char> st;
    bool ok = true;

    for (char ch : s) {
        if (ch == '(' || ch == '[' || ch == '{') {
            st.push(ch);    // 开括号：压栈
        } else {
            // 闭括号
            if (st.empty()) {
                ok = false;  // 没有对应的开括号
                break;
            }
            char top = st.top();
            st.pop();

            // 检查是否匹配
            if ((ch == ')' && top != '(') ||
                (ch == ']' && top != '[') ||
                (ch == '}' && top != '{')) {
                ok = false;
                break;
            }
        }
    }

    if (!st.empty()) ok = false;  // 还有未匹配的开括号

    cout << (ok ? "YES" : "NO") << "\n";
    return 0;
}

关键点：

• 核心思路：最近打开的括号必须是下一个关闭的
• 栈的 LIFO 特性完美模拟了「最近打开」的要求
• 三种失败条件：(1) 空栈时遇到闭括号；(2) 括号类型不匹配；(3) 末尾还有未关闭的括号

思路： 全部压入最大堆，弹出 K 次。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    priority_queue<int> pq;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pq.push(x);
    }

    for (int i = 0; i < k && !pq.empty(); i++) {
        cout << pq.top() << "\n";
        pq.pop();
    }

    return 0;
}

关键点：

• 优先队列自动把最大值放在顶部
• 每次 pop() 移除当前最大值，下一个最大值浮现
• 替代方案：降序排序后取前 K 个——结果相同

思路： 用 map<string, long long> 作为库存，解析每条命令并相应更新。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int m;
    cin >> m;

    map<string, long long> inventory;

    while (m--) {
        string cmd;
        cin >> cmd;

        if (cmd == "ADD") {
            string name;
            long long qty;
            cin >> name >> qty;
            inventory[name] += qty;
        } else if (cmd == "REMOVE") {
            string name;
            long long qty;
            cin >> name >> qty;
            inventory[name] -= qty;
            if (inventory[name] < 0) inventory[name] = 0;
        } else {  // QUERY
            string name;
            cin >> name;
            // 用 count 检查存在性，避免为缺失的商品创建条目
            if (inventory.count(name)) {
                cout << inventory[name] << "\n";
            } else {
                cout << 0 << "\n";
            }
        }
    }

    return 0;
}

关键点：

• inventory[name] += qty——若 name 不存在，以 0 创建后加 qty（正确！）
• QUERY 时用 inventory.count(name) 检查存在性，避免悄悄创建值为 0 的条目
• 数量用 long long 以防较大

思路： 用 deque（双端队列）维护一个有用下标的窗口。双端队列按值的递减顺序存储下标——deque.front() 始终是当前窗口最大值的下标。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    deque<int> dq;  // 存储下标，队首 = 当前最大值的下标

    for (int i = 0; i < n; i++) {
        // 移除已超出当前窗口的下标
        while (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }

        // 从队尾移除值小于 arr[i] 的下标
        //（只要 arr[i] 还在窗口里，它们就不可能成为最大值）
        while (!dq.empty() && arr[dq.back()] <= arr[i]) {
            dq.pop_back();
        }

        dq.push_back(i);

        // 从窗口满的位置（下标 k-1）开始打印最大值
        if (i >= k - 1) {
            cout << arr[dq.front()] << "\n";
        }
    }

    return 0;
}

关键点：

• 双端队列维护「单调递减队列」的下标
• 队首 = 当前窗口最大值的下标
• 加入新元素 arr[i] 时：从队尾移除所有 ≤ arr[i] 的元素（它们无用——arr[i] 更大且在窗口中待的时间更长）
• 当该下标不再在窗口内时（下标 < i - k + 1），从队首移除
• 总计 O(N)——每个下标最多压入和弹出各一次

思路： 对位置排序，对每个查询用 lower_bound 和 upper_bound 在 O(log N) 内找出范围内的数量。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    vector<int> pos(n);
    for (int i = 0; i < n; i++) cin >> pos[i];

    sort(pos.begin(), pos.end());  // 二分查找前必须排序

    while (q--) {
        int l, r;
        cin >> l >> r;

        // lower_bound(l)：第一个 >= l 的位置
        // upper_bound(r)：第一个 > r 的位置
        // [l, r] 内的元素个数 = 这两个迭代器之间的距离
        auto lo = lower_bound(pos.begin(), pos.end(), l);
        auto hi = upper_bound(pos.begin(), pos.end(), r);

        cout << (hi - lo) << "\n";  // 迭代器间距离 = 个数
    }

    return 0;
}

关键点：

• 先对位置排序——二分查找的前提条件
• lower_bound(pos.begin(), pos.end(), l) 返回第一个 ≥ l 的元素的迭代器
• upper_bound(pos.begin(), pos.end(), r) 返回第一个 > r 的元素的迭代器
• [l, r] 内元素个数 = 两迭代器之间的距离 = hi - lo
• 总复杂度：排序 O(N log N) + 查询 O(Q log N)——远优于暴力 O(N×Q)