Codeforces 1191F (树状数组 / 线段树 + 扫描线)

Codeforces 1191F
题意：给定平面上$n$个点，每次可以用$x\in [l,r],y \in [a,+\infty)$作为限制条件来得到一个点集。求能得到多少种不同的点集。

很显然要扫描线。

发现$y \in [a,+\infty)$，那么从上往下即可。

考虑从上往下，从左到右加点，然后统计新加的点的答案。

可能一开始会想到一个找这个点的左上角的所有点乘上右上角所有点，但是有重复。

考虑缩小右上角点的范围，那么我们只需要统计矩形$([x_i,x_{i+1}], y_i), y_i=y_{i+1}$的点的个数作为右上角点的范围即可。

注意这里每列的赋值只能最多一，那么我们能想到用线段树维护，但是这里由于只是单点修改，我们完全可以开一个树状数组和一个vis数组来判断某个地方加了1没有即可完成。

坐标数据大离散化即可。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    struct data {
        int ox, oy;
        int x, y;
    } pos[200000 + 5];

    int n, tax[400000 + 5], tot = 0;
    LL sumv[400000 * 4 + 5];
    #define lc (o << 1)
    #define rc (o << 1 | 1)
    #define M ((l + r) >> 1)

    bool cmp(data a, data b) {return a.y == b.y ? a.x < b.x : a.y > b.y;}

    void pushup(int o) {sumv[o] = sumv[lc] + sumv[rc];}
    void add(int o, int l, int r, int p) {
        if (l == r) {sumv[o] = 1; return ;}
        if (p <= M) add(lc, l, M, p);
        else if (p > M) add(rc, M + 1, r, p);
        pushup(o);
    }
    LL query(int o, int l, int r, int x, int y) {
        if (x <= l && r <= y) {
            return sumv[o];
        }
        LL ret = 0;
        if (x <= M) ret += query(lc, l, M, x, y);
        if (M < y)  ret += query(rc, M + 1, r, x, y);
        return ret;
    }

    void clean() {
    }
    int solve() {

        clean();
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d", &pos[i].ox, &pos[i].oy);
            tax[++tot] = pos[i].ox;
            tax[++tot] = pos[i].oy;
        }
        sort(tax + 1, tax + 1 + tot);
        tot = unique(tax + 1, tax + 1 + tot) - tax - 1;
        for (int i = 1; i <= n; ++i) {
            pos[i].x = lower_bound(tax + 1, tax + 1 + tot, pos[i].ox) - tax;
            pos[i].y = lower_bound(tax + 1, tax + 1 + tot, pos[i].oy) - tax;
        }
        sort(pos + 1, pos + 1 + n, cmp);
        LL ans = 0, lst = 1;
        while (lst <= n) {
            LL now = lst + 1;
            while (now <= n && pos[now].y == pos[now - 1].y) ++now;
            now--;
            for (LL i = lst; i <= now; ++i) add(1, 1, tot, pos[i].x);
            for (LL i = lst; i <= now; ++i) {
                LL l = query(1, 1, tot, 1, pos[i].x);
                LL gg = pos[i + 1].x - 1;
                if (i == now) gg = tot;
                LL r = query(1, 1, tot, pos[i].x, gg);
                ans += l * r;
            }
            lst = now + 1;
        } 
        cout << ans;

        return 0;
    }  
}
int main() {
    flyinthesky::solve();
    return 0;
}