View Code of Problem 1358

#include<iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
using namespace std;
const int maxn=1e6+10;
const int inf=0xffffff0;
typedef long long ll;
//线段树 
struct node
{
    int id,val;
}num[maxn];
bool cmp(node n1,node n2)
{
    return n1.val<n2.val;
}
struct Tree{
	int l,r;
	ll w;
	Tree(){
	};
	Tree(int _l,int _r,ll _v){
		l=_l,r=_r,w=_v;	
	};
	int mid(){
		return (l+r)/2;
	};
	
};
int rank[maxn];
Tree tree[maxn*4];
void build(int k,int l,int r){		//建树 
	tree[k]=Tree(l,r,0);
	if(tree[k].l==tree[k].r){
		return;
	}
	build(k<<1,l,(l+r)/2);
	build(k<<1|1,(l+r)/2+1,r);
}

void update(int k,int x)
{
    tree[k].w++;
    if(tree[k].l==tree[k].r&&tree[k].l==x)
        return;
    if(x<=tree[k].mid())
		update(k<<1,x);
    else 
		update(k<<1|1,x);
}
ll ans;
int query(int k,int x,int y){			//区间查询 
	int sum=0;
	if(tree[k].l==x&&tree[k].r==y){
		return tree[k].w;
	}

	if(y<=tree[k].mid())
		sum=query(k<<1,x,y);
	else if(x>tree[k].mid())
		sum=query(k<<1|1,x,y);
	else
		sum=query(k<<1,x,tree[k].mid())+query(k<<1|1,tree[k].mid()+1,y);
	return sum;
}


int main()  
{  
    int n;
    while(~scanf("%d",&n)&&n)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d",&num[i].val);
            num[i].id=i;
        }
        sort(num,num+n,cmp);
        for(int i=0;i<n;i++) rank[num[i].id]=i+1;
        build(1,0,n+1);
        long long sum=0;
        for(int i=0;i<n;i++)
        {
            int x = rank[i];
            sum+=query(1,x+1,n+1);
            update(1,x);
        }
        printf("%lld\n",sum);
    }
    return 0;
}