deque、priority_queue 与 bitset

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

void show(deque<int>& d, string name) {
    cout << name << " : ";
    if (d.empty()) cout << "(empty)";
    else for (int x : d) cout << x << " ";
    cout << "   [front="
         << (d.empty() ? -1 : d.front())
         << ", back="
         << (d.empty() ? -1 : d.back())
         << ", size=" << d.size() << "]\n";
}

int main() {
    deque<int> d;

    d.push_back(3);        // 队尾进：3
    d.push_back(4);        // 队尾进：3 4
    d.push_front(2);       // 队首进：2 3 4
    d.push_front(1);       // 队首进：1 2 3 4
    show(d, "四次 push 后");

    cout << "d[0]=" << d[0]            // 随机访问：1
         << ", d[3]=" << d[3] << "\n";   // 4
    cout << "front=" << d.front()
         << ", back=" << d.back() << "\n";

    d.pop_front();                // 队首出：2 3 4
    d.pop_back();                 // 队尾出：2 3
    show(d, "一前一后各出一次");

    d.insert(d.begin() + 1, 99);   // 中间插入是 O(n)，尽量少用
    show(d, "中间插入 99");

    cout << "sort 前："; for (int x : d) cout << x << " "; cout << "\n";
    sort(d.begin(), d.end());     // deque 迭代器是随机访问，可以 sort
    cout << "sort 后："; for (int x : d) cout << x << " "; cout << "\n";

    d.clear();
    cout << "clear 后 empty = " << d.empty() << "\n";
    return 0;
}

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

int main() {
    priority_queue<int> pq;        // 默认就是「大根堆」

    for (int x : {3, 1, 9, 4, 7}) pq.push(x);

    cout << "size = " << pq.size() << ", top = " << pq.top() << "\n";

    cout << "依次弹堆顶（降序）：";
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << "\n";

    // 注意：优先队列不能遍历、不能随机访问、不能清空单个元素
    // for (int x : pq) ... // 编译错误
    // cout << pq[0];        // 编译错误
    return 0;
}

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

int main() {
    // ① 大根堆（默认）
    priority_queue<int> big;
    // ② 小根堆：必须写全三个模板参数
    priority_queue<int, vector<int>, greater<int>> small;

    for (int x : {5, 1, 9, 3}) { big.push(x); small.push(x); }
    cout << "大根堆 top = " << big.top() << "\n";    // 9
    cout << "小根堆 top = " << small.top() << "\n";  // 1

    // ③ pair 入堆：先按 first 比，first 相同再按 second 比
    priority_queue<pair<int, int>> pq;
    pq.push({2, 100});
    pq.push({3, 10});
    pq.push({3, 99});
    pq.push({1, 999});
    cout << "pair 堆弹出顺序：";
    while (!pq.empty()) {
        cout << "(" << pq.top().first << "," << pq.top().second << ") ";
        pq.pop();
    }
    cout << "\n";

    // ④ 存负值当小根堆用（不想写比较器时的投机写法）
    priority_queue<long long> neg;
    for (long long x : {5L, 1L, 9L}) neg.push(-x);
    cout << "用负数模拟小根堆，最小值 = " << -neg.top() << "\n";  // 1
    return 0;
}

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

struct Node {
    int step;    // 步数
    int id;      // 编号
};

// 比较器：返回 true 表示 a 的优先级「低于」b（即 a 应该排在更后面）
struct Cmp {
    bool operator()(const Node& a, const Node& b) const {
        if (a.step != b.step) return a.step > b.step;  // step 小的优先
        return a.id > b.id;                          // id 小的优先
    }
};

int main() {
    priority_queue<Node, vector<Node>, Cmp> pq;
    pq.push({5, 1});
    pq.push({2, 7});
    pq.push({2, 3});
    pq.push({9, 2});

    cout << "出堆顺序（step 升序，同 step 按 id 升序）：\n";
    while (!pq.empty()) {
        Node t = pq.top(); pq.pop();
        cout << "step=" << t.step << " id=" << t.id << "\n";
    }
    return 0;
}

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

