solution

先从三个排名中选择两个，假设是 $(a,b)$ ，就是要找对于每个队伍，满足a比他大并且b比他小的队伍有多少个。这就是一个二维偏序的问题，先按照a从大到小排序，这时每个位置左边都满足a比他大，所以从左向右扫的过程中维护一个权值树状数组，每次将一个元素的b***去，并且在树状数组上查询小于当前这个b的元素有多少个。

对于另外的两种组合 $(a,c),(b,c)$ 同理。

显然这样肯定会有一些队伍组合被考虑了多次。只要找到每对队伍多被考虑了几次即可。

考虑对于两个队伍，其中一个的排名是 $(a_1,b_1,c_1)$ ，另外一个的排名是 $(a_2,b_2,c_2)$ 。因为每个元素表示的都是排名，所以肯定不会有相同的两个元素。如果同时满足 $a_1>a_2,b_1>b_2,c_1>c_2$ ，肯定不会被计算到，所以不用考虑。那么剩下的一种情况就是其中一个二元组有两个元素比另一个大，一个元素比另一个小。这里不妨设 $a_1>a_2,b_1>b_2,c_1<c_2$ 。然后考虑我们算重了多少次，显然在按照 $(a,c),(b,c)$ 计算时这两个队伍都会被计算一次。也就是说每两个队伍都被算了两次。所以将最终结果除以二就行了。

对于此题的另外一点思考

上面讲了，我们可以直接把所计算的答案除以二得到真正答案的原因是每个任意两个二元组中的同一种元素是两两不同的。那么如果不满足此条性质应该如何做呢。

我们还是按照a进行排序，然后就是要找a左边的队伍里面，b大于当前位置的b，或者是c大于当前位置的c的数量。这里可以容斥，也就是用所有b大于当前位置的数量+c大于当前位置的数量-b大于当前位置且c大于当前位置的数量。

这个里面比较难求的只有b大于当前位置且c大于当前位置的数量，其他的可以用类似于此题的方法用树状数组求解。

然后这个b大于当前位置且c大于当前位置的数量，可以用树套树计算。

要注意的地方:因为a可能相同，所以要对a相同的内部进行计算。

code

/*
* @Author: wxyww
* @Date:   2020-05-29 14:56:00
* @Last Modified time: 2020-05-29 15:01:01
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 200010;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
struct node {
    int x,y,z;
}a[N];
bool cmp1(const node &A,const node &B) {
    return A.x > B.x;
}
bool cmp2(const node &A,const node &B) {
    return A.y > B.y;
}
int tree[N],n;
void update(int pos,int c) {
    while(pos <= n) {
        tree[pos] += c;
        pos += pos & -pos;
    }
}
int query(int pos) {
    int ret = 0;
    while(pos) {
        ret += tree[pos];
        pos -= pos & -pos;
    }
    return ret;
}

int main() {
    n = read();
    for(int i = 1;i <= n;++i) {
        a[i].x = read();a[i].y = read();a[i].z = read();
    }
    ll ans = 0;
    sort(a + 1,a + n + 1,cmp1);
    for(int i = 1;i <= n;++i) {
        ans += query(a[i].y);
        update(a[i].y,1);
    }
    memset(tree,0,sizeof(tree));
    for(int i = 1;i <= n;++i) {
        ans += query(a[i].z);
        update(a[i].z,1);
    }
    memset(tree,0,sizeof(tree));
    sort(a + 1,a + n + 1,cmp2);
    for(int i = 1;i <= n;++i) {
        ans += query(a[i].z);
        update(a[i].z,1);
    }
    cout<<ans / 2;

    return 0;
}

【每日一题】Contest

solution

code