信息奥赛题单

发布日期: 2023-11-14

文章字数: 5.3k

阅读时长: 24 分

阅读次数:

树状数组

题单 🧑🏻‍💻

题目来源	题目名称	题目链接	备注	难度
洛谷 - P3374	【模板】树状数组 1	链接🔗	树状数组 + 区间和	🟢
HDU - 1166	敌兵布阵	链接🔗	树状数组 + 区间和	🟢
洛谷 - P3368	【模板】树状数组 2	链接🔗	树状数组 + 差分	🟢
AcWing 243	楼兰图腾	链接🔗	树状数组 + 逆序对	🟢
洛谷 - P1908	逆序对	链接🔗	树状数组 + 离散化	🟢
AtCoder ABC221E	LEQ	链接🔗	树状数组 + 逆元	🟡

题解 🚀

【模板】树状数组 1

题目信息 📚

【题目名称】洛谷 P3374 - 【模板】树状数组 1

【题目描述】

如题，已知一个数列，你需要进行下面两种操作：

将某一个数加上 $x$
求出某区间每一个数的和

【输入】

第一行包含两个正整数 $n,m$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 个整数，表示一个操作，具体如下：

1 x k 含义：将第 $x$ 个数加上 $k$
2 x y 含义：输出区间 $[x,y]$ 内每个数的和

【输出】

输出包含若干行整数，即为所有操作 $2$ 的结果。

【数据范围】

对于 $30%$ 的数据，$1 \le n \le 8$，$1\le m \le 10$；

对于 $70%$ 的数据，$1\le n,m \le 10^4$；

对于 $100%$ 的数据，$1\le n,m \le 5\times 10^5$。

数据保证对于任意时刻，$a$ 的任意子区间（包括长度为 $1$ 和 $n$ 的子区间）和均在 $[-2^{31}, 2^{31})$ 范围内。

【输入样例】

【输出样例】

14
16

【原题链接】

https://www.luogu.com.cn/problem/P3374

题目解析 🍉

【题目分析】

树状数组模版题（单点更新 + 区间查询）

【C++ 代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
int n, m, op, x, y;
int a[N], tr[N];  // a数组存储原始数据，tr数组为树状数组

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

// 单点更新a[x] + c
void update(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

// 前缀和查询[1, x]
int query(int x) {
    int ans = 0;
    for (int i = x; i; i -= lowbit(i)) ans += tr[i];
    return ans;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> n >> m;
    // 读入n个数，并且利用n次单点更新来建立tr数组
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        update(i, a[i]);
    }

    // 读入m个操作：单调更新/查询
    for (int i = 1; i <= m; i++) {
        cin >> op >> x >> y;
        if (op == 1)
            update(x, y);
        else
            cout << query(y) - query(x - 1) << endl;
    }

    return 0;
}

敌兵布阵

题目信息 📚

【题目名称】HDU 1166 - 敌兵布阵

【题目描述】

C 国的死对头A国这段时间正在进行军事演习，所以 C国间谍头子 Derek 和他手下 Tidy 又开始忙乎了。A国在海岸线沿直线布置了 $N$ 个工兵营地，Derek 和 Tidy 的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数 C国都掌握的一清二楚，每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手，但这些都逃不过C国的监视。

中央情报局要研究敌人究竟演习什么战术，所以 Tidy 要随时向 Derek 汇报某一段连续的工兵营地一共有多少人，例如 Derek 问：“Tidy, 马上汇报第 $3$ 个营地到第 $10$ 个营地共有多少人！” Tidy 就要马上开始计算这一段的总人数并汇报。