priority_queue<int> pq;                  // 主堆：大根堆
priority_queue<int, vector<int>, greater<int>> del;  // 待删堆：小根堆

// 关键：把两个堆顶「对上账」——主堆顶等于待删堆顶的那些都是已经失效的
void cleanup() {
    while (!pq.empty() && !del.empty() && pq.top() == del.top()) {
        pq.pop();
        del.pop();
    }
}

void insert(int x) { pq.push(x); }
void erase(int x)  { del.push(x); cleanup(); }
bool empty()       { cleanup(); return pq.empty(); }
int  top()         { cleanup(); return pq.top(); }

int main() {
    for (int x : {5, 3, 9, 5, 7}) insert(x);
    cout << "top = " << top() << "\n";      // 9

    erase(9);
    cout << "删除 9 后 top = " << top() << "\n";   // 7

    erase(5);                            // 只删「一个 5」
    cout << "删除一个 5 后 top = " << top() << "\n";  // 7
    cout << "现在最大值仍是 7，说明另一个 5 还在\n";
    return 0;
}

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

int main() {
    bitset<8> b;                       // 8 个位，初值全 0
    cout << "初始 b = " << b << "\n";

    b.set();                            // 全部置 1
    cout << "set() 后 = " << b << "\n";

    b.reset();                          // 全部置 0
    cout << "reset() 后 = " << b << "\n";

    b.set(0); b.set(2); b.set(3); b.set(7);   // 指定位置 1
    cout << "打点后 = " << b << "\n";      // 10001101（左边是高位）

    cout << "b[2] = " << b[2] << "\n";         // 1
    b.flip(2);                        // 翻转第 2 位
    cout << "flip(2) 后 = " << b << "\n";

    b.set(2);                          // 翻转回来（为了下面的统计）
    cout << "count() = " << b.count() << "\n";   // 4 个 1
    cout << "size()  = " << b.size()  << "\n";   // 8
    cout << "any()   = " << b.any()   << "\n";   // 1（存在 1）
    cout << "none()  = " << b.none()  << "\n";   // 0（不是全 0）
    cout << "all()   = " << b.all()   << "\n";   // 0（不是全 1）
    cout << "test(2) = " << b.test(2) << "\n";  // 1

    cout << "to_string = " << b.to_string() << "\n";
    cout << "转 unsigned long = " << b.to_ulong() << "\n";   // 141

    // 位运算与移位：整块并行，速度快 64 倍
    bitset<8> x(string("1100")), y(string("1010"));
    cout << "x & y = " << (x & y) << "\n";   // 1000
    cout << "x | y = " << (x | y) << "\n";   // 1110
    cout << "x ^ y = " << (x ^ y) << "\n";   // 0110
    cout << "~x    = " << (~x)    << "\n";   // 0011（取反补齐到 4 位）
    cout << "x << 2 = " << (x << 2) << "\n";  // 0000（1100 左移两位溢出）
    return 0;
}

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

// ========= ① 01 背包：能否凑出和 S =========
bitset<100005> f;

// ========= ② Floyd 传递闭包：n ≤ 1000 =========
const int N = 1005;
bitset<N> reach[N];

