#include<stdio.h>
#include<algorithm>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define MAX_N 1100
using namespace std;
int tree[MAX_N<<2],arr[MAX_N],s[MAX_N];
int query(int val,int l,int r,int rt)
{
    ++tree[rt];
    if(l==r)
        return 0;
    int m = l + ( r - l ) / 2 ;
    return val <= s[m] ? query(val,lson)+tree[rt<<1|1] : query(val,rson);
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;++i)
    {
        int n ;
        scanf("%d",&n);
        for(int j=0;j<n;++j)
        {
            scanf("%d",arr+j);
            s[j] = arr[j] ;
        }
        sort(s,s+n);
        int len = unique(s,s+n) - s ;
        int res = 0 ;
        for(int j=0;j<n;++j)
            res +=query(arr[j],0,len-1,1);
        printf("Scenario #%d:\n%d\n\n",i,res);
        fill(tree,tree+n*4,0);
    }
    return 0;
}

• Re:好吧,我来个线段树版本的吧,勿喷!!! (954) zjh461682551 2018-12-20 15:53:28