洛谷 SCP-S 2023 第一轮模拟赛（提高级 C++）

#include <iostream>
using namespace std;

int a[100005], b[100005], n, m;

void very_quick_sort(int l, int r, int p, int q) {
    if (l >= r || p > q) { // ①
        return;
    }
    int mid = (l + r) / 2;
    int p0 = p - 1;
    int q0 = q + 1;
    for (int i = p; i <= q; i++) {
        if (a[i] > mid) b[++p0] = a[i];
        else b[--q0] = a[i];
    }
    for (int i = p; i <= q; i++)
        a[i] = b[i];
    very_quick_sort(mid + 1, r, p, p0);
    very_quick_sort(l, mid, q0, q);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    very_quick_sort(1, m, 1, n);
    // ②
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int mod = 1000000000 + 7;
int w0[100005];
int w1[100005];
int w2[100005];
int n, m, k, f[100005], d[100005], id[100005];
vector<int> e[100005];

void dfs(int u, int fa) {
    d[u] = d[fa] + 1;
    f[u] = fa;
    for (auto &v : e[u]) if (v != fa) {
        dfs(v, u);
    }
}

bool cmp(int a, int b) {
    return d[a] < d[b];
}

int main() {
    cin >> n >> m >> k;
    for (int i = 2; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0); // ①
    for (int i = 1; i <= m; i++) {
        int x, w;
        cin >> x >> w;
        w1[x] = (w1[x] + w) % mod;
        w2[x] = (w2[x] + w) % mod;
    }
    for (int i = 1; i <= n; i++)
        id[i] = i;
    sort(id + 1, id + 1 + n, cmp);
    for (int i = 1; i <= k; i++) {
        for (int j = n; j >= 1; j--) {
            int x = id[j];
            for (auto &y : e[x]) if (y != f[x]) {
                w1[y] = (w1[y] + w1[x]) % mod;
            }
            w1[x] = 0;
        }
        for (int x = 1; x <= n; x++)
            w1[x] = (w1[x] - w0[x] + mod) % mod,
            w0[x] = 0;
        for (int j = 1; j <= n; j++) { // ②
            int x = id[j];
            if (f[x]) {
                w1[f[x]] = (w1[f[x]] + w2[x]) % mod;
                w2[f[x]] = (w2[f[x]] + w2[x]) % mod;
                w0[x] = (w0[x] + w2[x]) % mod;
                w2[x] = 0;
            }
        }
    }
    for (int i = 1; i <= n; i++)
        cout << w1[i] << " ";
    return 0;
}

#include <iostream>
using namespace std;
typedef long long i64;

namespace CirnoTree {
    const int SIZ = 4e6 + 3;

    int build1(int l, int r);
    int build2(int l, int r);

    int siz = 0;
    int lft[SIZ], rgt[SIZ];
    int nex[SIZ], son[SIZ];
    i64 sum[SIZ];
    i64 below_tag[SIZ];
    i64 right_tag[SIZ];

    int build1(int l, int r) {
        int u = ++siz;
        lft[u] = l;
        rgt[u] = r;
        son[u] = l == r ? 0 : build2(l, r);
        return u;
    }

    int build2(int l, int r) {
        int mid = (l + r) / 2;
        int p = build1(l, mid);
        nex[p] = l == r ? 0 : build2(mid + 1, r);
        return p;
    }

    void update(int t) {
        if (below_tag[t] != 0 && son[t] != 0) {
            sum[son[t]] +=
                1ll * (rgt[son[t]] - lft[son[t]] + 1) * below_tag[t];
            below_tag[son[t]] += below_tag[t];
            right_tag[son[t]] += below_tag[t];
        }
        below_tag[t] = 0;
        if (right_tag[t] != 0 && nex[t] != 0) {
            sum[nex[t]] +=
                1ll * (rgt[nex[t]] - lft[nex[t]] + 1) * right_tag[t];
            below_tag[nex[t]] += right_tag[t];
            right_tag[nex[t]] += right_tag[t];
        }
        right_tag[t] = 0;
    }

    void modify(int t, int pos, int w) {
        if (rgt[t] <= pos) {
            below_tag[t] += w;
            sum[t] += 1ll * w * (rgt[t] - lft[t] + 1);
        } else {
            int l = max(lft[t], 1);
            int r = min(rgt[t], pos);
            update(t);
            sum[t] += 1ll * (r - l + 1) * w;
            for (int p = son[t]; p != 0 && lft[p] <= pos; p = nex[p])
                update(p), modify(p, pos, w);
        }
    }

    i64 query(int t, int pos) {
        if (rgt[t] <= pos) {
            return sum[t];
        } else {
            update(t); i64 ans = 0;
            for (int p = son[t]; p != 0 && lft[p] <= pos; p = nex[p])
                update(p), ans += query(p, pos);
            return ans;
        }
    }
};

int main() {
    int n, m, root;
    cin >> n >> m;
    root = CirnoTree::build1(1, n);
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        CirnoTree::modify(root, i, x);
    }
    for (int i = 1, op; i <= m; i++) {
        cin >> op;
        if (op == 1) {
            int l, r, w;
            cin >> l >> r >> w;
            CirnoTree::modify(root, r, w);
            CirnoTree::modify(root, l - 1, -w);
        } else {
            int l, r;
            cin >> l >> r;
            i64 w1 = CirnoTree::query(root, r);
            i64 w2 = CirnoTree::query(root, l - 1);
            cout << w1 - w2 << endl;
        }
    }
    return 0;
}

