Tokitsukaze and Strange Rectangle

Created by LXC on Fri Mar 1 15:14:03 2024

https://codeforces.com/problemset/problem/1190/D

ranting: 2000

tag: data structures, divide and conquer, sortings, two pointers

problem

平面上有n个点，第i个点在（xi，yi）处

小t想绘制一个矩形区域（如下图

该矩形被其左侧、底部和右侧的三条线围起：x=l，y=a和x=r(l, r, a 都可以为实数并且l<r)。

求可能有多少种不同的非空点集可以被小t的矩形覆盖，我们认为两个集合不同是在一个集合中存在一个点而不在另一个集合中存在。

solution

对于所有点(x,y)，将y值相同的点的x纳入有序集合$Y_y$中，

设集合操作$A\wedge B$为A与B集合合并去重

设所有出现的y值共有k个，并有大到小排列为$y_1, y_2, \cdots, y_k$

我们可以用扫描线，依次用直线$y=y_1, y_2, \cdots, y_k$，将扫过的点纳入同一集合中，如果我们遍历到了$y=y_i$，此时扫过的点集合为$C=Y_{y_1}\wedge Y_{y_2} \wedge \cdots \wedge Y_{y_i}$，将C的点放在数轴上，其中属于$Y_{y_i}$的点将其他所有点分割为$|Y_{y_i}|+1$个区间，不妨设各个区间的大小为$sz_1, sz_2, \cdots, sz_{|Y_{y_i}|+1}$

在C中任选两个点（可以是同一个点）的形成的区间只要包含了$Y_{y_i}$中的至少一个点，那么就是一个合法矩形覆盖。

扫描线$y=y_i$的贡献，总区间个数$\binom{|C|}{2}+|C|$，减去不合法区间个数$\sum \limits_{i=1}^{|Y_{y_i}|+1}\binom{sz_i}{2}+sz_i$

用线段树维护区间和，能做单点修改，区间查询，即可实现。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}


#define N 200005
#define LS (id << 1)
#define RS (id << 1 | 1)
ll sum[4 * N];

void push_up(int id) {
    sum[id] = sum[LS] + sum[RS];
}


void build(int id, int l, int r) {
    sum[id] = 0;
    if (l == r) {
        // sum[id] = a[l];
        return;
    }
    int m = l + r >> 1;
    build(LS, l, m);
    build(RS, m + 1, r);
    push_up(id);
}
// 单点增加v
void add(int id, int l, int r, int q, ll v) {
    if (l == r && l == q) {
        sum[id] = v;
        return;
    }
    int m = l + r >> 1;
    if (q <= m)
        add(LS, l, m, q, v);
    if (m < q)
        add(RS, m + 1, r, q, v);
    push_up(id);
}
// 区间查询和
ll ask(int id, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return sum[id];
    }
    int m = l + r >> 1;
    ll rt = 0;
    if (ql <= m)
        rt += ask(LS, l, m, ql, qr);
    if (m < qr)
        rt += ask(RS, m + 1, r, ql, qr);
    return rt;
}

void sol() {
    int n;
    cin >> n;
    map<int,int> idx;
    map<int,vector<int>, greater<int>> Y;
    for (int i=0; i<n; i++) {
        int x, y;
        cin >> x >> y;
        idx[x];
        Y[y].push_back(x);
    }
    int sz = 0;
    for (auto& [i,j]:idx) j=++sz;

    build(1, 1, sz);
    ll ans = 0;
    for (auto [i,j]:Y) {
        sort(j.begin(), j.end());
        // cout << i << " " << j << endl;
        for (auto k:j) {
            add(1, 1, sz, idx[k], 1);
        }    
        ll s = sum[1]*(sum[1]-1)/2 + sum[1];
        ll pre = 0;
        for (auto k:j) {
            add(1, 1, sz, idx[k], 0);
            ll cur = ask(1, 1, sz, 1, idx[k]);
            ll d = cur-pre;
            s -= d*(d-1)/2+d;
            pre = cur;
        }
        ll cur = ask(1, 1, sz, 1, sz);
        ll d = cur - pre;
        s -= d*(d-1)/2+d;
        for (auto k:j) {
            add(1, 1, sz, idx[k], 1);
        }
        // cout <<s << endl;
        ans += s;
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}