正经题解｜眼红的同学

题目解析

题干信息很简单，看到数据量之后就不简单了。在数据量小的时候可以使用双层循环暴力的方法来求答案。显然对于这道题而言 $O(n^2)$ 是完全过不去的。

前置知识：

1. 使用树状数组求逆序对。
2. 会归并排序等分治算法。

考虑使用分治算法来解决，这是一道经典的三维偏序问题。对于这种坐标相关题目，一个很常见的方法是先对其中一个纬度进行排序。这样子控制一个纬度之后再去查找速度就会快很多。

例如如果控制语文成绩这个维度，按照从大到小的顺序排序后可以得出以下结论：

第 $i$ 位同学的嫉妒值一定只会被前 $i-1$ 位同学所影响，排在 $i$ 后面的所有学生都不会贡献为第 $i$ 为同学贡献嫉妒值。

接下来的做法和分治逆序对很像，每次将所有的数字分成两半，以任意一个 $k$ 为分界线，保证第 $k$ 个学生的语文成绩低于第 $k+1$ 个学生的成绩即可。直至区间的长度为 $1$。

由于前半部分的任意 $x$ 肯定比后半部分的任意 $x$ 要大，可以按照数学成绩再分别被前半部分和后半部分的学生进行排序。这样子依然也不会损失单调性，只要保证前半部分 $x$ 都比后半部分 $x$ 大即可。接下来我们就可以遍历后半部分，在遍历的时候计算单个点所获得的贡献（这些贡献来自于前半部分维度）。

截至目前已经对两个维度进行排序了，最后一个维度可以使用树状数组进行维护。这部分可以借用树状数组求逆序对的思想（请自行查阅，类似于本场比赛的第四题 - 股票购买方案）。

AC代码

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

const int MAXN = 3e5 + 5;
int maximum;
int n, ans[MAXN];
int L[MAXN], R[MAXN];
int bit[MAXN << 1];
// x, y, z 记录学生成绩。
// id记录学生编号。
// ans记录学生的嫉妒值。
// val记录这个学生的最高成绩，即 max(x, y, z)。
struct student{
    int x, y, z;
    int id, ans, val;
} arr[MAXN];

// 根据第一关键字排序
bool cmp1(student a, student b){
    if (a.x != b.x) return a.x > b.x;
    if (a.y != b.y) return a.y > b.y;
    return a.z > b.z;
}

// 根据第二关键字排序。
bool cmp2(student a, student b){
    if (a.y != b.y) return a.y > b.y;
    if (a.z != b.z) return a.z > b.z;
    return a.x > b.x;
}

// 三个数取最大值。
inline int max(int a, int b, int c){
    return max(a, max(b, c));
}

// lowbit获取低位二进制1的操作。
inline int lowbit(int k) {
    return k & (-k);
}

// 数状数组但点增加操作。
void add(int x, int val){
    for (int i=x; i<=maximum; i+=lowbit(i))
        bit[i] += val;
    return ;
}

// 数状数组区间查询操作。
int query(int x){
    int ans = 0;
    for (int i=x; i; i-=lowbit(i)) 
        ans += bit[i];
    return ans;
}

// CDQ分治应该是可以AK的。
// 分治闭区间[L,R]
void cdq(int l, int r){
    // 将大问题拆解成小问题：
    if (l >= r || L[r] == L[l]) return ;
    int mid = L[(l + r) >> 1];
    // 以mid为中线，将左右两边分开。
    // 保证左边的任意x严格小于右边。
    if (arr[mid].x == arr[mid+1].x) mid--;
    if (mid < l) {
        // 往右边寻找中点
        mid = R[(l + r) >> 1];
        if (mid + 1 > r) return ;
    }
    
    cdq(l, mid); cdq(mid+1, r);
    
    // 分别对左半边和右半边按照第二关键字进行排序。
    sort(arr+l, arr+mid+1, cmp2);
    sort(arr+mid+1, arr+r+1, cmp2);
    
    // 统计答案：
    int j = l;
    for (int i=mid+1; i<=r; i++){
        while (j <= mid && arr[j].y > arr[i].y){
            add(arr[j].z, arr[j].val);
            j++;
        }
        arr[i].ans += query(maximum) -  query(arr[i].z);
    }
    // 恢复树状数组
    for (int i=l; i<j; i++)
        add(arr[i].z, -arr[i].val);
    return ;
}

int main(){
    // 数据输入
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i=1; i<=n; i++){
        int x, y, z;
        cin >> x >> y >> z;
        maximum = max(maximum, max(x, y, z));
        arr[i] = (student){x, y, z, i, 0, max(x, y, z)};
    }

    sort(arr+1, arr+1+n, cmp1);
    
    // 排序好之后计算L和R数组。
    // 通过使用L数组记录相同x值第一次出现的位置。
    for (int i=1; i<=n; i++){
        if (arr[i].x != arr[i-1].x) L[i] = i;
        else L[i] = L[i-1];
    }
    
    // 相同地，处理R数组。
    for (int i=n; i>=1; i--){
        if (arr[i].x != arr[i+1].x) R[i] = i;
        else R[i] = R[i+1];
    }
    
    cdq(1, n);  // 分治。
    for (int i=1; i<=n; i++) ans[arr[i].id] += arr[i].ans;  // 答案统计。
    for (int i=1; i<=n; i++) cout << ans[i] << endl;  // 答案输出。
    return 0;
}

复杂度分析

时间复杂度也比较好计算，分治的时间复杂度为 $O(\log{n} \times n)$。树状数组的单点修改和区间查询也分别是 $O(\log{n})$ 级别的。综合下来时间复杂度在 $O(n \times \log^2{n})$ 附近。因为题输入数据比较大，注意常数优化。