第 5 章 数据结构

stack<int> st;   // st.push(x)  st.top()   st.pop()
queue<int> q;    // q.push(x)   q.front()  q.pop()            BFS 用它
deque<int> dq;   // dq.push_back(x)  dq.push_front(x)  dq.pop_back()  dq.pop_front()  dq.front()  dq.back()
// 三个都有 empty() 和 size()

int stk[N], top = 0;             // 入栈 stk[++top] = x   栈顶 stk[top]   出栈 top--   判空 top == 0      清空 top = 0
int que[N], head = 1, tail = 0;  // 入队 que[++tail] = x  队头 que[head]  出队 head++  判空 head > tail   清空 head = 1, tail = 0

// 单调栈：对每个 i，求它右边第一个比 a[i] 大的元素的下标（没有则为 0）。洛谷 P5788。
// 栈里存下标。新元素进来时，栈顶那些比它小的元素等到了答案——就是这个新元素——于是出栈。
#include <bits/stdc++.h>
using namespace std;

const int N = 3000005;
int a[N], ans[N], stk[N], top;  // stk 是手写栈，存下标；top 是栈里的元素个数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        while (top > 0 && a[stk[top]] < a[i]) {  // 严格小于才出栈：相等不算“更大”
            ans[stk[top]] = i;
            top--;
        }
        stk[++top] = i;
    }
    // 循环结束后还留在栈里的元素，右边没有比它大的，ans 保持初值 0
    for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
    cout << '\n';
    return 0;
}

for (int i = 1; i <= n; i++) R[i] = n + 1;       // 右边没有更大的：记成 n+1
for (int i = 1; i <= n; i++) {
    while (top > 0 && a[stk[top]] < a[i]) {      // 右边第一个 > 它的（严格）
        R[stk[top]] = i;
        top--;
    }
    L[i] = top > 0 ? stk[top] : 0;               // 左边第一个 >= 它的（不严格）；没有记成 0
    stk[++top] = i;
}
// a[i] 负责的区间：左端点在 (L[i], i]，右端点在 [i, R[i])，一共 (i - L[i]) * (R[i] - i) 个

// 单调队列：长度为 k 的窗口从左滑到右，输出每个窗口的最小值（第一行）和最大值（第二行）。洛谷 P1886。
// 队列里存下标：下标递增，对应的值单调，队头永远是当前窗口的最值。
#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;
int n, k, a[N], q[N];  // q 是手写队列，存下标，有效部分是 q[head..tail]

// want_min 为 true 时求每个窗口的最小值，为 false 时求最大值
void slide(bool want_min) {
    int head = 1, tail = 0;  // head > tail 表示队列为空
    for (int i = 1; i <= n; i++) {
        // 求最小值时：队尾的值不比 a[i] 小，它又比 a[i] 先滑出窗口，永远轮不到它，删掉
        while (head <= tail && (want_min ? a[q[tail]] >= a[i] : a[q[tail]] <= a[i])) tail--;
        q[++tail] = i;
        while (q[head] <= i - k) head++;        // 队头滑出了窗口 [i-k+1, i]；刚放进去的 i 一定在窗口里，不会删空
        if (i >= k) cout << a[q[head]] << ' ';  // 凑满一个窗口才开始输出
    }
    cout << '\n';
}

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

// 堆（优先队列）：每次取出最小的两堆合并，代价是两堆之和，求合并成一堆的最小总代价。洛谷 P1090 合并果子。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    priority_queue<long long, vector<long long>, greater<long long> > heap;  // 小根堆：top() 是最小值
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        heap.push(x);
    }
    long long total = 0;
    while (heap.size() > 1) {
        long long first = heap.top();  // top() 只看不取
        heap.pop();                    // pop() 才删除，而且没有返回值
        long long second = heap.top();
        heap.pop();
        total += first + second;
        heap.push(first + second);
    }
    cout << total << '\n';
    return 0;
}

priority_queue<int, vector<int>, greater<int> > small;   // 写法一：标准写法，照抄

priority_queue<int> negated;                              // 写法二：存相反数。只适合数字
negated.push(-x);
int smallest = -negated.top();

struct Node {                                             // 写法三：结构体里重载小于号
    long long dist;
    int id;
    bool operator<(const Node &other) const { return dist > other.dist; }   // 方向是反的：dist 小的优先
};
priority_queue<Node> heap;

// ST 表：数组不修改，多次询问区间最大值。预处理 O(n log n)，每次询问 O(1)。洛谷 P3865。
// f[j][i] 表示从 i 开始、长度为 2^j 的一段（即 [i, i + 2^j - 1]）的最大值。
#include <bits/stdc++.h>
using namespace std;

const int N = 100005, LOG = 17;  // 2^17 = 131072 >= N；n 到 1e6 时 LOG 取 20
int f[LOG + 1][N], lg[N];        // lg[x] = log2(x) 向下取整

int read() {  // 询问有 2e6 次，必须快读
    int x = 0, sign = 1, c = getchar();
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    if (c == '-') sign = -1, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + (c - '0'), c = getchar();
    return x * sign;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n = read(), m = read();
    for (int i = 1; i <= n; i++) f[0][i] = read();  // 长度为 1 的段就是元素自己
    for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
    for (int j = 1; j <= LOG; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)  // 这一段的右端点不能超过 n
            f[j][i] = max(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);  // 左半段、右半段各长 2^(j-1)
    while (m--) {
        int l = read(), r = read();
        int j = lg[r - l + 1];
        // 两段长 2^j 的区间，一段贴着 l，一段贴着 r，合起来正好盖住 [l, r]；中间重叠不影响最大值
        cout << max(f[j][l], f[j][r - (1 << j) + 1]) << '\n';
    }
    return 0;
}

