总体评价：难度适中，一小时ak。重点考察了树状数组。力扣的树状数组题也很少，可能稍有超纲。但树状数组是一种码量极少的数据结构，后面给出了几道入门题，可以学习一下。

第一题

概述：计算所点菜品的总价，然后减去满减和红包。

输入描述

第一行输入一个正整数 $n$，代表菜品总数。
第二行输入 $n$ 个正整数 $a_i$，代表每道菜的价格。
第三行输入两个正整数 $x$ 和 $y$，$x$ 代表满减的价格，$y$ 代表红包的价格。
$$\begin{gathered} 1\le n\le 10^5 \\ 1\le x,y,a_i\le 10^9 \end{gathered}$$
保证所有 $a_i$ 的和大于 $x+y$ ，保证会用到满减。

输出描述

一个正整数，代表小美最终应付的钱数。

示例 1

输入
4
10 20 10 20
25 10
输出
25

说明
四个菜一共 60 元，满减减掉了 25 元，再用一个 10 元的红包，因此需要付 25 元。

解题思路

保证可以满减，只需要判断减完不是负数就行了。

通过代码

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

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v){ os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

using i64 = long long;
using pii = pair<int, int>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n; cin >> n;
    i64 s = 0, a, b;
    for (int i = 0; i < n; ++i) {
        i64 x; cin >> x;
        s += x;
    }
    cin >> a >> b;

    cout << max(0LL, s - a - b);

    return 0;
}

第二题

小明定义以下三种单词是合法的：

1. 所有字母都是小写。例如：good
2. 所有字母都是大写。例如：APP
3. 第一个字母大写，后面所有字母都是小写。例如：Alice

小明每次操作可以修改任意一个字符的大小写。小明想知道最少操作几次可以使得单词变成合法的？

输入描述

一个仅由大写字母和小写字母组成的字符串，长度不超过 $10^5$。

输出描述

一个整数，代表操作的最小次数。

示例 1

输入
AbC
输出
1

说明
变成 ABC 或者 Abc 均可。只需要一次操作。

解题思路

分别对三种情况进行统计取最小值就可以了。

通过代码

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

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v){ os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

using i64 = long long;
using pii = pair<int, int>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    string s; cin >> s;

    auto isLower = [](char c) { return c >= 'a' and c <= 'z'; };
    auto isUpper = [](char c) { return c >= 'A' and c <= 'Z'; };

    int a = !isLower(s[0]), b = !isUpper(s[0]), c = !isUpper(s[0]);
    for (int i = 1; i < s.size(); ++i) {
        a += isUpper(s[i]);
        b += isLower(s[i]);
        c += isUpper(s[i]);
    }

    cout << min(a, min(b, c));

    return 0;
}

第三题

概述：小明拿到了一个数组，他每次操作会将除了第 $x$ 个元素的其余元素翻倍，一共操作了 $q$ 次。请你帮小明计算操作结束后所有元素之和。由于答案过大，请对 $10^9+7$ 取模。

输入描述

第一行输入两个正整数 $n,q$，代表数组的大小和操作次数。
第二行输入 $n$ 个正整数 $a_i$，代表数组的元素。
第三行输入一个正整数 $q$，代表操作的次数。
接下来的 $q$ 行，每行输入一个正整数 $x_i$，代表第 $i$ 次操作未被翻倍的元素。
$$\begin{gathered} 1\le n,q\le 10^5 \\ 1\le x_i\le n \\ 1\le a_i\le 10^9 \end{gathered}$$

输出描述

一个整数，代表操作结束后所有元素之和模 $10^9+7$ 的值。

示例 1

输入
4 2
1 2 3 4
1
2
输出
34

说明
第一次操作后，数组变成[1,4,6,8]
第二次操作后，数组变成[2,4,12,16]
所有元素之和为 34。

解题思路

可以统计出每个元素没被翻倍的次数，记为cnt[i]

那原来的每个数a[i]就变为了a[i] * pow(2, q - cnt[i]) % mod

因为q - cnt[i]的范围是 $10^5$ ，所以这里要用快速幂

最后求和取模就行了

