二维偏序 && 离散化

二维偏序

#include <cstdio>
#include <cstring>
#include <cmath>

#define max 32001
using namespace std;

int c[max], ans[max], x, y, n;

int sum(int x) {
    int s = 0;
    while (x > 0) {
        s += c[x];
        x -= x & (-x);
    }
    return s;
}

void insert(int x) {
    while (x <= max) {
        c[x]++;
        x += x & (-x);
    }
}

int main() {
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &x, &y);
            x++;
            ans[sum(x)]++;
            insert(x);
        }
        for (int i = 0; i < n; i++)
            printf("%d\n", ans[i]);
    }
}

离散化

//对a[]进行离散化
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &a[i]), w[i] = a[i];//将数组a复制给数组w
    sort(w + 1, w + n + 1);//对数组w排序
    int t = unique(w + 1, w + n + 1) - w - 1;//去重
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(w + 1, w + t + 1, a[i].y) - w;//赋值
   

全部代码：

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string>
#include<string.h>
#include<algorithm>

using namespace std;
#define ll long long
#define il inline
#define lowbit(x) x&-x
#define sc(x) scanf("%d",&x)

const int maxn = 1e5;
int tree[maxn], ans[maxn], w[maxn], n;

struct Node {
    int x, y;
} node[maxn];


void add(int i, int k) {
    while (i <= n) {
        tree[i] += k;
        i += lowbit(i);
    }
}

int getSum(int i) {        //求A[1 - i]的和
    int res = 0;
    while (i > 0) {
        res += tree[i];
        i -= lowbit(i);
    }
    return res;
}

il bool comp(Node a, Node b) {
    return a.y < b.y;
}

int main() {
    while (~sc(n)) {

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


        //将x离散化
        sort(w + 1, w + n + 1);//对x排序
        int t = unique(w + 1, w + n + 1) - w - 1;//去除重复
        for (int i = 1; i <= n; i++)
            node[i].x = lower_bound(w + 1, w + t + 1, node[i].x) - w;//赋值
        sort(node + 1, node + n + 1, comp);//按y排序

        for (int i = 1; i <= n; i++) {  //检测小于该点的x的数目
            ans[getSum(node[i].x)]++;
            add(node[i].x, 1);
        }

        for (int i = 0; i < n; i++) {
            printf("%d\n", ans[i]);
        }
    }

    return 0;
}