51nod 1107 斜率小于零连线数量 特调逆序数

逆序数的神题。。。。

居然是逆序数

居然用逆序数过的

提示。。。按照X从小到大排列，之后统计Y的逆序数。。。

之后，得到的答案就是传说中的解（斜率小于零）

#include<bits/stdc++.h>

using namespace std;

const long long MAXN = ;

pair<long long,long long> arr[MAXN];

bool com(pair<long long,long long>p1,

        pair<long long,long long>p2)

{

    if(p1.first==p2.first)return p1.second<p2.second;

    return p1.first<p2.first;

}

long long tree[MAXN];

long long arr1[MAXN];

void insert(int pos,int key=)

{

    while(pos<MAXN)

    {

        tree[pos]+=key;

        pos+=pos&(-pos);

    }

}

long long getSum(int pos)

{

    long long ret=;

    while(pos>)

    {

        ret+=tree[pos];

        pos-=pos&(-pos);

    }return ret;

}

map<long long ,long long> m1;

int main()

{

    cin.sync_with_stdio(false);

    long long n;cin>>n;

    for(int i=;i<n;++i)

    {

        cin>>arr[i].first>>arr[i].second;

        arr1[i]=arr[i].second;

//        cout<<m1[arr[i].second]<<endl;

    }

    sort(arr1,arr1+n);

    for(int i=;i<n;++i)if(!m1.count(arr1[i]))m1[arr1[i]]=m1.size()+;

    sort(arr,arr+n,com);

    //long long ret=0;

    long long ret=(n-)*(n)/;

    for(int i=;i<n;++i)

    {

    //    cout<<arr[i].first<<ends<<arr[i].second<<ends;

        ret-=getSum(m1[arr[i].second]);//cout<<ret<<endl;

        insert(m1[arr[i].second]);

    }

    cout<<ret<<endl;

    return ;

} 

我们大家都很绝望，但是有的人比我们更加绝望。