题意:
给定二维坐标系中的n个整数点。一个上*的矩形 \((x1,y),(x2,y),(x2,+\infty),(x1,+\infty),矩形坐标为实数\) 可以围出一个*区域,区域内的的点组成一个集合。随便画这样的矩形,问不同的集合有多少种。
思路:
按纵坐标从大到小处理点,纵坐标相同的点要放一起处理。注意避免重复计数。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define x second
#define y first
const int N = 2e5 + 5;
int n, vis[N]; pair<int, int> a[N];
int tr[N];
int lowbit(int x) {return x&-x; }
void add(int p, int x) {for(;p<=n;p+=lowbit(p))tr[p]+=x; }
int ask(int p) {int s=0;for(;p;p-=lowbit(p))s+=tr[p];return s; }
int ask(int l, int r) {return ask(r)-ask(l-1); }
void LSH() //离散化后的坐标范围[1,n]
{ //all、排序、去重、二分
vector<int> all; all.push_back(0); //为0的话树状数组处理不了
for(int i = 1; i <= n; i++) all.push_back(a[i].x);
sort(all.begin(), all.end());
all.erase(unique(all.begin(),all.end()), all.end());
for(int i = 1; i <= n; i++)
a[i].x = lower_bound(all.begin(),all.end(),a[i].x)-all.begin();
}
signed main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d%d", &a[i].x, &a[i].y);
LSH(); //离散化横坐标
//这样x和y都会倒序,其实还是手写小于号比较好
sort(a + 1, a + 1 + n, greater<pair<int,int>>());
ll ans = 0;
for(int i = 1; i <= n + 1; i++)
{
if(a[i].y != a[i-1].y) //统计上一层
{ //上一层为 i-1, i-2, ..., j+1, j
int j = i-1; while(j && a[j-1].y == a[j].y) j--;
if(j) for(int k = j; k < i; k++)
{ //左端点*右端点计数
ll left = k == i-1 ? ask(a[k].x) : ask(a[k+1].x,a[k].x)-1;
ans += left * ask(a[k].x,n);
}
}
if(i == n + 1) return printf("%lld", ans), 0;
if(!vis[a[i].x]) add(a[i].x, 1), vis[a[i].x] = 1;
}
}