POJ3928(树状数组:统计数字出现个数)

#include"cstdio"
#include"cstring"
#include"algorithm"
using namespace std;
const int MAXN=20005;
const int N=100005;
typedef long long LL;
struct Node{
    int id,x;
}a[MAXN];
bool comp(const Node &a,const Node &b)
{
    return a.x < b.x;
}
int bit[N];
int n;
int lowbit(int i)
{
    return i&(-i);
}
void add(int i,int x)
{
    while(i<=MAXN)
    {
        bit[i]+=x;
        i+=lowbit(i);
    }
}
LL sum(int i)
{
    LL s=0;
    while(i>0)
    {
        s+=bit[i];
        i-=lowbit(i);
    }
    return s;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(bit,0,sizeof(bit));
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i].x);
            a[i].id=i+1;
        }    
        sort(a,a+n,comp);
        int lmin;
        int rmin;
        LL res=0;
        for(int i=0;i<n;i++)
        {
            lmin=sum(a[i].id-1);//zuoxiao
            rmin=sum(n)-sum(a[i].id);
            res+=(lmin*(n-a[i].id-rmin));
            res+=(rmin*(a[i].id-lmin-1));
            add(a[i].id,1);
        }
        printf("%lld\n",res);
    }
    return 0;
}
/*
1
5 1 3 5 2 4
res:3
*/