【51NOD 1107 斜率小于0的连线数量】 离散化+权值线段树

51NOD1107斜率小于0的连线数量
题意就是二维平面上N个点之间共有C(n,2)条连线。求这C(n,2)条线中斜率小于0的线的数量
我们将两个点的坐标描述一下就是.$A点为(ax,ay),B点为(bx,by)斜率小于0也就是bx>ax且by<ay$，那么这就是一个经典的二维偏序问题，由于题目规定$ax=bx|ay=by$的情况都不算，所以我们只要以第一关键字为x的顺序，第二关键字为y的逆序，进行排序，这样就能保证当x不相等时只有小于他的x会更新他，当x相等时也只有之前的大于他的y会更新他，之后离散化建一颗权值线段树，单点更新区间求和就可以了。
代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 5e4+5;
int n,Hash[maxn];
struct data
{int x,y;
}p[maxn];
bool cmp(const data &a,const data &b)
{if(a.x==b.x) return a.y<b.y;return a.x<b.x;
}
struct T
{int l,r,mid;int sum;
}tree[maxn<<2];
void push_up(int rt)
{tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
void build(int rt,int l,int r)
{tree[rt].l=l;tree[rt].r=r;tree[rt].sum=0;if(l==r)  return ;int mid=tree[rt].mid=l+r>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);push_up(rt);return ;
}
int query(int rt,int pos)
{if(tree[rt].r<pos) return 0;if(tree[rt].l>pos) return tree[rt].sum;int ans=0;if(pos<tree[rt<<1].r) ans+=query(rt<<1,pos);if(pos<tree[rt<<1|1].r) ans+=query(rt<<1|1,pos);return ans;
}
void  update(int rt,int pos)
{if(tree[rt].l==tree[rt].r){tree[rt].sum++;return ;}if(pos<=tree[rt].mid) update(rt<<1,pos);else update(rt<<1|1,pos);push_up(rt);return ;
}
int GetId(int x)
{return lower_bound(Hash+1,Hash+1+n,x)-Hash;
}
vector<int> v;
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);for(int i=1;i<=n;i++) Hash[i]=p[i].y;sort(p+1,p+1+n,cmp);sort(Hash+1,Hash+1+n);int MAX = unique(Hash+1,Hash+1+n)-Hash-1;build(1,1,MAX);long long ans=0;for(int i=1;i<=n;i++){int pos=GetId(p[i].y);ans+=query(1,pos);update(1,pos);}printf("%lld\n",ans);return 0;
}