K04 前缀和、差分、递推 + 栈、队列、链表（第二轮系统课 · 第 4 次）

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

long long s[1005][1005];     // 下标从 1 开始，第 0 行第 0 列天然是 0

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            long long x;
            cin >> x;
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;
        }
    int q;
    cin >> q;
    while (q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] << endl;
    }
    return 0;
}

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

int d[1005][1005];

int main() {
    int n, m;
    cin >> n >> m;                 // n×n 的格子，m 次矩形加 1
    while (m--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        d[x1][y1]++;
        d[x1][y2 + 1]--;
        d[x2 + 1][y1]--;
        d[x2 + 1][y2 + 1]++;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];   // 原地做前缀和
            cout << d[i][j] << (j == n ? '\n' : ' ');
        }
    }
    return 0;
}

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

long long f[100];

int main() {
    int n;
    cin >> n;
    // n<=90，f(90) 约 4.6e18，long long 刚好装得下
    f[1] = 1;
    f[2] = 2;
    for (int i = 3; i <= n; i++) f[i] = f[i - 1] + f[i - 2];
    cout << f[n] << endl;
    return 0;
}

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

int main() {
    // 输入：用空格隔开的后缀表达式，例如 3 5 2 - * 7 +
    stack<long long> st;
    string tok;
    while (cin >> tok) {
        if (tok == "+" || tok == "-" || tok == "*" || tok == "/") {
            long long b = st.top(); st.pop();     // 先弹出的是右边那个数
            long long a = st.top(); st.pop();
            if (tok == "+") st.push(a + b);
            if (tok == "-") st.push(a - b);
            if (tok == "*") st.push(a * b);
            if (tok == "/") st.push(a / b);
        } else {
            st.push(stoll(tok));
        }
    }
    cout << st.top() << endl;
    return 0;
}

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

const int N = 100005;
int L[N], R[N];
bool removed[N];

void insertRight(int k, int x) {      // 把 x 插到 k 的右边
    R[x] = R[k];
    L[x] = k;
    L[R[k]] = x;
    R[k] = x;
}

void erase_(int x) {                  // 删掉 x
    if (removed[x]) return;           // 删过的不能再删
    removed[x] = true;
    R[L[x]] = R[x];
    L[R[x]] = L[x];
}

int main() {
    R[0] = 0; L[0] = 0;               // 空链表：哨兵自己连自己
    insertRight(0, 1);                // 1
    insertRight(1, 3);                // 1 3
    insertRight(1, 2);                // 1 2 3
    insertRight(0, 4);                // 4 1 2 3
    erase_(2);                        // 4 1 3
    erase_(2);                        // 再删一次，不应出错
    for (int x = R[0]; x != 0; x = R[x]) cout << x << " ";
    cout << endl;
    return 0;
}

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

int main() {
    list<int> lst = {1, 2, 3};
    auto it = lst.begin();       // 指向 1
    ++it;                        // 指向 2
    lst.insert(it, 9);           // 插到 2 的前面：1 9 2 3
    it = lst.erase(it);          // 删掉 2，it 指向下一个（3）：1 9 3
    lst.push_front(0);           // 0 1 9 3
    for (int x : lst) cout << x << " ";
    cout << endl;
    return 0;
}