链接:
Links

题意:
坐标系上有n个塔,对于任意两个塔,如果存在一个平行于坐标轴的矩形仅包含这两个塔,可以将它们连接。(包含的含义是位于矩形内部或其边缘)输出最多能够连接多少对塔。

思路:
我们只要对于每个点(xi,yi),处理y坐标小于yi的点,
对于x坐标小于xi的点,按x坐标递增顺序维护一个y坐标单调递减队列,
对于x坐标大于xi的点,按x坐标递减顺序维护一个y坐标单调递减队列,
统计一下就是答案。
这样做的复杂度为o(n^2)
现在的问题是如何维护(1-当前点)的单调队列的大小。
可以用线段树分割维护单调队列。因为单调队列的右端是变化的左端永远是1。
所以可以先访问线段树的右端,然后记录当前单调队列左端最大值,然后再线段树左端进行二分,合并。
例如线段树是(1-8)现在要求(1-6)的单调队列。(1-6)显然分成(1-4)(5-6)。
我们先访问(5-6),然后记录其单调队列的大小,和其左端的值left。
然后再(1-4)的单调队列中二分left的值,然后去掉小于left的部分,然后再记录。
这种做法复杂度为o(nlogn^2)

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long int64;
const int maxn = 100000+10 , maxv = maxn*4 , inf = 2000000000;
int n,m,ys[maxn],Right;
int64 ans;
struct node { int x,y; } v[maxn];
vector <node> t[maxv];
void init()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&v[i].x,&v[i].y);
ans=0;
}
void Sort(int l,int r)
{
int i=l,j=r;
node mid=v[rand()%(r-l+1)+l];
do
{
while ( v[i].x<mid.x || ( v[i].x==mid.x && v[i].y<mid.y ) ) i++;
while ( v[j].x>mid.x || ( v[j].x==mid.x && v[j].y>mid.y ) ) j--;
if (i<=j)
swap(v[i++],v[j--]);
}
while (i<=j);
if (l<j) Sort(l,j);
if (i<r) Sort(i,r);
}
int binary( int x )
{
int l=1,r=m;
while (l<r)
{
int mid=(l+r)>>1;
if ( ys[mid]<x ) l=mid+1;
else r=mid;
}
return l;
}
void pre()
{
for (int i=1;i<=n;i++)
v[i].y*=-1,ys[i]=v[i].y;
sort(ys+1,ys+1+n);
m=1;
for (int i=2;i<=n;i++)
if (ys[i]!=ys[m]) ys[++m]=ys[i];
Sort(1,n);
for (int i=0;i<maxv;i++) t[i].clear();
}
void ins( int x,int a,int b,int l,int r,int X,int Y )
{
while ( t[x].size() && t[x][t[x].size()-1].y<=Y )
t[x].pop_back();
node v; v.x=X,v.y=Y;
t[x].push_back(v);
if ( a<=l && r<=b ) return;
int mid=(l+r)>>1;
if ( a<=mid ) ins(x+x,a,b,l,mid,X,Y);
if ( mid<b ) ins(x+x+1,a,b,mid+1,r,X,Y);
}
int64 find( int x,int a,int b,int l,int r )
{
if ( a<=l && r<=b )
{
int L=0,R=t[x].size()-1;
if ( R<0 || t[x][R].x<=Right ) return 0;
while ( L<R )
{
int Mid=(L+R)>>1;
if ( t[x][Mid].x>Right ) R=Mid;
else L=Mid+1;
}
Right=t[x][t[x].size()-1].x;
return t[x].size()-R;
}
int mid=(l+r)>>1;
int64 ans=0;
if ( mid<b ) ans+=find(x+x+1,a,b,mid+1,r);
if ( a<=mid) ans+=find(x+x,a,b,l,mid);
return ans;
}
void solve()
{
for (int i=1;i<=n;i++)
{
Right=-inf;
int rank=binary(v[i].y);
ans+=find(1,1,rank,1,m);
ins(1,rank,rank,1,m,v[i].x,rank);
}
}
void del()
{
Sort(1,n);
for (int i=1;i<=n;)
{
int tot=0;
while ( i+1<=n && v[i].x==v[i+1].x ) i++,tot++;
ans-=int64(tot);
i++;
}
for (int i=1;i<=n;i++) swap(v[i].x,v[i].y);
Sort(1,n);
for (int i=1;i<=n;)
{
int tot=0;
while ( i+1<=n && v[i].x==v[i+1].x ) i++,tot++;
ans-=int64(tot);
i++;
}
}
int main()
{
init();
pre();
solve();
pre();
solve();
del();
printf("%lld\n",ans);
return 0;
}