题解|#2D Rank Finding

• 题目考点:二维偏序

• 题目大意：对于二维坐标里面每个点，寻找该点左下角的点的个数（包括同X、同Y轴上面的点）

• 先说WA思路（还没想好为什会错，后面知道了再来补充）：把所有坐标先按X轴优先排序，再按Y轴优先排序，取两次排序该点最小的位置，于是出现了下图。。。 思路乍一看好像没什么问题，但越想越奇怪，究竟什么原因还不知道。

• AC思路：二维偏序，将X轴排序后，离散化Y轴，用树状数组维护每个Y轴的前缀数量即可。

代码：

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

using namespace std;
typedef long long LL;

const int N = 300010, M = N*2;

struct Node
{
    int x, y, rank_y;
    int id;
}a[M];

int n, tr[M], ans[M];
int tot[M];

bool cmp(Node A, Node B)
{
    if(A.x == B.x) return A.y<B.y;
    return A.x < B.x;
}

void solve()
{
    for(int i = 1; i <= n; i++)
    {
        int y = a[i].y;
        a[i].rank_y = upper_bound(tot+1, tot+n+1, y)-tot-1;
        //cout << "**" << y << ' ' << a[i].rank_y << '\n';
    }
}

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

void add(int t, int c)
{
    for(int i = t; i <= N; i += lowbit(i)) tr[i] += c;
    return ;
}

int que(int t)
{
    int res = 0;
    for(int i = t; i; i -= lowbit(i)) res += tr[i];
    return res;
 }

int main()
{
    scanf("%d", &n);

    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d", &a[i].x, &a[i].y);
        a[i].id = i;
        tot[i] = a[i].y;
    }

    sort(tot+1, tot+n+1); // 离散化Y轴
    solve();

    sort(a+1, a+n+1, cmp);
    for(int i = 1; i <= n; i++)
    {
        int y = a[i].rank_y;
        int id = a[i].id;   

        ans[id] = que(y);  // 树状数组维护前缀点数
        add(y, 1);
    }

    for(int i = 1; i <= n; i++) printf("%d ", ans[i]);

    return 0;
}