// 树状数组：单点加、区间求和，每次 O(log n)。洛谷 P3374。
// c[i] 存的是以 i 结尾、长度为 lowbit(i) 的那一段的和。
#include <bits/stdc++.h>
using namespace std;

const int N = 500005;
int n, m;
long long c[N];

int lowbit(int x) { return x & -x; }  // x 的二进制里最低位的 1 所代表的数，例如 lowbit(6) = 2

void add(int pos, long long value) {  // 第 pos 个数加上 value
    for (int i = pos; i <= n; i += lowbit(i)) c[i] += value;
}

long long prefix(int pos) {  // 前 pos 个数的和
    long long sum = 0;
    for (int i = pos; i > 0; i -= lowbit(i)) sum += c[i];
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        add(i, x);  // 初值也当成一次“单点加”
    }
    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) add(x, y);                           // 第 x 个数加上 y
        else cout << prefix(y) - prefix(x - 1) << '\n';  // 区间 [x, y] 的和 = 两个前缀和相减
    }
    return 0;
}

// 逆序对：有多少对 i < j 满足 a[i] > a[j]。离散化 + 树状数组，O(n log n)。洛谷 P1908。
#include <bits/stdc++.h>
using namespace std;

const int N = 500005;
int n, a[N], sorted_a[N];
int c[N];  // 树状数组：下标是“值的排名”，存这个排名已经出现了几次

void add(int pos) {
    for (int i = pos; i <= n; i += i & -i) c[i]++;
}

int prefix(int pos) {
    int sum = 0;
    for (int i = pos; i > 0; i -= i & -i) sum += c[i];
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sorted_a[i] = a[i];
    }
    // 离散化：值最大到 1e9，不能直接当下标；只关心大小关系，所以把值换成它的排名 1..cnt
    sort(sorted_a + 1, sorted_a + n + 1);
    int cnt = unique(sorted_a + 1, sorted_a + n + 1) - (sorted_a + 1);
    long long ans = 0;  // 最多约 n^2/2 = 1.25e11，超过 int
    for (int i = 1; i <= n; i++) {
        int rk = lower_bound(sorted_a + 1, sorted_a + cnt + 1, a[i]) - sorted_a;  // a[i] 的排名
        ans += (i - 1) - prefix(rk);  // 前面 i-1 个数里，不超过 a[i] 的有 prefix(rk) 个，剩下的都比它大
        add(rk);
    }
    cout << ans << '\n';
    return 0;
}

// 线段树：区间加、区间求和，带懒标记，每次操作 O(log n)。洛谷 P3372。
// 结点 p 管区间 [l, r]；左儿子 2p 管 [l, mid]，右儿子 2p+1 管 [mid+1, r]。
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int n, m;
long long a[N], sum[N * 4], tag[N * 4];  // 开 4 倍；tag[p]：p 这一段的每个数都该加 tag[p]，但还没通知儿子

void pushup(int p) { sum[p] = sum[p * 2] + sum[p * 2 + 1]; }

void add_tag(int p, int l, int r, long long v) {  // 结点 p（管 [l, r]）整段加 v：改自己的和，记下标记
    sum[p] += v * (r - l + 1);
    tag[p] += v;
}

void pushdown(int p, int l, int r) {  // 把欠儿子的标记发下去
    if (tag[p] == 0) return;
    int mid = (l + r) / 2;
    add_tag(p * 2, l, mid, tag[p]);
    add_tag(p * 2 + 1, mid + 1, r, tag[p]);
    tag[p] = 0;
}

void build(int p, int l, int r) {
    tag[p] = 0;  // 多组数据时靠这一行清标记
    if (l == r) {
        sum[p] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    pushup(p);
}

void update(int p, int l, int r, int ql, int qr, long long v) {  // [ql, qr] 里每个数加 v
    if (ql <= l && r <= qr) {  // 当前结点被完全包含：打上标记就返回，不再往下
        add_tag(p, l, r, v);
        return;
    }
    pushdown(p, l, r);  // 要往下走，先把旧标记发下去
    int mid = (l + r) / 2;
    if (ql <= mid) update(p * 2, l, mid, ql, qr, v);
    if (qr > mid) update(p * 2 + 1, mid + 1, r, ql, qr, v);
    pushup(p);  // 儿子变了，重新算自己
}

long long query(int p, int l, int r, int ql, int qr) {  // [ql, qr] 的和
    if (ql <= l && r <= qr) return sum[p];
    pushdown(p, l, r);
    int mid = (l + r) / 2;
    long long result = 0;
    if (ql <= mid) result += query(p * 2, l, mid, ql, qr);
    if (qr > mid) result += query(p * 2 + 1, mid + 1, r, ql, qr);
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            long long k;
            cin >> k;
            update(1, 1, n, x, y, k);
        } else {
            cout << query(1, 1, n, x, y) << '\n';
        }
    }
    return 0;
}

long long mx[N * 4];                                               // 1. sum 数组换成 mx
void pushup(int p) { mx[p] = max(mx[p * 2], mx[p * 2 + 1]); }      // 2. 合并两个儿子：取较大的
void add_tag(int p, long long v) { mx[p] += v; tag[p] += v; }      // 3. 整段加 v，最大值也加 v，和区间长度无关
// 4. query 里：result 的初值改成 LLONG_MIN，两处 result += ... 改成 result = max(result, ...)