POJ 3928 Ping pong 树状数组

树状数组的运用

具体就是枚举每个裁判，左边比裁判小的个数乘以右边比裁判大的个数，以及左边比裁判大的个数乘以右边小的个数，总和即为结果

/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 100000000
#define LOCA
#define PI acos(-1.0)
using namespace std;
int a[100001], b[100001], data[100001];
int lowbit(int  x)  //返回二进制下最右边的1，用于树状数组存储和查询时的结构
{
    return x & (-x);
}
void calculate1(int x) //由于所有数据是独一无二，并且在100000以内，所以将所有数据处理，用树状数组a预存,所有能被x影响到的数组均改变
{
    for(; x < 100001; x += lowbit(x))
    a[x]++;
}
void calculate2(int x) //枚举每个裁判时，一个一个的存入树状数组b,方便对当前左侧选手的查询
{
    for(; x < 100001; x += lowbit(x))
    b[x]++;
}
__int64 sum1(int x) //计算所有数据中比裁判小的个数，从而推出比裁判大的个数
{
    __int64 sum = 0;
    for(; x > 0; x -= lowbit(x))
    sum += a[x];
    return sum;
}
__int64 sum2(int x) //计算裁判左侧比裁判小的个数，就能推出右侧，从而推出大的个数
{
    __int64 sum = 0;
    for(; x > 0; x -= lowbit(x))
    sum += b[x];
    return sum;
}
int main()
{
#ifdef LOCAL
    freopen("ride.in","r",stdin);
    freopen("ride.out","w",stdout);
#endif
    int n, i, t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        for(i = 1; i <= n; i++)
        {
            scanf("%d", &data[i]);
            calculate1(data[i]);
        }
        __int64 ans = 0;
        calculate2(data[1]);
        for(i = 2; i < n; i++)
        {
            calculate2(data[i]);
            __int64 allsmall = sum1(data[i]);
            __int64 nowsmall = sum2(data[i]);
            ans += (nowsmall - 1) * ((n - allsmall) - (i - nowsmall));//左边小的乘以右边大的
            ans += (i - nowsmall) * (allsmall - nowsmall);//右边小的乘以左边大的
        }
        printf("%I64d\n", ans);
    }
    return 0;
}