配列内の逆順序ペア

説明
 
テストの説明とコミット
 
コミットステータス
 
テーマの設定

Problem Description

2つの数値のセットが与えられ、前の数値が後の数値より大きい場合、この2つの数値は逆シーケンスペアを構成します.配列を入力し、この配列の逆シーケンスペアの総数を求めます.

Input

まず、データ群数T(1<=T<=100)を入力する

各テストデータのセットには2行が含まれます.最初の行には、配列内の要素の数を表す整数nが含まれます.そのうち1<=n<=10^5である.2行目にはn個の整数が含まれ、各配列はintタイプである.

Output

各テストデータのセットに対応して、配列内の逆シーケンスペアの総数を表す整数を出力します.注意して、結果は比較的に大きくて、long longを使ってください!

Sample Input

1
4
7 5 6 4

Sample Output

5

<strong>#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
long long sum;
int a[100010];
void merge(int *a,int l,int mid,int r)
{
    int n1=mid-l+1;
    int n2=r-mid;
    int *L=new int[n1+1];
    int *R=new int [n2+1];
    int i,j,k;
    for(i=0; i<n1; i++)
    {
        L[i]=a[i+l];
    }
    for(j=0; j<n2; j++)
    {
        R[j]=a[j+mid+1];
    }

    for(i=0,j=0,k=l; k<=r&&i<n1&&j<n2; k++)
    {
        if(L[i]<=R[j])
        {
            a[k]=L[i++];
        }
        else
        {
            sum+=(n1-i);
            a[k]=R[j++];

        }
    }
    if(i>=n1)
    {
        while(k<=r)
        {
            a[k++]=R[j++];
        }
    }
    else
    {
        while(k<=r)
        {
            a[k++]=L[i++];
        }
    }
    delete []L;
    delete []R;
}
void merge_sort(int *a,int l,int r)
{
    if(l<r)
    {
        int mid=(l+r)>>1;
        merge_sort(a,l,mid);
        merge_sort(a,mid+1,r);
        merge(a,l,mid,r);
    }
}
int main()
{
    int n,t;
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            sum=0;
            scanf("%d",&n);

            for(int i=0; i<n; i++)
            {
                scanf("%d",&a[i]);
            }
            merge_sort(a,0,n-1);
            printf("%lld
",sum);
        }
    }
    return 0;
</strong>
 な : で を さいものから きいものに べ える.R[j]