int main() {
    // —— 01 背包演示 ——
    f[0] = 1;                    // 和为 0 总是可达
    int a[] = {2, 3, 5};
    for (int x : a)
        f |= (f << x);              // 一次位运算 = 一整轮 DP 转移
    cout << "可达和集合（≤12）：";
    for (int s = 0; s <= 12; s++)
        if (f[s]) cout << s << " ";
    cout << "\n";

    // —— Floyd 传递闭包演示 ——
    int n = 4;
    int edges[][2] = {{1,2}, {2,3}, {3,4}};
    for (int i = 1; i <= n; i++) reach[i][i] = 1;   // 自己可达自己
    for (auto& e : edges) reach[e[0]][e[1]] = 1;

    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            if (reach[i][k]) reach[i] |= reach[k];  // 一行搞定一整行

    cout << "可达矩阵：\n";
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) cout << reach[i][j];
        cout << "\n";
    }
    cout << "1 能否到 4 ? " << (reach[1][4] ? "YES" : "NO") << "\n";
    cout << "4 能否到 1 ? " << (reach[4][1] ? "YES" : "NO") << "\n";
    return 0;
}

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

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

    int n; cin >> n;
    // 小根堆：三个模板参数一个都不能少
    priority_queue<long long, vector<long long>, greater<long long>> pq;

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

    long long ans = 0;
    while (pq.size() > 1) {
        long long a = pq.top(); pq.pop();   // 最小
        long long b = pq.top(); pq.pop();   // 次小
        long long s = a + b;
        ans += s;                            // 本次体力消耗
        pq.push(s);                          // 合并后的新堆放回
    }

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

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

const int MAXN = 1000005;
long long a[MAXN];
int n, k;

// mode = 0 求最小值（队内单调递增）; mode = 1 求最大值（队内单调递减）
vector<long long> solve(int mode) {
    deque<int> dq;                  // 存「下标」而不是值！
    vector<long long> res;

    for (int i = 1; i <= n; i++) {
        // ① 队尾维护单调性：把「不可能成为答案」的旧元素弹掉
        while (!dq.empty() &&
               (mode == 0 ? a[dq.back()] >= a[i]   // 求最小：弹掉更大的
                            : a[dq.back()] <= a[i])) // 求最大：弹掉更小的
            dq.pop_back();

        dq.push_back(i);

        // ② 队头过期判断：下标 <= i-k 的已经滑出窗口
        while (dq.front() <= i - k) dq.pop_front();

        // ③ 窗口形成后开始记录答案，队头就是最值
        if (i >= k) res.push_back(a[dq.front()]);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<long long> mn = solve(0);
    vector<long long> mx = solve(1);

    for (long long v : mn) cout << v << " ";
    cout << "\n";
    for (long long v : mx) cout << v << " ";
    cout << "\n";
    return 0;
}

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

const int MAXN = 1005;
bitset<MAXN> f[MAXN];          // f[i] 的第 j 位 = 1 表示 i 能到 j

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

    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) f[i][i] = 1;   // 自反闭包

    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        f[u][v] = 1;
    }

    // 传递闭包：O(n^3 / 64)
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            if (f[i][k]) f[i] |= f[k];      // ★ 核心只有这一行！

    int q; cin >> q;
    while (q--) {
        int u, v; cin >> u >> v;
        cout << (f[u][v] ? "YES\n" : "NO\n");
    }
    return 0;
}

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

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

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

    long long ans = 0;
    while (pq.size() > 1) {
        long long a = pq.top(); pq.pop();
        long long b = pq.top(); pq.pop();
        ans += a + b;
        pq.push(a + b);
    }
    cout << ans << "\n";
    return 0;
}

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

const int MAXN = 100005;
long long h[MAXN];     // 小根堆：h[i] <= h[2i], h[i] <= h[2i+1]
int sz = 0;

void shift_up(int i) {                 // 上浮
    while (i > 1 && h[i] < h[i >> 1]) {
        swap(h[i], h[i >> 1]);
        i >>= 1;
    }
}

void shift_down(int i) {               // 下沉
    while ((i << 1) <= sz) {
        int s = i << 1;                     // 左儿子
        if (s + 1 <= sz && h[s + 1] < h[s]) s++;   // 选较小的儿子
        if (h[i] <= h[s]) break;
        swap(h[i], h[s]);
        i = s;
    }
}

void push(long long v) { h[++sz] = v; shift_up(sz); }
long long top()        { return h[1]; }
void pop()            { h[1] = h[sz--]; shift_down(1); }

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    for (int i = 0; i < n; i++) { long long x; cin >> x; push(x); }

    long long ans = 0;
    while (sz > 1) {
        long long a = top(); pop();
        long long b = top(); pop();
        ans += a + b;
        push(a + b);
    }
    cout << ans << "\n";
    return 0;
}

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

