ikki 近期对数字颇感兴趣。如今ikki在纸上写了连续的N个数字，每一个数字都是[1,N]之间随意的一个数并且不反复，即这串数字

是数字1~N的一个排列。数字的序号从1到N，如今ikki想考你一下：

在这N个数字中能找出多少个3个数的组合满足:num[x]<num[z]<num[y]且x<y<z,当中x,y,z为这三个数字的下标。

对于每组数据，第一行输入一个整数N表示数列中数字的个数（1<=N<=5000）

第二行输入N个数字表示一个1~N的排列。

对于每组数据，输出”Case #k: p” ,k表示第k组例子，p表示满足要求的3个数字的组合数目，每组输出占一行。

因为结果可能比較大，结果需对100000007取模。

周洲@hrbust

隐藏着树状数组~~~根本没看出来，事实上主要是没思路，思路出来了才干用树状数组求解

然后肯定要减去后面的全部组成的i<j<k且a[i]<a[j]<a[k]的个数;

1. 能够先求出（xyz，xzy)的总数量
2. 仅仅需出去x后面多少个比它大的个数n，C(n,2)就是了
3. 然后求出xyz的个数，
4. 对于a，求出比a小的个数low[a],比a大的个数high[a],low[a]*high[a]就是答案
5. 能够借助树状数组求上述个数

注意了，总体求解！

并非说单独考虑某个数

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

typedef long long LL;

const int mod = 100000007;

int T,n;

int c[5010];

int lowbit(int x)

{

    return x & -x;

}

LL getsum(int x)

{

    LL sum = 0;

    while(x > 0)

    {

        sum += c[x];

        x -= lowbit(x);

    }

    return sum;

}

void update(int x , int val)

{

    while(x <= n)

    {

        c[x] += val;

        x += lowbit(x);

    }

}

int main()

{

#ifdef xxz

    freopen("in.txt","r",stdin);

#endif // xxz

    cin>>T;

    int Case = 1;

    while(T--)

    {

        memset(c,0,sizeof(c));

        cin>>n;

        LL ans = 0;

        for(int i = 1; i <= n; i++)

        {

            int temp;

            cin>>temp;

            update(temp,1);

            LL presmaller = getsum(temp - 1);

            LL prebigger = i-1 - presmaller;

            LL totbigger = n - temp;

            LL afterbigger = totbigger - prebigger;

            ans -= presmaller * afterbigger;

            if(afterbigger >= 2)

            {

                ans += afterbigger*(afterbigger - 1)/2;

            }

        }

        cout<<"Case #"<<Case++<<": "<<ans%mod<<endl;

    }

    return 0;

}