【每日一题】Context
Contest
https://ac.nowcoder.com/acm/problem/13947
第一次写树状数组，希望莫得问题QAQ
题目描述：
n支队伍一共参加了三场比赛。
一支队伍x认为自己比另一支队伍y强当且仅当x在至少一场比赛中比y的排名高。
求有多少组(x,y)，使得x自己觉得比y强，y自己也觉得比x强。
(x, y), (y, x)算一组。
输入描述：
输出描述：
输出一个整数表示满足条件的(x,y)数；64bit请用lld
题目
题目描述：n支队伍一共参加了三场比赛。
一支队伍x认为自己比另一支队伍y强当且仅当x在至少一场比赛中比y的排名高。
求有多少组(x,y)，使得x自己觉得比y强，y自己也觉得比x强。
(x, y), (y, x)算一组。
输入描述：
第一行一个整数n，表示队伍数； 接下来n行，每行三个整数a[i], b[i], c[i]。
分别表示i在第一场、第二场和第三场比赛中的名次；n 最大不超过200000
输出一个整数表示满足条件的(x,y)数；64bit请用lld
解析
知识点
- 这道题其实就是求逆序数的题目，但是这道题很复杂，所以我们至少也要用树状数组做，就会比较简单（第一次写树状数组orz）。
- 如果树状数组基础知识不清楚可移步下面<h3>小专栏。
看题目
- 那首先我们就来看题目吧：我们题目要求你我都能觉得我有优势的场景。
- 那么如果我把其中一个比赛进行排序（就是我们已经可以用序号得到他们的胜负顺序），那么另外一组只要求逆序数就行了对吧。
- 但是这里有三场比赛，单纯的求逆序数当然是不行的。因为多了一场比赛的可能性。
- 而且苣苣也说了：所以把三种都算出来，再除个二就好了。
算法讲解
- 我们大家现在都应该已经略微了解了树状数组，那么我没有很多可以多说的：就是求三次逆序数呗。
- 那么逆序数又该怎么求呢？
- 首先说到逆序数，大家应该都会想到冒泡排序，归并排序：都是和排序前后的数据移动位置和距离有关。树状数组求逆序数也不例外。
- ————————————————————我们先忘了树状数组啥的，先来看方法————————————————————
- 我们可以逐步把每个数加到原数组里面去，并同时累计在这一步时，判断这个时候有多少个数在自己后面。
- 这里看一下图：
- 我们就能知道，我们每次更新这个数组就可以算出每个数后面有多少个比他小的，加起来就好了（这里说的比他小是指原来的数组下标小）。
- ————————————————————那我们再回过来看树状数组————————————————————
- 我们用树状数组就是为了做标记和计算后面到底有多少个数呗。
- 我们用到树状数组的区间增删和区间查找就可以了。
算法操作
- 所以我们这里就专门讲一下该怎么操作吧。
- 和我们上面说的一样，我们当然要对一个成绩进行排序，再对另外一个数组求逆序数（设两场比赛为：a，b）。
- 首先我们对a排序的同时把b排序后的位置保存下来。因为我们只要b在a排序后的位置，而且b不大，直接来一遍桶排序就好了：
for (int i = 1; i <= n; i++) tmp[a[i]] = b[i];//桶排序把b排到，a排序后的对应位置上
- 排完了序就是计算逆序数了。按照我们上面的说法，我们要对每一次的数进行按位摆放与对后面求和。
- 按位摆放自然就是在原数组的位置上+1，并加到树状数组的对应位置上面去。求和就是函数对区间查找呗（类似于前缀和）：
ll calc(int a[], int b[]) { memset(sum, 0, sizeof sum); for (int i = 1; i <= n; i++) tmp[a[i]] = b[i];//桶排序把b排到，a排序后的对应位置上 ll ans = 0; for (int i = 1; i <= n; i++) { ans += quary(n) - quary(tmp[i]);//计算该位后面有多少比他小的 add(tmp[i], 1);//在排序后的数组位置上加一 } return ans; } //计算逆序数的函数 - 这样我们就把答案累加出来了。
打代码
- 所以代码就是：
- 先保存三个数组。
- 然后对每两个数组求出逆序数。
- 最后加起来除二输出就好了。
- 看下面完整代码趴~
树状数组
- 树状数组：顾名思义就是用数组表示出来的一颗树。
树状数组的作用
- 首先我们要知道这棵树有什么作用：简单来说作用就是用来维护并计算一段区间的值。
- 可以对某一个位置上的数进行增删查的操作（既然可以某个位置，当然可以增删查某个区间）。
- 查某个区间就是求出这个区间的区间和。
树状数组的构成
- 我们的树状数组是用二进制的规律构成的。
- 我们先把树状数组的图画出来看一下：
- 我们可以发现，所有二的倍数的点都是一个总的根节点。
- 所以C[i] = A[i - 2k+1] + A[i - 2k+2] + ... + A[i]（用C表示树状数组，A表示原数组）就是树状数组每一个数的求法。
- 从这里也可以看得出来，我们的树状数组和二进制有关系的。尤其是奇数节点都是表示自己的叶子结点。
树状数组的构建
- 说到构建，我们先来看一下每一项的情况：
C[1] = A[1];
C[2] = A[1] + A[2];
C[3] = A[3];
C[4] = A[1] + A[2] + A[3] + A[4];
C[5] = A[5];
C[6] = A[5] + A[6];
C[7] = A[7];
C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8];
- 从这里，这个是树状数组的算术表示，我们从这里也能看出，原数组中的每一个数据再树状数组中的分部都是有规律的。
- 规律何在？：相同的数据都相隔2k，如果用代码来表示就是：
void add(int pos, int x) { while (pos <= n) { sum[pos] += x; pos += lowbit(pos);//累加得到树状数组下一位 } } //这是对树状数组对应位置上面加一个原数组pos位置的数据 //这个操作对原数组的每个位置上面进行一遍操作就可以了
树状数组的增删查找
- 首先数组的增加删除和上面的初始化是一样的：因为初始化的原理也就是在原来树状数组为0的基础上面增加一个数据。
- 同样是对原数组增加或删除一个数据（删除的话加负数也是一样的）：
void add(int pos, int x) { while (pos <= n) { sum[pos] += x; pos += lowbit(pos);//累加得到树状数组下一位 } } - 接下来就是我们大家最关心的查找了：我们如何查找一个区块或一个区间的值呢？
- 其实和我们构建树状数组是一个类似的过程，不过就是反过来，因为我们构建是从前往后按位摆放累加。我们查找就是从查找值按二进制拆分二进制的每一位进行计算。
- 我先摆出代码来让大家理解一下：
ll quary(int pos) { ll ans = 0; while (pos) { ans += sum[pos]; pos -= lowbit(pos);//去掉最低位，和累加是反操作 } return ans; } //这样可以求出从1~pos之间的和 - 我们可以简单的理解为，我们如果对每一个位置进行一遍这个操作，放到一个数组里面就是一个前缀和数组。
- 那我们求一个区间的和或者求某个位置的值不就是易如反掌了吗。
AC代码
#include <iostream>
#include <string.h>
using namespace std;
typedef long long ll;
#define lowbit(x) x & -x;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
const int MAX = 2e5 + 7;
int a[MAX], b[MAX], c[MAX];//三次比赛的数组
int sum[MAX], tmp[MAX];//在b排成顺序下构成的树状数组（统计每一位的个数），排序后的b数组
int n;//队伍数量和答案统计
//全局变量区
void add(int pos, int x);//给原数组中的第pos位加一（在树状数组中在相应位置上加一）
ll quary(int pos);//计算从原数组中1~pos位之和
ll calc(int a[], int b[]);//计算逆序数
//函数预定义区
int main() {
IOS;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];
ll ans = calc(a, b) + calc(a, c) + calc(b, c);//a对bc的倒序数和b对c的倒序数
ans >>= 1;//总数的一半
cout << ans << endl;
return 0;
}
void add(int pos, int x) {
while (pos <= n) {
sum[pos] += x;
pos += lowbit(pos);//累加得到树状数组下一位
}
}
ll quary(int pos) {
ll ans = 0;
while (pos) {
ans += sum[pos];
pos -= lowbit(pos);//去掉最低位，和累加是反操作
}
return ans;
}
ll calc(int a[], int b[]) {
memset(sum, 0, sizeof sum);
for (int i = 1; i <= n; i++) tmp[a[i]] = b[i];//桶排序把b排到，a排序后的对应位置上
ll ans = 0;
for (int i = 1; i <= n; i++) {
ans += quary(n) - quary(tmp[i]);//计算该位后面有多少比他小的
add(tmp[i], 1);//在排序后的数组位置上加一
}
return ans;
}
//函数区每日一题 文章被收录于专栏
憨憨的专栏
CVTE公司福利 269人发布
查看6道真题和解析