const int MAXN = 1000005;
long long a[MAXN];
int n, k;

void run(int mode) {          // 0 = 求最小, 1 = 求最大
    deque<int> dq;
    for (int i = 1; i <= n; i++) {
        while (!dq.empty() &&
               (mode == 0 ? a[dq.back()] >= a[i] : a[dq.back()] <= a[i]))
            dq.pop_back();
        dq.push_back(i);
        while (dq.front() <= i - k) dq.pop_front();
        if (i >= k) cout << a[dq.front()] << (i == n ? '\n' : ' ');
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    run(0);
    run(1);
    return 0;
}

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

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

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

    // pair 默认先比 first（值）再比 second（下标），所以是大根堆
    priority_queue<pair<long long, int>> pq;

    for (int i = 1; i <= n; i++) {
        pq.push({a[i], i});
        if (i >= k) {
            // 懒删除：堆顶下标若已滑出窗口，直接丢弃
            while (pq.top().second <= i - k) pq.pop();
            cout << pq.top().first << (i == n ? '\n' : ' ');
        }
    }
    return 0;
}

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

const int MAXS = 1000005;
bitset<MAXS> f;            // f[j] = 1 表示和 j 可以被凑出
bitset<MAXS> snap[1005];  // 存档，用于还原方案

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

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

    f[0] = 1;                     // 和为 0 永远可达
    for (int i = 1; i <= n; i++) {
        snap[i] = f;                   // 存档：加入第 i 个数之前的状态
        f |= (f << a[i]);              // ★ 核心一行：整批状态同时转移
    }

    if (!f[S]) { cout << "NO\n"; return 0; }
    cout << "YES\n";

    // 从后往前还原：若 snap[i] 里 j 已可达，说明第 i 个数没被选
    vector<int> pick;
    int j = S;
    for (int i = n; i >= 1; i--) {
        if (j >= 0 && !snap[i][j]) {     // 加之前不可达 → 是第 i 个数贡献的
            pick.push_back(i);
            j -= a[i];
        }
    }
    for (int i = (int)pick.size() - 1; i >= 0; i--)
        cout << pick[i] << (i ? ' ' : '\n');
    return 0;
}

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

// ============ 一、deque 模板 ============
void dequeTemplate() {
    deque<int> d;
    d.push_back(3);          // 尾部进
    d.push_front(1);         // 头部进（vector 做不到）
    d.pop_back();              // 尾部出
    d.pop_front();             // 头部出
    int a = d.front(), b = d.back();
    int c = d[0];              // 随机访问 O(1)
    sort(d.begin(), d.end());  // 迭代器是随机访问，可以排序
    // d.reserve(1000);        // ❌ 不存在这个接口

    // ★ 单调队列（求滑动窗口最小值）核心四行
    // while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
    // dq.push_back(i);
    // while (dq.front() <= i - k) dq.pop_front();
    // if (i >= k) ans = a[dq.front()];
}

// ============ 二、priority_queue 模板 ============
void pqTemplate() {
    // ① 大根堆（默认）
    priority_queue<int> big;
    // ② 小根堆（三个参数写全）
    priority_queue<int, vector<int>, greater<int>> small;
    // ③ pair 大根堆（先比 first）
    priority_queue<pair<int,int>> pp;

    big.push(5);
    int t = big.top();          // O(1) 取最值
    big.pop();                  // O(log n) 删堆顶
    bool e = big.empty();
    int s = big.size();
    // big.clear();             // ❌ 没有 clear，只能循环 pop
    // for (int x : big) ;       // ❌ 不可遍历
}

// 自定义比较器：返回 true 表示 a 优先级更低（沉下去）
struct Node { int dis, id; };
struct Cmp {
    bool operator()(const Node& a, const Node& b) const {
        if (a.dis != b.dis) return a.dis > b.dis;  // dis 小的优先
        return a.id > b.id;
    }
};
// priority_queue<Node, vector<Node>, Cmp> pq;

