题面
Starry Landscape Photo
问题描述
在AtCoder行星上看到的夜空中，有N NN颗星星，这些星星从东到西排成一条直线。从东方数起的第i ii颗星（1 ≤ i ≤ N 1 \le i \le N1≤i≤N）是这些星星中第B i B _ iBi亮的。
Takahashi决定按照以下步骤拍摄夜空的照片：
1.选择一对整数（l , r l , rl,r），满足1 ≤ l ≤ r ≤ N 1 \le l \le r \le N1≤l≤r≤N，并设置相机，使得从东数起的第l ll、第l + 1 l + 1l+1、… \dots…、第r rr颗星都能进入画面，而其他星星不会进入画面。
2.选择一个整数b bb，满足1 ≤ b ≤ N 1 \le b \le N1≤b≤N，打开快门，使得所有亮度排名在第1 11到第b bb位之间（且位于画面中的）星星被捕捉，而其他星星不会被捕捉。
但是，他不能拍摄不包含任何星星的照片。
求出在这种方式下拍摄的照片中，可以捕捉到的不同星星集合的数量。
约束条件
1 ≤ N ≤ 5 × 1 0 5 1 \le N \le 5 \times 10 ^ 51≤N≤5×105
1 ≤ B i ≤ N 1 \le B _ i \le N1≤Bi≤N（1 ≤ i ≤ N 1 \le i \le N1≤i≤N）
B i ≠ B j B _ i \neq B _ jBi=Bj（1 ≤ i < j ≤ N 1 \le i < j \le N1≤i<j≤N）
所有输入值都是整数。
输入
输入通过标准输入给出，格式如下：
N NN
B 1 B 2 … B N B _ 1 \ B _ 2 \ \dots \ B _ NB1B2…BN
输出
输出答案。
思路
tag \text{tag}tag：数学树状数组
根据题意，易知一张照片由左端点、右端点与感光度（照片中最暗亮度值）决定。令pos i \text{pos} _ iposi为亮度为i ii的星星的位置，则满足i ∈ [ 1 , N ] i \in [1 , N]i∈[1,N]的三元数对( l , r , pos i ) (l , r , \text{pos} _ i)(l,r,posi)，其l ll与r rr取值分别有L i L _ iLi和R i R _ iRi种，其中L i L _ iLi为同时满足j ≤ pos i j \le \text{pos} _ ij≤posi与B j ≤ i B _ j \le iBj≤i的j jj的个数，R i R _ iRi为同时满足j ≥ pos i j \ge \text{pos} _ ij≥posi与B j ≤ i B _ j \le iBj≤i的j jj的个数。根据乘法原理，照片种数为左端点个数与右端点个数的乘积，又因满足B j < i B _ j < iBj<i的j jj的个数为i + 1 i + 1i+1个，故ans = ∑ i = 1 N L i R i = ∑ i = 1 N L i ( i + 1 − L i ) \text{ans} = \sum _ {i = 1} ^ {N} L _ i R _ i = \sum _ {i = 1} ^ {N} L _ i (i + 1 - L _ i)ans=∑i=1NLiRi=∑i=1NLi(i+1−Li)。
由于1 ≤ N ≤ 5 × 1 0 5 1 \le N \le 5 \times 10 ^ 51≤N≤5×105，所以需在O ( log 2 N ) O(\log _ 2 N)O(log2N)时间内求出每个i ii的L i L _ iLi。考虑用树状数组。令i ii为升序，则每次计算时，在pos i \text{pos} _ iposi处增加一个星星，并计算位置小于等于pos i \text{pos} _ iposi的个数，即L i L _ iLi。
预处理pos \text{pos}pos需要O ( N ) O(N)O(N)，树状数组O ( N log 2 N ) O(N \log _ 2 N)O(Nlog2N)，总时间复杂度O ( N log 2 N ) O(N \log _ 2 N)O(Nlog2N)。
代码
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintmaxn=5e5;intb[maxn+5];intpos[maxn+5];intk[maxn*2+5];intn;intans=0;intlowbit(intx){returnx&(-x);}voidadd(intx){for(;x<=maxn*2;x+=lowbit(x)){k[x]++;}}intquery(intx){intres=0;for(;x;x-=lowbit(x)){res+=k[x];}returnres;}voidsolve(){cin>>n;for(inti=1;i<=n;i++){cin>>b[i];pos[b[i]]=i;}for(inti=1;i<=n;i++){add(pos[i]);inttmp=query(pos[i]);ans+=tmp*(i-tmp+1);}cout<<ans<<"\n";}signedmain(){intt=1;while(t--){solve();}return0;}
)