通过代码

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

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v){ os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

using i64 = long long;
using pii = pair<int, int>;

const int mod = 1e9+7;

int qpow(i64 a, int n) {
    i64 ans = 1;
    while (n) {
        if (n & 1) ans = ans * a % mod;
        n >>= 1;
        a = a * a % mod;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n, q; cin >> n >> q;
    i64 a[n];
    vector<int> cnt(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    for (int i = 0; i < q; ++i) {
        int x; cin >> x;
        cnt[x - 1]++;
    }

    i64 ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = (ans + a[i] * qpow(2, q - cnt[i]) % mod) % mod;
    }

    cout << ans;


    return 0;
}

第四题

概述：小明要求出一个数组的所有子数组的众数之和，定义子数组的众数为出现次数最多的那个数。如果有多个数出现次数最多，那么众数是其中最小的那个数。

输入描述

第一行输入一个正整数 $n$，代表数组的大小。
第二行输入 $n$ 个正整数 $a_i$，代表数组的元素。
$$\begin{gathered} 1\le n\le 200000 \\ 1\le a_i\le 2 \end{gathered}$$

输出描述

一个正整数，代表所有区间的众数之和。

示例 1

输入
3
2 1 2
输出
9

说明
[2],[2,1,2],[2]的众数是 2。
[2,1],[1],[1,2]的众数是 1。
因此答案是 9。

解题思路

1. $a_i$ 的取值只有 $1$ 或 $2$
2. 像这种只有两种取值的问题，一种常见的技巧是转为 $1$ 和 $-1$ （类似技巧：1124. 表现良好的最长时间段）
3. 根据上面的技巧：数组的众数是 $1$ 等价于 数组的和不小于 $0$
4. 问题已经转化为统计有多少个子数组的和不小于 $0$（那其它的就是众数为 $2$ 的数组了）
5. 求子数组的和，一般会想到前缀和
6. 那当前的思路就是在遍历当前元素的时候，要知道前面有几个前缀和 $\le$ 当前的前缀和
7. 这里其实用下标为前缀和，权值为 $1$ 的树状数组就可以统计某个取值范围内，有多少个前缀和了
8. 因为前缀和可能为负数，所以这里要对树状数组的下标做适当的偏移

通过代码

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

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v){ os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

using i64 = long long;
using pii = pair<i64, i64>;

const i64 N = 2e5+10;
i64 tr[2 * N + 10];

i64 lowbit(i64 x) {
    return x & -x;
}

i64 query(i64 x) {
    i64 res = 0;
    for (i64 i = x; i; i -= lowbit(i)) {
        res += tr[i];
    }
    return res;
}

void add(i64 x) {
    for (i64 i = x; i <= 2 * N; i += lowbit(i)) {
        tr[i] += 1;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    i64 n; cin >> n;

    i64 s = 0, ans = 0;
    add(N);	// 偏移 其实是前缀和为0
    for (int i = 0; i < n; ++i) {
        int x; cin >> x;
        s += (x == 1 ? 1 : -1);
        ans += query(s + N);
        add(s + N);
    }

    i64 total = (n + 1) * n >> 1;	// 子数组的总数量
    cout << ans + 2 * (total - ans);

    return 0;
}

第五题

概述：小明拿到了一个排列，他定义 $f(i)$ 为：将第 $i$ 个元素取反后，形成的数组的逆序对数量。小明希望你求出 $f(1)$ 到 $f(n)$ 的值。（排列是指一个长度为 $n$ 的数组，$1$ 到 $n$ 每个元素恰好出现了一次）

输入描述

第一行输入一个正整数 $n$，代表排列的大小。
第二行输入 $n$ 个正整数 $a_i$，代表排列的元素。
$$\begin{gathered} 1\le n\le 200000 \\ 1\le a_i\le n \end{gathered}$$
输出描述

输出 $n$ 个整数，第 $i$ 个整数是 $f(i)$ 的值。

示例 1

输入
3
1 2 3
输出
0 1 2

说明
第一个元素取反，数组将变成[-1,2,3]，逆序对数量为 0。
第二个元素取反，数组将变成[1,-2,3]，逆序对数量为 1。
第三个元素取反，数组将变成[1,2,-3]，逆序对数量为 2。

解题思路

1. 首先要求出来原来数组的逆序对数量（记为ans），常见的方法是树状数组或者归并排序

统计逆序对有两种遍历方法，一种是看前面的元素有几个比当前元素大（记为pre[i]），或者是看后面的元素有几个比当前元素小(记为suf[i])。

2. 在遍历每个元素求 $f(i)$ 的时候，要分别求出当前元素取反之后，对前面元素和后面元素的影响，$f(i)$ = ans + 对前面的影响 + 对后面的影响

• 对后面元素：取负之后，后面的元素一定比当前元素大，相比原来少了suf[i]个逆序对，所以ans要减去suf[i]；
• 对前面元素：取负之后，前面的元素一定比当前元素小，所以现在一定形成了i-1个逆序对，再减去pre[i]，就求出变化量了。

3. 所以 $f(i)$ = ans + ((i - 1) - pre[i]) + (-suf[i])

4. 求pre[i]和suf[i]的过程要用到树状数组

通过代码

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

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v){ os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

using i64 = long long;
using pii = pair<i64, i64>;

const i64 N = 2e5+10;
i64 tr[N], a[N], pre[N], suf[N];

i64 lowbit(i64 x) {
    return x & -x;
}

i64 query(i64 x) {
    i64 res = 0;
    for (i64 i = x; i; i -= lowbit(i)) {
        res += tr[i];
    }
    return res;
}

void add(i64 x) {
    for (i64 i = x; i < N; i += lowbit(i)) {
        tr[i] += 1;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    i64 n; cin >> n;

    i64 ans = 0;
    for (i64 i = 1; i <= n; ++i) {
        i64 x; cin >> x;
        a[i] = x;
        ans += (pre[i] = query(n) - query(x));	// 求pre[i]的同时，求出原数组的逆序对数量
        add(x);
    }

    memset(tr, 0, sizeof tr);
    for (i64 i = n; i >= 1; i--) {
        suf[i] = query(a[i]);
        add(a[i]);
    }
	// ans + 对前缀的影响 + 对后缀的影响
    for (i64 i = 1; i <= n; ++i) {
        cout << ans + (i - 1) - pre[i] - suf[i] << ' ';
    }

    return 0;
}

这里给出一些关于树状数组的入门题

模板题：307. 区域和检索 - 数组可修改
下标偏移：315. 计算右侧小于当前元素的个数
离散化：493. 翻转对