(1)（异或和）给定序列 $a_n$，求其所有子区间异或和的和。某个区间的异或和的意思是将这个区间内的所有数字分别进行异或计算。其中 $n \leq 10^5$， $\emptyset \leq a_i \leq 10^9$。

提示：对每一位独立计算，对右端点扫描线，并用异或前缀和辅助统计。

试补全程序。

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

const int N = 1e5 + 7;
int n, a[N], cnt[2];
long long ans;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], ①;
    for (int bit = ②; ③; bit--) {
        cnt[0] = cnt[1] = 0;
        for (int i = 0; i <= n; i++) {
            cnt[④]++;
            ans += 1LL * ⑤;
        }
    }
    cout << ans;
}

(2)（覆盖）给定序列$\{a_n\}$（$1\leq n\leq 100$，$a_i\in\{0,1,2\}$），描述$n$个格子的状态。若$a_i$为$0$，则表示覆不覆盖均可；若为$1$，则表示一定不能覆盖；若为$2$，则表示一定要被覆盖。询问依次进行$m$次操作（$1\leq m\leq 10^9$），每次选定一个区间$[1,r]$的格子将其覆盖，使得满足$a_n$数组的所有限制条件，有多少种方案？两种方案不同，当且仅当存在某次操作覆盖的区间不同。如果格子可以被覆盖，则可以被覆盖多次。

如图例（第一张图和第四张图算不同方案，因为步骤1覆盖的区间不同。）：

提示：考虑容斥原理，使用动态规划求出每种权值的贡献次数。

试补全程序。

#include <iostream>
using namespace std;

const int MAXN = 100 + 3;
const int MAXM = 1e4 + 3;
const int MOD = 1e9 + 7;
int F[2][MAXN][MAXM], A[MAXN];

int power(int a, int b) {
    int r = 1;
    while (b) {
        if (b & 1) r = 1ll * r * a % MOD;
        b >>= 1, ①;
    }
    return r;
}

int main() {
    int n, m;
    cin >> n >> m;
    int h = n * (n + 1) / 2;
    for (int i = 1; i <= n; i++)
        cin >> A[i];
    ②;
    F[0][0][0] = 1;
    for (int i = 1; i <= n + 1; i++)
        if (A[i] == 1 || A[i] == 2) {
            for (int j = i - 1; j >= 0; j--) {
                int c = ③;
                int g = ④;
                for (int k = h; k >= g; --k) {
                    F[0][i][k] = (F[0][i][k] + F[0 ^ c][j][k - g]) % MOD;
                    F[1][i][k] = (F[1][i][k] + F[1 ^ c][j][k - g]) % MOD;
                }
                if (A[j] == 1) break;
            }
        }
    int ans = 0;
    for (int i = 0; i <= h; i++) {
        ans = (ans + 1ll * F[0][n + 1][i] * power(i, m)) % MOD;
        ans = (ans + 1ll * ⑤ * power(i, m)) % MOD;
    }
    cout << ans << endl;
    return 0;
}