蒟蒻求调教

#include<bits/stdc++.h>
using namespace std;
struct node
{
    long long l,r,val;
}a[1145140*4+1];
struct shit
{
    int id,va;
}da[1145141];
int n,ans,k,id[1145141];
bool cmp(shit x,shit y)
{
    return x.va==y.va?x.id<y.id:x.va<y.va;
}
void bld(int l,int r,int root)
{
    a[root].l=l;
    a[root].r=r;
    if(l==r)
        return;
    int mid=(l+r)/2;
    bld(l,mid,root*2);
    bld(mid+1,r,root*2+1);
}
void add(int x,int root)
{
    if(a[root].l==a[root].r)
    {
        a[root].val++;
        return;
    }
    int mid=(a[root].l+a[root].r/2);
    if(x<=mid)
        add(x,root*2);
    else
        add(x,root*2+1);
    a[root].val=a[root*2].val+a[root*2+1].val;
}
int query(int x,int y,int root)
{
    int mid=(a[root].l+a[root].r)/2;
    int ret=0;
    if (x<=a[root].l&&a[root].r<=y)
        return a[root].val;
    if (x<=mid)
        ret+=query(x,y,root*2);
    if (y>mid)
        ret+=query(x,y,root*2+1);
    return ret;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>da[i].va,da[i].id=i;
    sort(1+da,1+da+n,cmp);
    for(int i=1;i<=n;i++)
        id[da[i].id]=i;
//  for(int i=1;i<=n;i++)
//      cout<<id[i];
    bld(1,n,1);
    for(int i=1;i<=n;i++)
    {
        int x=id[i];
        ans+=query(x+1,n,1);
        add(x,1);
    }
    cout<<ans;
}