简单数数题。要是最后 30min 没写作业说不定就过了。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意解析：定义一个长度为 nnn 的数组 AAA 的“峰”与“谷”如下：
* 若 2≤i≤n2\le i\le n2≤i≤n 且 Ai−1<Ai>Ai+1A_{i-1}\lt A_i\gt A_{i+1}Ai−1 <Ai >Ai+1 ，则 iii 为 AAA 的峰。
* 若 2≤i≤n2\le i\le n2≤i≤n 且 Ai−1>Ai<Ai+1A_{i-1}\gt A_i\lt A_{i+1}Ai−1 >Ai <Ai+1 ，则 iii 为 AAA 的谷。
定义一个数组 AAA 为山峰数组当且仅当它的峰的数量严格大于谷的数量。
给定一个 nnn 的排列 AAA，求 AAA 有多少个子序列为山峰数组。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
我们考虑什么情况下才是山峰数组。
注意到不算两边的话，一定是“...峰谷峰谷峰谷...”状的。
再进一步，分类讨论一下，可以发现一个长度为 kkk 的数组 BBB 是山峰数组当且仅当 B1<B2B_1\lt B_2B1 <B2 且 Bn−1>BnB_{n-1}\gt B_nBn−1 >Bn 。
现在问题就简单了。
先考虑暴力。
我们可以暴力枚举 i<j≤k<li\lt j\le k\lt li<j≤k<l 分别作为子数组的 B1,B2,Bk−1,BkB_1,B_2,B_{k-1},B_kB1 ,B2 ,Bk−1 ,Bk ，如果 Ai<AjA_i\lt A_jAi <Aj 且 Ak>AlA_k\gt A_lAk >Al ，则不论中间是啥，都可以构成山峰数组，对答案的贡献为 max{2k−j−1,1}\max\{2^{k-j-1},1\}max{2k−j−1,1}（因为 j=kj=kj=k 时前面的是 12\frac{1}{2}21 所以要对 111 取最大值）。这样是 O(n4)O(n^4)O(n4) 的。
然后推式子。
∑i=1n∑j=i+1n∑k=jn∑l=k+1n[Ai<Aj][Ak>Al]max{2k−j−1,1}=∑i=1n∑j=i+1n[Ai<Aj]∑k=jn∑l=k+1n[Ak>Al]max{2k−j−1,1}=∑j=2n−1∑k=jn(∑i=1j−1[Ai<Aj])(∑l=k+1n[Al<Ak])max{2k−j−1,1}\sum_{i=1}^n\sum_{j=i+1}^n\sum_{k=j}^n\sum_{l=k+1}^n [A_i\lt A_j][A_k\gt A_l]\max\{2^{k-j-1},1\}\\ =\sum_{i=1}^n\sum_{j=i+1}^n[A_i\lt
A_j]\sum_{k=j}^n\sum_{l=k+1}^n [A_k\gt A_l]\max\{2^{k-j-1},1\}\\ =\sum_{j=2}^{n-1}\sum_{k=j}^n(\sum_{i=1}^{j-1}[A_i\lt A_j])(\sum_{l=k+1}^n [A_l\lt A_k])\max\{2^{k-j-1},1\}\\ i=1∑n j=i+1∑n k=j∑n l=k+1∑n [Ai <Aj ][Ak >Al ]max{2k−j−1,1}=i=1∑n j=i+1∑n [Ai <Aj ]k=j∑n l=k+1∑n [Ak >Al
]max{2k−j−1,1}=j=2∑n−1 k=j∑n (i=1∑j−1 [Ai <Aj ])(l=k+1∑n [Al <Ak ])max{2k−j−1,1}
显然我们可以通过树状数组 O(nlogn)O(n\log n)O(nlogn) 预处理出 ∑j=1i−1[Aj<Ai]\sum_{j=1}^{i-1} [A_j\lt A_i]∑j=1i−1 [Aj <Ai ] 与 ∑j=i+1n[Aj<Ai]\sum_{j=i+1}^{n} [A_j\lt A_i]∑j=i+1n [Aj <Ai ]，分别记作 prei,sufi\text{pre}_i,\text{suf}_iprei ,sufi 。则原式为：
∑i=2n−1∑j=inpreisufjmax{2j−i−1,1}\sum_{i=2}^{n-1}\sum_{j=i}^n\text{pre}_i\text{suf}_j\max\{2^{j-i-1},1\}\\ i=2∑n−1 j=i∑n prei sufj max{2j−i−1,1}
max\maxmax 有点难搞，拆开吧。
∑i=2n−1preisufi+∑i=2n−1∑j=i+1npreisufj2j−i−1\sum_{i=2}^{n-1}\text{pre}_i\text{suf}_i+\sum_{i=2}^{n-1}\sum_{j=i+1}^n\text{pre}_i\text{suf}_j2^{j-i-1}\\ i=2∑n−1 prei sufi +i=2∑n−1 j=i+1∑n prei sufj 2j−i−1
然后继续转化。注意到 222 的整数次幂是可逆的。所以：
∑i=2n−1preisufi+∑i=2n−1∑j=i+1npreisufj2j−i−1=∑i=2n−1preisufi+∑i=2n−1∑j=i+1npreisufj2j2i+1=∑i=2n−1preisufi+∑i=2n−1prei2i+1∑j=i+1nsufj2j\sum_{i=2}^{n-1}\text{pre}_i\text{suf}_i+\sum_{i=2}^{n-1}\sum_{j=i+1}^n\text{pre}_i\text{suf}_j2^{j-i-1}\\
=\sum_{i=2}^{n-1}\text{pre}_i\text{suf}_i+\sum_{i=2}^{n-1}\sum_{j=i+1}^n\text{pre}_i\text{suf}_j\frac{2^j}{2^{i+1}}\\ =\sum_{i=2}^{n-1}\text{pre}_i\text{suf}_i+\sum_{i=2}^{n-1}\frac{\text{pre}_i}{{2^{i+1}}}\sum_{j=i+1}^n\text{suf}_j2^j\\ i=2∑n−1 prei sufi +i=2∑n−1 j=i+1∑n prei sufj 2j−i−1=i=2∑n−1
prei sufi +i=2∑n−1 j=i+1∑n prei sufj 2i+12j =i=2∑n−1 prei sufi +i=2∑n−1 2i+1prei j=i+1∑n sufj 2j
我们只需要递推求出 ∑j=i+1nsufj2j\sum_{j=i+1}^n\text{suf}_j2^j∑j=i+1n sufj 2j 即可。
代码如下：
时间复杂度：O(nlogn)O(n\log n)O(nlogn)。