但敌兵营地的人数经常变动，而 Derek 每次询问的段都不一样，所以 Tidy 不得不每次都一个一个营地的去数，很快就精疲力尽了，Derek 对 Tidy 的计算速度越来越不满:”你个死肥仔，算得这么慢，我炒你鱿鱼！” Tidy 想：“你自己来算算看，这可真是一项累人的工作!我恨不得你炒我鱿鱼呢！”无奈之下，Tidy 只好打电话向计算机专家 Windbreaker 求救, Windbreaker 说：“死肥仔，叫你平时做多点acm题和看多点算法书，现在尝到苦果了吧！”Tidy 说：”我知错了。。。”但 Windbreaker 已经挂掉电话了。Tidy 很苦恼，这么算他真的会崩溃的，聪明的读者，你能写个程序帮他完成这项工作吗？不过如果你的程序效率不够高的话，Tidy 还是会受到 Derek 的责骂的。

【输入】

第一行一个整数 $T$，表示有 $T$ 组数据。

每组数据第一行一个正整数 $N$（$N \leq 50000$），表示敌人有 $N$ 个工兵营地，接下来有 $N$ 个正整数, 第 $i$ 个正整数 $a_i$ 代表第 $i$ 个工兵营地里开始时有 $a_i$ 个人（$1 \leq a_i \leq 50$）。接下来每行有一条命令，命令有4种形式：

Add i j, $i$ 和 $j$ 为正整数, 表示第 $i$ 个营地增加 $j$ 个人（$j$ 不超过 $30$）
Sub i j, $i$ 和 $j$ 为正整数, 表示第 $i$ 个营地减少 $j$ 个人（$j$ 不超过 $30$）
Query i j, $i$ 和 $j$ 为正整数, $i \leq j$，表示询问第 $i$ 到第 $j$ 个营地的总人数
End 表示结束，这条命令在每组数据最后出现

每组数据最多有 $40000$ 条命令

【输出】

对第 $i$ 组数据,首先输出 Case i: 和回车

对于每个 Query 询问，输出一个整数并回车,表示询问的段中的总人数,这个数保持在 int 以内。

【输入样例】

1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End

【输出样例】

Case 1:
6
33
59

【原题链接】

https://vjudge.net/problem/HDU-1166

题目解析 🍉

【题目分析】

树状数组模版题（单点更新 + 区间查询）

【C++ 代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
int n, a, b, tmp, cnt, tr[N];

// 树状数组模版
int lowbit(int x) { return x & -x; }

