鄂州网站建设企业推广手机网站建设教材

鄂州网站建设企业推广,手机网站建设教材,如何在微信上做推广,品牌推广型网站题面 Starry Landscape Photo 问题描述 在 AtCoder 行星上看到的夜空中#xff0c;有 NNN 颗星星#xff0c;这些星星从东到西排成一条直线。从东方数起的第 iii 颗星#xff08;1≤i≤N1 \le i \le N1≤i≤N#xff09;是这些星星中第 BiB _ iBi​ 亮的。 Takahashi 决…题面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 1l1、… \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×1051 ≤ B i ≤ N 1 \le B _ i \le N1≤Bi​≤N1 ≤ i ≤ N 1 \le i \le N1≤i≤NB i ≠ B j B _ i \neq B _ jBi​Bj​1 ≤ i j ≤ N 1 \le i j \le N1≤ij≤N所有输入值都是整数。输入输入通过标准输入给出格式如下N NNB 1 B 2 … B N B _ 1 \ B _ 2 \ \dots \ B _ NB1​B2​…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 1i1个故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∑i1N​Li​Ri​∑i1N​Li​(i1−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(log2​N)时间内求出每个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(Nlog2​N)总时间复杂度O ( N log ⁡ 2 N ) O(N \log _ 2 N)O(Nlog2​N)。代码#includebits/stdc.h#defineintlonglongusingnamespacestd;constintmaxn5e5;intb[maxn5];intpos[maxn5];intk[maxn*25];intn;intans0;intlowbit(intx){returnx(-x);}voidadd(intx){for(;xmaxn*2;xlowbit(x)){k[x];}}intquery(intx){intres0;for(;x;x-lowbit(x)){resk[x];}returnres;}voidsolve(){cinn;for(inti1;in;i){cinb[i];pos[b[i]]i;}for(inti1;in;i){add(pos[i]);inttmpquery(pos[i]);anstmp*(i-tmp1);}coutans\n;}signedmain(){intt1;while(t--){solve();}return0;}