CF5E 题解
$\text{Description}$
环上有 $n$ 个点，每个点有高度，定义两个点能互相看到当且仅当存在一段端点为该两点的圆弧内任意点高度都不超过该两点。求能相互看见的点对数。
$1\le n\le 10^6$
$\text{Solution}$
首先对高度离散化。
由于环可以任意循环移位，我们任取某一个最大值作为这个环的首端，这样除了最大值，其它任意元素绕一圈回来都只能撞到最大值，无法继续前进。
接下来考虑将能相互看见的点分两类。第一类是两点高度相同，对此我们可以按高度从大到小进行计算，让高于它的节点将环分成若干段，对于每段分别计算答案；第二类是两点高度不同，我们考虑在高度较低的点计算，这样只需考虑左右第一个高度大于它的点，同样从大到小计算，二分出左右的值，注意在环上可能这两个点都是环的第一个点，需要减去重复的值。
上述过程可以通过 std::set 维护，时间复杂度 $\mathcal O(n\log n)$。
$\text{Code}$
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
| #include<bits/stdc++.h>
#define REG register
using namespace std;
typedef long long ll;
const int N=1e6+10;
inline void read(int& x){
static char c;
while(!isdigit(c=getchar()));x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
int n,M,C;
int T[N],srt[N],H[N];
vector<int> Pos[N];
set<int> Occ;
set<int>::iterator it;
ll Ans;
inline void Work(){
read(n);
for(REG int i=1;i<=n;++i) read(T[i]),srt[i]=T[i];
sort(srt+1,srt+n+1),C=unique(srt+1,srt+n+1)-srt-1;
for(REG int i=1;i<=n;++i){
T[i]=lower_bound(srt+1,srt+C+1,T[i])-srt;
if(T[i]>T[M]) M=i;
}
for(REG int i=1;i<=n;++i) H[i]=T[(M+i-2)%n+1],Pos[H[i]].push_back(i);
Occ.insert(n+1);
for(REG int i=C;i;--i){
int cnt=0,lst=0;
for(int P:Pos[i]){
it=Occ.lower_bound(P);
if((*it)^lst) Ans+=1ll*cnt*(cnt-1)/2,cnt=1,lst=*it;
else ++cnt;
if(i==C) continue;
if(*it<=n) Ans+=2;
else
if(*(--it)==1) ++Ans;
else Ans+=2;
}
Ans+=1ll*cnt*(cnt-1)/2;
for(int P:Pos[i]) Occ.insert(P);
}
printf("%lld\n",Ans);
}
int main(){Work();}
|