// 求区间和
int sum(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

// 单点更新
void update(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

void solve() {
    // 多组测试样例，需要清空树状数组
    memset(tr, 0, sizeof tr);
    cout << "Case " << ++cnt << ":" << endl;

    // 读入初始数据，并用树状数组维护
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> tmp;
        update(i, tmp);
    }

    // 查询与更新
    string op;
    while (cin >> op && op != "End") {
        if (op == "Query") {
            cin >> a >> b;
            cout << sum(b) - sum(a - 1) << endl;
        } else if (op == "Add") {
            cin >> a >> b;
            update(a, b);
        } else if (op == "Sub") {
            cin >> a >> b;
            update(a, -b);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
    }

    return 0;
}

【模板】树状数组 2

题目信息 📚

【题目名称】洛谷 P3368 - 【模板】树状数组 2

【题目描述】

如题，已知一个数列，你需要进行下面两种操作：

将某区间每一个数加上 $x$；
求出某一个数的值。

【输入】

第一行包含两个整数 $N$、$M$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $N$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i $ 项的初始值。

接下来 $M$ 行每行包含 $2$ 或 $4$个整数，表示一个操作，具体如下：

操作 $1$：格式：1 x y k 含义：将区间 $[x,y]$ 内每个数加上 $k$；

操作 $2$：格式：2 x 含义：输出第 $x$ 个数的值。

【输出】

输出包含若干行整数，即为所有操作 $2$ 的结果。

【数据范围】

对于 $30%$ 的数据：$N\le8$，$M\le10$；

对于 $70%$ 的数据：$N\le 10000$，$M\le10000$；

对于 $100%$ 的数据：$1 \leq N, M\le 500000$，$1 \leq x, y \leq n$，保证任意时刻序列中任意元素的绝对值都不大于 $2^{30}$。

【输入样例】

【输出样例】

6
10

【原题链接】

https://www.luogu.com.cn/problem/P3368

题目解析 🍉

【题目分析】

树状数组实现差分（区间修改 + 单点查询）

【C++ 代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
int n, m, op, l, r, c, t;
int a[N], tr[N];

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

// 单点更新
int update(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

// 前缀和查询
int query(int x) {
    int ans = 0;
    for (int i = x; i; i -= lowbit(i)) ans += tr[i];
    return ans;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> n >> m;
    // 读取n个数，并利用单点更新，将其差分数组b存入树状数组
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        update(i, a[i] - a[i - 1]);
    }
    
    // m次操作
    // 若不借助树状数组，区间修改复杂度为O(1)，单点查询复杂度为O(n)
    // 若借助树状数组，两者复杂度均变为O(logn)
    for (int i = 1; i <= m; i++) {
        cin >> op;
        if (op == 1) {
            cin >> l >> r >> c;
            update(l, c);
            update(r + 1, -c);
        } else {
            cin >> t;
            // 查询a[t]，需要求b[1]~b[t]的前缀和，可以用树状数组的query实现
            cout << query(t)<< endl;
        }
    }

    return 0;
}

楼兰图腾

题目信息 📚

【题目名称】AcWing 243 - 楼兰图腾

【题目描述】

在完成了分配任务之后，西部 314 来到了楼兰古城的西部。

相传很久以前这片土地上(比楼兰古城还早)生活着两个部落，一个部落崇拜尖刀(V)，一个部落崇拜铁锹(∧)，他们分别用 V 和 ∧ 的形状来代表各自部落的图腾。

西部 314 在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了 $n$ 个点，经测量发现这 $n$ 个点的水平位置和竖直位置是两两不同的。

西部 314 认为这幅壁画所包含的信息与这 $n$ 个点的相对位置有关，因此不妨设坐标分别为 $(1,y_1),(2,y_2),…,(n,y_n)$，其中 $y_1∼y_n$ 是 $1$ 到 $n$ 的一个排列。

西部 314 打算研究这幅壁画中包含着多少个图腾。

如果三个点 $(i,y_i),(j,y_j),(k,y_k)$ 满足 $1 \le i<j<k \le n$ 且 $y_i>y_j,y_j<y_k$，则称这三个点构成 V 图腾;

如果三个点 $(i,y_i),(j,y_j),(k,y_k)$ 满足 $1 \le i<j<k \le n$ 且 $y_i<y_j,y_j>y_k$，则称这三个点构成 ∧ 图腾;

西部 314 想知道，这 $n$ 个点中两个部落图腾的数目。

因此，你需要编写一个程序来求出 V 的个数和 ∧ 的个数。

【输入】

第一行一个数 $n$。

第二行是 $n$ 个数，分别代表 $y_1，y_2,…,y_n$。

【输出】

两个数，中间用空格隔开，依次为 V 的个数和 ∧ 的个数。

【输入样例】

5
1 5 3 2 4

【输出样例】

3 4

【数据范围】

对于所有数据，$n \le 200000$，且输出答案不会超过 int64。

$y_1∼y_n$ 是 $1$ 到 $n$ 的一个排列。

【原题链接】

https://www.acwing.com/problem/content/243/

题目解析 🍉

【题目分析】

本题由暴力法很容易想出思路：枚举所有中间点，统计每个中间点左右两边比它大/小的点数量，利用乘法原理累加即可得到答案。
- 时间复杂度为：$O(n^2)$ ，显然 TLE ❌
利用数状数组，优化「中间统计每个中间点左右两边比它大/小的点数量」的过程至 $2 * log(n)$
- 时间复杂度为：$O(nlogn)$ ✅

利用 树状数组求逆序对 的核心其实可以由以下两句话概括：

抽象意义上，借助桶思想，利用桶数组 b 将问题转化为单点更新、区间查询两个操作
具体操作上，利用树状数组 tr 实现桶数组 b

【C++ 代码】暴力（TLE） ❌

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL n, ans1, ans2;
int a[N];
int L_G[N], L_L[N];  // L_G -> left_greater
int R_G[N], R_L[N];  // R_L -> right_lower

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

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

    // 暴力枚举，中间点i均需存储4个信息
    // 即比i小/大的点在i的左边有多少个，i小/大的点在i的右边有多少个
    for (int i = 2; i <= n - 1; i++) {
        // 比较点i左边的点1～i-1与点i的大小
        for (int j = 1; j < i; j++) {
            if (a[j] < a[i]) L_L[i]++;
            else L_G[i]++;
        }
        // 比较点i右边的点i+1~n与点i的大小
        for (int j = i + 1; j <= n; j++) {
            if (a[j] < a[i]) R_L[i]++;
            else R_G[i]++;
        }
        // 累加以点i为中间点的图腾数量
        ans1 += (LL) L_G[i] * R_G[i];
        ans2 += (LL) L_L[i] * R_L[i];
    }
    cout << ans1 << " " << ans2 << endl;

    return 0;
}

【C++ 代码】树状数组 ✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL n, ans1, ans2;
int a[N], tr[N];
int L_G[N], L_L[N];  // L_G -> left_greater
int R_G[N], R_L[N];  // R_L -> right_lower

// 树状数组维护模版
int lowbit(int x) { return x & -x; }

// 单点更新
int update(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

// 前缀和查询
int query(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

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

    // 抽象意义上，维护一个桶数组b
    // 具体操作上，利用树状数组tr维护桶数组b
    for (int i = 1; i <= n; i++) { // 获取所有中间点的L_G, L_L
        update(a[i], 1);  // 实现"抽象"的桶数组b[a[i]] + 1（实际用tr维护）
        L_G[i] = query(n) - query(a[i]);  // 在第i个点左边，且比它大的点为sum(b[a[i]+1], b[n])
        L_L[i] = query(a[i] - 1);  // 在第i个点左边，且比它小的点为sum(b[1], b[a[i]-1])
    }

    // 获取所有中间点的R_G, R_L
    memset(tr, 0, sizeof(tr));  // 注意清空上一次的树状数组tr
    for (int i = n; i; i--) {
        update(a[i], 1);
        R_G[i] = query(n) - query(a[i]);
        R_L[i] = query(a[i] - 1);

        // 累加以当前点为中间点的答案
        ans1 += (LL) R_G[i] * L_G[i];
        ans2 += (LL) R_L[i] * L_L[i];
    }

    cout << ans1 << " " << ans2 << endl;

    return 0;
}

逆序对

题目信息 📚

【题目名称】洛谷 P1908 - 逆序对

【题目描述】

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 $a_i>a_j$ 且 $i<j$ 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

【输入】

第一行，一个数 $n$，表示序列中有 $n$个数。

第二行 $n$ 个数，表示给定的序列。序列中每个数字不超过 $10^9$。

【输出】

输出序列中逆序对的数目。

【输入样例】

6
5 4 2 6 3 1

【输出样例】

【数据范围】

对于 $25%$ 的数据，$n \leq 2500$

对于 $50%$ 的数据，$n \leq 4 \times 10^4$。

对于所有数据，$n \leq 5 \times 10^5$

请使用较快的输入输出

【原题链接】

https://www.luogu.com.cn/problem/P1908

题目解析 🍉

【题目分析】

归并排序の经典应用（具体分析见「归并排序」知识点介绍博客：信息奥赛｜归并排序🔗 / （备用）信息奥赛｜归并排序🔗）

此外，逆序对也可以像上题「楼兰图腾」那样，由 树状数组 维护。

由于此题中的 a[i] 的最大值到了 $10^9$，因此需要 离散化 后，用树状数组 tr 维护桶数组b。

【C++ 代码】归并排序 ✅

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
int n, a[N], t[N];
ll cnt;  //逆序对的数量最多约为n^2，爆int

// 归并排序统计逆序对数量
void InversionCount(int l, int r) {
    if (l >= r) return;

    //归并排序递归调用
    int mid = (l + r) / 2;
    InversionCount(l, mid);
    InversionCount(mid + 1, r);

    //对已经有序的两个序列求逆序对数量
    int p1 = l, p2 = mid + 1, p3 = l;
    while (p1 <= mid && p2 <= r) {
        if (a[p1] <= a[p2]) {
            t[p3++] = a[p1++];
        } else {
            t[p3++] = a[p2++];
            cnt = cnt + (mid - p1 + 1);  //核心代码
        }
    }

    while (p1 <= mid) t[p3++] = a[p1++];
    while (p2 <= r) t[p3++] = a[p2++];
    for (int i = l; i <= r; ++i) a[i] = t[i];
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    // 读入数据
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    // 归并排序统计逆序对数量
    InversionCount(1, n);
    cout << cnt << endl;

    return 0;
}

【C++ 代码】树状数组 ✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
int n, a[N], r[N];
vector<int> tmp;
int tr[N];

// 树状数组模版
int lowbit(int x) { return x & -x; }

// 单点更新
void update(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

// 前缀和查询
int query(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

// 离散化查询
int findi(int x) {
    return lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin() + 1;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], tmp.push_back(a[i]);

    // 由于a数组中最大的数字为1e9，故需要使用离散化
    sort(tmp.begin(), tmp.end());
    tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());

    LL cnt = 0;
    // 累加以a[i]结尾的逆序对个数
    for (int i = 1; i <= n; i++) {
        int id = findi(a[i]);  // a[i]的离散化下标
        // 单点更新
        update(id, 1);
        // 统计以该点结尾的逆序对数量
        r[id] = query(tmp.size()) - query(id);
        // 累加答案
        cnt += r[id];
    }
    // 输出答案
    cout << cnt << endl;

    return 0;
}

LEQ

题目信息 📚

【题目名称】AtCoder ABC221E - LEQ

【题目描述】

Given is a sequence of $N$ integers: $A = (A_1, A_2, \dots, A_N)$.

Find the number of (not necessarily contiguous) subsequences $A’=(A’_1,A’_2,\ldots,A’_k)$ of length at least $2$ that satisfy the following condition:

$A’_1 \leq A’_k$.

Since the count can be enormous, print it modulo $998244353$.

Here, two subsequences are distinguished when they originate from different sets of indices, even if they are the same as sequences.

【输入】

Input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

【输出】

Print the number of (not necessarily contiguous) subsequences $A’=(A’_1,A’_2,\ldots,A’_k)$ of length at least $2$ that satisfy the condition in Problem Statement.

【数据范围】

$2 \leq N \leq 3 \times 10^5$

$1 \leq A_i \leq 10^9$

All values in input are integers.

【输入样例1】

3
1 2 1

【输出样例1】

【输入样例2】

3
1 2 2

【输出样例2】

【输入样例1】

3
3 2 1

【输出样例1】

【输入样例2】

10
198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501

【输出样例2】

【题目来源】

AtCoder ABC221E

题目解析 🍉

【题目分析】

官方题解传送门：https://atcoder.jp/contests/abc221/tasks/abc221_e/editorial

本题需要的知识点：子序列 + 离散化 + 树状数组 + 快速幂 + 求逆元

子序列
- $n$ 个元素组成的序列，其子序列个数有：$2^n$
- $n$ 个元素组成的序列中，下标为 $[i, j]$ 的区间，其子序列个数为：$2^{j - i + 1}$
- $n$ 个元素组成的序列中，下标为 $[i, j]$ 的区间，若保留a[i], a[j]，其子序列个数为：$2^{j - i - 1}$
离散化
- 由于 a 数组的值域较大，故需要进行离散化
树状数组
- 利用数状数组维护
快速幂
- 使用经典快速幂模版即可
求逆元
- 【乘法逆元费马小定理】 https://www.bilibili.com/video/BV1RD4y1i7PK/?share_source=copy_web&vd_source=33934722b558a5cefa750c1a9be72249

【C++代码】✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 3e5 + 10, M = 998244353;
LL n, a[N], tr[N];
vector<LL> tmp;

// 离散化查询
LL findi(LL x) {
    return lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin() + 1;
}

// 快速幂
LL quick_power(LL base, LL power) {
    LL res = 1;
    while (power) {
        if (power & 1) res = res * base % M;
        power >>= 1;
        base = base * base % M;
    }
    return res;
}

// 树状数组模版
int lowbit(int x) { return x & -x; }

void update(int x, LL c) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] = (tr[i] % M + c % M) % M;
}

