/ ALGORITHM

CodeForces Gym #100247 K

Contest Information

source: It’s from the Gym #100247 of codeforces

Problem H

$n$ 支队伍参加了 $3$ 场比赛,定义两支队伍属于一组,当且仅当两支队伍至少在一场比赛中排名小于另一支队伍。给出他们每场比赛的排名,求一共有多少组

数据范围:$ n ≤ 200000 $

Solution

我们容易想到的做法是按照某一场比赛排序后,从后往前统计在另外两场比赛中排名在当前队伍前的队伍数,但这样会产生重复,又 $n$ 的数量级太大,也不能使用二维树状数组。

那么,我们考虑两支队伍之间的关系:对于满足在同一组的两支队伍,其中一支队伍必定在两场比赛中排名小于另一支;而不满足同组关系的两支队伍,其中一支队伍必定在三场比赛中排名小于另一支。所以我们对于第一、二场,第二、三场,第一、三场比赛分别统计在两场比赛中都小于的组的数量,那么满足同一组的两支队伍肯定会被统计一次,设为 $A$,而不满足同一组的两支队伍就会被统计三次,设为$B$。那么最终答案就是$ tot - (A+B-tot)/2,tot = \frac{n*(n-1)}{2}$。

AC code

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        int x,y,z;
        bit.init(n);
        for(int i=1;i<=n;i++)
        {
            read(x);read(y);read(z);
            node[i] = Node(x,y,z);
        }
        LL ans = 0;
        sort(node+1, node+1+n, [](Node a, Node b){
            return a.x < b.x;
        });
        for(int i=1;i<=n;i++)
        {
            ans += bit.sum(node[i].y);
            bit.update(node[i].y, 1);
        }
        bit.init(n);
        for(int i=1;i<=n;i++)
        {
            ans += bit.sum(node[i].z);
            bit.update(node[i].z, 1);
        }
        sort(node+1, node+1+n, [](Node a, Node b){
            return a.y < b.y;
        });
        bit.init(n);
        for(int i=1;i<=n;i++)
        {
            ans += bit.sum(node[i].z);
            bit.update(node[i].z, 1);
        }
        ans = 1LL*n*(n-1)/2 - (ans - 1LL*n*(n-1)/2)/2;
        out(ans);puts("");
    }
}