CF出div 4了，初学者也可以打比赛，AK不是梦~~
原题链接
题目大意：要求在上下两个区间连线，上面按次序1....n，下面连线位置从输入得到。例如样例中
7 4 1 4 6 7 7 5
那么连线方式就是上面1和下面4，上面2和下面1，即线段[1,4],[2,1],[3,4],[4,6],[5,7],[6,7][7,5]
要求最多能得到多少个线之间交叉点。通过分析可以看出，两个线段[a,b]和[c,d]，其中a和c一定不相同，假设a<c，那么只有当b>=d时两线才有交点。
解题思路：只要按次序读入数据，检查第i个数据a[i]之前有多少个数字不小于a[i]。由于a[i]不会超过n，因此这是一个树状数组的模板题。
用树状数组记录每个数字出现的次数，通过树状数组查询功能,能快速得到小于a[i]的个数，做个减法就得到不小于a[i]的个数，那么a[i]和这些数字一定能构成交点。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int t,n;
int update(int a[],int x)/**< 树状数组模板 */
{
for(;x<=n;x+=x&-x)
a[x]++;
}
int getSum(int a[],int x)
{
int sum=0;
for(;x>0;x-=x&-x)
sum+=a[x];
return sum;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
int i,j,x;
cin>>t;
while(t--)
{
cin>>n;
ll ans=0;/**< 可能会超过int范围 */
int s[n+5]={0};
for(i=1;i<=n;i++)
{
cin>>x;
ans+=i-1-getSum(s,x-1);/**< i左边有i-1个数字，getSum(s,x-1)找到比x小的数字个数 */
update(s,x);
}
cout<<ans<<endl;
}
return 0;
}
