题解

Kano_zyc · 2024-01-21 15:00:27 · 题解

看了一下楼下的题解都有点抽象， 让我来水一发清晰一点的。

题意简述

在一个平面直角坐标系中，给定一些点，每个点的坐标都在第一象限且所有的横坐标和纵坐标都是不同的整数。

要找出所有的点对，使得这两个点的连线与 x 轴和 y 轴都有一个交点，求这样的点对的数量。

思路分析

此题初看似乎有些无从下手，先分析相交的条件。不难发现相交必须满足的条件是 x_i>x_j 并且 y_i<y_j，或者 x_i<x_j 并且 y_i>y_j。

不觉得这个东西很眼熟吗？没错，它就是逆序对！

然后我们把 x 排序，求 y 的逆序对就行了。用归并排序或树状数组均可。

注意事项

• 注意此题答案可能会爆 int 需要开 long long。

• 注意范围要开够。

• 多组数据记得初始化。

AC Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

#define int long long

using namespace std;

#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
char *p1,*p2,buf[1<<20+5];
inline int read(){
    int x=0;
    char c=gc();
    while(!isdigit(c)){
        c=gc();
    }while(isdigit(c)){
        x=x*10+(c^48);
        c=gc();
    }return x;
}

const int N = 1e6 + 10;

struct node
{
    int x, y;
}a[N];

int c[N], t, n, m, k, ans;

bool cmp(node a, node b)
{
    if(a.x == b.x) 
      return a.y < b.y;
    return a.x < b.x;
}

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int y)
{
    for(int i = x;i <= n;i += lowbit(i)) 
      c[i] += y;
}

int sum(int x)
{
    int ans = 0;
    for(int i = x;i > 0; i -= lowbit(i))
      ans+=c[i];
    return ans;
}

signed main()
{
    t = read();
    for(int l = 1; l <= t; l ++ )
    {
        ans=0;

        n = read(), m = read(), k = read();

        for(int i = 1;i <= k; i ++ ) 
          a[i].x = read(), a[i].y = read();

        memset(c, 0, sizeof(c));

        sort(a + 1, a + 1 + k, cmp);

        for(int i = k; i >= 1; i -- )
        {
            ans += sum(a[i].y - 1);
            add(a[i].y, 1);
        }

        printf("Test case %lld: %lld\n",l,ans);
    }
    return 0;
}