UVALive 4329 Ping pong, beijing 2008

旧城等待， 2022-06-18 09:29 96阅读 0赞

**题目链接:**[  
][Link 1]

[https://vjudge.net/contest/157087\#problem/A][Link 1]

[https://vjudge.net/problem/13895/origin][https_vjudge.net_problem_13895_origin]

**题意 :**

一条街上住着**n**(3 <= **n** <= 20 000)个乒乓球爱好者,一人一间屋,每个人都有一个**不同**的技能值**ai**.每场比赛需要三人:一名裁判,两名选手.他们有一个奇怪的规定,即裁判必须住在两名选手之间,并且技能值也在两选手之间.问一共有多少种比赛.

**输入格式:**

输入第一行为数据组数**T( 1 <= T <= 20 )** .每组数据占一行,首先是一个整数**n( 3 <= n <= 20 000 )** ,然后是n个不同整数,即**a1,a2...,an(1 <= ai <= 100 000 )** , 按照住所从左到右的顺序给出每个爱好者的技能值.

**输出格式:**

对每组数据,输出一行,比赛总数的值.

**分析 :**

考虑第i个人当裁判的情况.假设a1到a(i -1)有ci个人比ai小,那么就有(i - 1) - ci个人比ai大; 同理, 假设a(i+1) 到an中有di个比ai小,那么就有 ( n - i )  - di个比ai大.那么i当裁判有

**ci ( n - i - di ) + ( i - ci - 1)di**中比赛. 如此问题便转换为求ci和di.

ci表示前i个元素中小于ai的元素个数,由于ai的取值范围不大,可以用树状数组记录某个值是否存在,那前缀和便是ci.

#include <bits/stdc++.h>
    
    using namespace std;
    
    const long long maxn = 100100;
    
    long long C[maxn];    //左边
    long long Cr[maxn];   //右边
    long long a[20200];
    
    long long sum(long long c[], long long x) //统计1 - x有多少个
    {
        long long s = 0;
        while(x > 0)
        {
            s += c[x];
            x -= x & -x;
        }
        return s;
    }
    void add(long long c[], long long x, long long d)
    {
        while(x < maxn)
        {
            c[x] += d;
            x += x & -x;
        }
    }
    
    
    int main()
    {
        int T;
        while(scanf("%d", &T) != EOF)
        {
            while(T--)
            {
                int n;
                memset(C, 0, sizeof(C));
                memset(Cr, 0, sizeof(Cr));
                scanf("%d", &n);
                for(int i = 1; i <= n; i++)
                {
                    scanf("%d", &a[i]);
                    add(Cr, a[i], 1);   //右边,先扫一遍,然后依次减,得后缀
                }
                long long ans = 0;
                for(int i = 1; i <= n; i++) //遍历裁判
                {
                    add(Cr, a[i], -1);  //裁判不能和右选手是同一人,故减后统计
                    ans += sum(C, a[i]) * (sum(Cr, maxn) - sum(Cr, a[i] - 1));  //左边小,右边大
                    ans += (i - 1 - sum(C, a[i])) * (n - i - sum(Cr, maxn) + sum(Cr, a[i] - 1)); //左边大,右边小
                    add(C, a[i], 1);    //裁判不能和左选手是同一人,故统计后加
                }
                printf("%lld\n", ans);
            }
        }
        return 0;
    }

[Link 1]: https://vjudge.net/contest/157087#problem/A
[https_vjudge.net_problem_13895_origin]: https://vjudge.net/problem/13895/origin