[codeforces Round #573(Div.2)-F]Tokitsukaze and Strange Rectangle

题目传送门

题目大意为:

给你n个一维象限的坐标,用$y=a,y=INF,x=l,x=r$ 所组成的的矩形包含的点构成一个点集,求所有不相同的点集数量。

非常复杂的一个题(just for me)

对于一个点集,一定会有最靠左的点 $x_L$,最靠右的点 $x_R$ ,最靠下的点 $y_D$ .通过观察可知,只要固定了这三个点,就可以确定出一个点集。因此我们现在的任务就变成了如何计算所有的$x_L,x_R,y_D$。

首先我们固定 $y_D$ 的值,然后根据 $y_D$ 的值求出所有在 $y=y_D$ 上面的点,由定义可知$x_L \leq x_D \leq x_R$ ,$x_D$为$y_D$ 所对定的点的横坐标,因此我们需要计算纵坐标大于等于y_D的点中横坐标小于等于x_D的点的数量和大于等于x_D的点的数量

在计算点的数量时,我们可以先离散化所有点的横坐标,然后利用线段树或树状数组进行查询。

但是有一种情况,如果有两个点的横坐标相同,那么求出来的点集就会有重复的情况。所以我们需要对所求的值进行某些简化。

我们在计算以 $y_{1D}$ 为底的点集时,如果 $y_{2D}==y_{1D} 并且 x_{1D} \leq x_{2D}$ , 那么我们在求大于等于 $x_{1D}$的点的数量时只需要求横坐标在区间$[ x_{1D} , x_{2D} - 1 ]$的数即可。这样就能避免某些点集被重复计算。

代码如下(查询方式实现为线段树):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll mod=1000000007;
const ll maxn=1000000+10;
struct node{
int x,y;
bool friend operator <(node i,node j){
if(i.y==j.y) return i.x<j.x;
return i.y>j.y;
}
}a[maxn];
int c[maxn],vis[maxn];
int sum[maxn];
int n,N;
void init(int x){
N=1;
while(N<x) N*=2;
}
void update(int k){
k+=N-1;
sum[k]++;
while(k){
k=(k-1)/2;
sum[k]++;
}
}
int query(int a,int b,int l,int r,int k){
if(b<0) return 0;
if(r<a || b<l) return 0;
if(a<=l && r<=b) return sum[k];
else{
int vl=query(a,b,l,(l+r)/2,k*2+1);
int vr=query(a,b,(l+r)/2+1,r,k*2+2);
return vl+vr;
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d %d",&a[i].x,&a[i].y);
c[i]=a[i].x;
}
sort(c,c+n);
int p=unique(c,c+n)-c;
for(int i=0;i<n;i++) a[i].x=lower_bound(c,c+n,a[i].x)-c;

sort(a,a+n);
init(n);
ll res=0;
int list=0;//list用来标记相同的纵坐标的数的起点。
for(int i=0;i<n;i++){
if(a[i].y!=a[i+1].y){
//每次都对相同的纵坐标的数进行一次统一的计算
for(int j=last;j<=i;j++){
if(!vis[a[j].x]){
vis[a[j].x]=1;
update(a[j].x);
}
ll vl=query(0,a[j].x,0,N-1,0);
//当j==i时,没有最右边的限制,因此我们就把N-1作为最右边的边界
ll vr=query(0,(j==i)?N-1:a[j+1].x-1,0,N-1,0) - query(0,a[j].x-1,0,N-1,0);
res+=vl*vr;
}
last=i+1;
}
}
printf("%lld\n",res);
return 0;
}
感谢您的支持
-------------本文结束感谢您的阅读-------------