// ============ 三、bitset 模板 ============
const int MAXN = 100005;

void bitsetTemplate() {
    bitset<MAXN> b;
    b.set();  b.reset();  b.flip();       // 全 1 / 全 0 / 全取反
    b.set(3);  b.reset(3);  b.flip(3);    // 单点操作
    cout << b[3] << b.count() << b.any() << b.none() << b.all();

    bitset<MAXN> c;
    b &= c;  b |= c;  b ^= c;  b = ~c;    // 位运算 O(N/64)
    b <<= 3;  b >>= 3;                     // 移位
    string s = b.to_string();

    // ★ 场景 A：01 背包可达性
    // f[0] = 1;
    // for (int x : a) f |= (f << x);
    // if (f[S]) cout << "YES";

    // ★ 场景 B：传递闭包（Floyd 位运算版）
    // for (int k = 1; k <= n; k++)
    //     for (int i = 1; i <= n; i++)
    //         if (g[i][k]) g[i] |= g[k];
}

// ============ 四、手写小根堆（下标从 1 开始）============
long long h[100005]; int sz = 0;
void upHeap(int i)   { while (i > 1 && h[i] < h[i>>1]) { swap(h[i], h[i>>1]); i >>= 1; } }
void downHeap(int i) { while ((i<<1) <= sz) { int s = i<<1;
        if (s + 1 <= sz && h[s+1] < h[s]) s++;
        if (h[i] <= h[s]) break; swap(h[i], h[s]); i = s; } }
void hpPush(long long v) { h[++sz] = v; upHeap(sz); }
void hpPop()              { h[1] = h[sz--]; downHeap(1); }

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

priority_queue<int> lo;                                          // 大根堆：较小的一半
priority_queue<int, vector<int>, greater<int>> hi;            // 小根堆：较大的一半

void add(int x) {
    if (lo.empty() || x <= lo.top()) lo.push(x);
    else hi.push(x);

    // 保持 lo.size() == hi.size() 或 lo.size() == hi.size()+1
    if ((int)lo.size() > (int)hi.size() + 1) { hi.push(lo.top()); lo.pop(); }
    if ((int)hi.size() > (int)lo.size())         { lo.push(hi.top()); hi.pop(); }
}

int main() {
    ios::sync_with_stdio(0);
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        add(x);
        if (i % 2 == 0) cout << lo.top() << "\n";   // P1168：奇数个时输出
    }
    return 0;
}

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

int main() {
    ios::sync_with_stdio(0);
    int n; cin >> n;
    vector<int> A(n), B(n);
    for (int& x : A) cin >> x;
    for (int& x : B) cin >> x;
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    // 小根堆：存 (和, A 的下标, B 的下标)
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>,
                   greater<tuple<int,int,int>>> pq;

    for (int i = 0; i < n; i++) pq.push({A[i] + B[0], i, 0});

    for (int c = 0; c < n; c++) {
        auto [sum, i, j] = pq.top(); pq.pop();
        cout << sum << (c == n - 1 ? '\n' : ' ');
        if (j + 1 < n) pq.push({A[i] + B[j + 1], i, j + 1});
    }
    return 0;
}

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

const int MAXS = 2000005;
bitset<MAXS> f;

int main() {
    ios::sync_with_stdio(0);
    int n, S; cin >> n >> S;
    vector<int> cnt(1005, 0);
    for (int i = 0; i < n; i++) { int x; cin >> x; cnt[x]++; }

    f[0] = 1;
    for (int v = 1; v <= 1000; v++) {
        if (!cnt[v]) continue;
        // 二进制拆分：把 cnt[v] 个 v 拆成 1,2,4,8,... 组，转成 01 背包
        int c = cnt[v];
        for (int p = 1; c > 0; p <<= 1) {
            int take = min(p, c);
            f |= (f << (v * take));
            c -= take;
        }
    }
    cout << f.count() << " 种不同的和可以被凑出\n";
    return 0;
}