LL query(int x) {
    LL res = 0;
    for (int i = x; i; i -= lowbit(i)) res = (res % M + tr[i] % M) % M;
    return res;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], tmp.push_back(a[i]);
    // 离散化
    sort(tmp.begin(), tmp.end());
    tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());

    LL cnt = 0;
    for (int i = 1; i <= n; i++) {
        // 查询离散化后下标
        int id = findi(a[i]);

        // 计算项
        LL t = quick_power(2, i - 1) % M;
        cnt = (cnt % M + t * query(id) % M) % M;

        // 费马小定理：若a、p互质，且p为质数，则a的逆元为a^(p-2)
        // 单点更新（利用费马小定理求解逆元）
        update(id, quick_power(quick_power(2, i), M - 2));
    }
    cout << cnt << endl;

    return 0;
}

参考资料 📚

https://oi-wiki.org/ds/fenwick/

Rickyの水果摊

https://ricky2333.github.io/2023/11/14/xin-xi-ao-sai-ti-dan-shu-zhuang-shu-zu/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Rickyの水果摊 !

信息奥赛 C++ 高级数据结构树状数组

信息奥赛｜线段树

2023-11-14 信息奥赛知识点

信息奥赛 C++ 高级数据结构线段树

信息奥赛｜树状数组

2023-11-14 信息奥赛知识点

