第一次写树状数组，希望莫得问题QAQ

题目

题目描述：
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>小专栏。

看题目

  1. 那首先我们就来看题目吧：我们题目要求你我都能觉得我有优势的场景。
  2. 那么如果我把其中一个比赛进行排序（就是我们已经可以用序号得到他们的胜负顺序），那么另外一组只要求逆序数就行了对吧。
  3. 但是这里有三场比赛，单纯的求逆序数当然是不行的。因为多了一场比赛的可能性。
  4. 而且苣苣也说了：所以把三种都算出来，再除个二就好了。

算法讲解

  1. 我们大家现在都应该已经略微了解了树状数组，那么我没有很多可以多说的：就是求三次逆序数呗。
  2. 那么逆序数又该怎么求呢？
  3. 首先说到逆序数，大家应该都会想到冒泡排序，归并排序：都是和排序前后的数据移动位置和距离有关。树状数组求逆序数也不例外。
  4. ————————————————————我们先忘了树状数组啥的，先来看方法————————————————————
  5. 我们可以逐步把每个数加到原数组里面去，并同时累计在这一步时，判断这个时候有多少个数在自己后面。
  6. 这里看一下图：
      
  7. 我们就能知道，我们每次更新这个数组就可以算出每个数后面有多少个比他小的，加起来就好了（这里说的比他小是指原来的数组下标小）。
  8. ————————————————————那我们再回过来看树状数组————————————————————
  9. 我们用树状数组就是为了做标记和计算后面到底有多少个数呗。
  10. 我们用到树状数组的区间增删和区间查找就可以了。

算法操作

  1. 所以我们这里就专门讲一下该怎么操作吧。
  2. 和我们上面说的一样，我们当然要对一个成绩进行排序，再对另外一个数组求逆序数（设两场比赛为：a，b）。
  3. 首先我们对a排序的同时把b排序后的位置保存下来。因为我们只要b在a排序后的位置，而且b不大，直接来一遍桶排序就好了： 
    for (int i = 1; i <= n; i++) tmp[a[i]] = b[i];//桶排序把b排到，a排序后的对应位置上
  4. 排完了序就是计算逆序数了。按照我们上面的说法，我们要对每一次的数进行按位摆放与对后面求和。
  5. 按位摆放自然就是在原数组的位置上+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;
}
//计算逆序数的函数
  6. 这样我们就把答案累加出来了。

打代码

  1. 所以代码就是：
  2. 先保存三个数组。
  3. 然后对每两个数组求出逆序数。
  4. 最后加起来除二输出就好了。
  5. 看下面完整代码趴~

树状数组

  • 树状数组：顾名思义就是用数组表示出来的一颗树。

树状数组的作用

  1. 首先我们要知道这棵树有什么作用：简单来说作用就是用来维护并计算一段区间的值。
  2. 可以对某一个位置上的数进行增删查的操作（既然可以某个位置，当然可以增删查某个区间）。
  3. 查某个区间就是求出这个区间的区间和。

树状数组的构成

  1. 我们的树状数组是用二进制的规律构成的。
  2. 我们先把树状数组的图画出来看一下：
  3. 我们可以发现，所有二的倍数的点都是一个总的根节点。
  4. 所以C[i] = A[i - 2k+1] + A[i - 2k+2] + ... + A[i]（用C表示树状数组，A表示原数组）就是树状数组每一个数的求法。
  5. 从这里也可以看得出来，我们的树状数组和二进制有关系的。尤其是奇数节点都是表示自己的叶子结点。

树状数组的构建

  1. 说到构建，我们先来看一下每一项的情况：
    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];
  2. 从这里，这个是树状数组的算术表示，我们从这里也能看出，原数组中的每一个数据再树状数组中的分部都是有规律的。
  3. 规律何在？：相同的数据都相隔2k，如果用代码来表示就是： 
    void add(int pos, int x) {
    while (pos <= n) {
        sum[pos] += x;
        pos += lowbit(pos);//累加得到树状数组下一位
    }
}
//这是对树状数组对应位置上面加一个原数组pos位置的数据
//这个操作对原数组的每个位置上面进行一遍操作就可以了

树状数组的增删查找

  1. 首先数组的增加删除和上面的初始化是一样的：因为初始化的原理也就是在原来树状数组为0的基础上面增加一个数据。
  2. 同样是对原数组增加或删除一个数据（删除的话加负数也是一样的）： 
    void add(int pos, int x) {
    while (pos <= n) {
        sum[pos] += x;
        pos += lowbit(pos);//累加得到树状数组下一位
    }
}
  3. 接下来就是我们大家最关心的查找了：我们如何查找一个区块或一个区间的值呢？
  4. 其实和我们构建树状数组是一个类似的过程，不过就是反过来，因为我们构建是从前往后按位摆放累加。我们查找就是从查找值按二进制拆分二进制的每一位进行计算。
  5. 我先摆出代码来让大家理解一下： 
    ll quary(int pos) {
    ll ans = 0;
    while (pos) {
        ans += sum[pos];
        pos -= lowbit(pos);//去掉最低位，和累加是反操作
    }
    return ans;
}
//这样可以求出从1~pos之间的和
  6. 我们可以简单的理解为，我们如果对每一个位置进行一遍这个操作，放到一个数组里面就是一个前缀和数组。
  7. 那我们求一个区间的和或者求某个位置的值不就是易如反掌了吗。

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;
}
//函数区