CSAcademy Round#68 Right Triangles

题目链接https://csacademy.com/contest/round-68/task/right-triangles/

题意:略。

思路:所有点按到原点的斜率从小到大排序,然后一个一个插入同时查询这个点位置之前比它小的点有几个,树状数组维护即可,和求逆序对思路一样。

const int N=1e5+10;
struct Point{
    int x,y,id;
    bool operator<(const Point&rhs)const{
        return 1LL*y*rhs.x<1LL*rhs.y*x;
    }
}p[N];
int n,ans[N];
int sum[N];
inline int lowbit(int x){return x&(-x);}
int get(int x){
    int res=0;
    for (;x>0;x-=lowbit(x)) res+=sum[x];
    return res;
}
void update(int x){for (;x<=1e5;x+=lowbit(x)) sum[x]++;}
int main(){
    read(n);
    for (int i=1;i<=n;i++) read(p[i].x),read(p[i].y),p[i].id=i;
    sort(p+1,p+1+n);
    for (int i=1;i<=n;i++){
        ans[p[i].id]+=get(p[i].x);
        update(p[i].x);
    }
    for (int i=1;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注