信息奥赛 C++ 高级数据结构树状数组

信息奥赛题单｜树状数组

树状数组

题单 🧑🏻‍💻

题解 🚀

【模板】树状数组 1

题目信息 📚

【题目名称】洛谷 P3374 - 【模板】树状数组 1

【题目描述】

【输入】

【输出】

【数据范围】

【输入样例】

【输出样例】

【原题链接】

题目解析 🍉

【题目分析】

【C++ 代码】

敌兵布阵

题目信息 📚

【题目名称】HDU 1166 - 敌兵布阵

【题目描述】

【输入】

【输出】

【输入样例】

【输出样例】

【原题链接】

题目解析 🍉

【题目分析】

【C++ 代码】

【模板】树状数组 2

题目信息 📚

【题目名称】洛谷 P3368 - 【模板】树状数组 2

【题目描述】

【输入】

【输出】

【数据范围】

【输入样例】

【输出样例】

【原题链接】

题目解析 🍉

【题目分析】

【C++ 代码】

楼兰图腾

题目信息 📚

【题目名称】AcWing 243 - 楼兰图腾

【题目描述】

【输入】

【输出】

【输入样例】

【输出样例】

【数据范围】

【原题链接】

题目解析 🍉

【题目分析】

【C++ 代码】暴力（TLE） ❌

【C++ 代码】树状数组 ✅

逆序对

题目信息 📚

【题目名称】洛谷 P1908 - 逆序对

【题目描述】

【输入】

【输出】

【输入样例】

【输出样例】

【数据范围】

【原题链接】

题目解析 🍉

【题目分析】

【C++ 代码】归并排序 ✅

【C++ 代码】树状数组 ✅

LEQ

题目信息 📚

【题目名称】AtCoder ABC221E - LEQ

【题目描述】

【输入】

【输出】

【数据范围】

【输入样例1】

【输出样例1】

【输入样例2】