问题描述
小布的团队在山洞里发现了一幅巨大的壁画，壁画上被标记出了 $N$ 个点，经测量发现这 $N$ 个点的水平位置和竖直位置是两两不同的。小布认为这幅壁画所包含的信息仅与这 $N$ 个点的相对位置有关，因此不妨设坐标分别为 $(1, y_1) , (2, y_2), …, (n, y_n)$ 其中 $y_1$ 到 $y_n$ 是 $1$ 到 $N$ 的一个排列。小布的团队打算研究在这幅壁画中包含着多少个图腾，其中闪电图腾的定义图示如下（图腾的形式只与 4 个纵坐标值的相对大小排列顺序有关）： 
崇拜高山的部落有两个氏族，因而山峰图腾有如下两种形式，左边为 A 类，右边为 B 类（同样，图腾的形式也都只与 4 个纵坐标值的大小排列顺序有关）： 
小布的团队希望知道，这 $N$ 个点中两个部落图腾数目的差值。因此在本题中，你需要帮助小布的团队编写一个程序，计算闪电图腾数目减去山峰图腾数目的值，由于该值可能绝对值较大，本题中只需输出该值对 $16777216$ 的余数。
输入
第一行包含一个整数 $N$ ($N≤200000$) 为点的数目。 接下来一行包含 $N$ 个整数，分别为 $y1,y2,…,yn$。
输出
仅包含一个数，表示闪电图腾数目与山峰图腾数目的差值对 16777216 的余数。
思路
超级神仙的一道题。
我们先考虑所有的六种情况 $1234,1243,1324,1342,1423,1432$，然后题目要求的是 $1324-1243-1432$ 的数量。然后可以发现形如 $1xxx,12xx,13xx,1x2x,1234,1243$ 的这些情况是可以求出来的（可能还有其他的情况）。然后就将题目要求的情况变换成我们能求出的情况： $1324-1243-1432$ $=(1x2x-1423)-(12xx-1234)-(14xx-1423)$ $=1x2x-12xx+1234-14xx$ $=1234+13xx+1x2x-1xxx$
我们设 $l_i=\sum_{j=1}^{i}[a_j<a_i]$，$r_i=\sum_{j=i}^{n}[a_j<a_i]$
$1xxx$ 的数量比较好求，就是： $1234$ 的数量也不难，枚举 $3$ 的位置 $i$，那么 $4$ 的情况数就是 $n-r_i-i$，$12$ 的情况数就是 $\sum_{j=1}^{i} ([a_j<a_i] l_i)$，总数量就是： $13xx$ 的数量同样枚举 $3$ 的位置 $i$，那么 $4$ 的情况数还是 $(n-r_i-i)$，$132$ 的情况数可以先计算 $12$ 的情况数 $\sum_{j=i}^{n}([a_j<a_i] (a_j-1))$ 然后减去 $12$ 同时在 $3$ 右边的情况 ${r_i}\choose{2}$，总数量就是：
$1x2x$ 的数量可以枚举 $2$ 的位置 $i$，那么 $2$ 后面 $x$ 的情况数就是 $(n-r_i-i)$，$1x2$ 的情况数先可以计算 $1x$ 和 $x1$ 的情况数 $l_i*(i-1)$，然后减去两个数都比 $2$ 小的情况数 ${l_i \choose 2}$，最后减去 $x$ 在 $1$ 前的情况数 $\sum_{j=1}^{i} ([a_j<a_i]j)$，总数量就是： 所有这些东西都可以用树状数组在 $O(n\log n)$ 内维护。
代码
1 |
|
无论 Snuke 怎么走都会符合这个模型，只是可能有一些部分不会出现。如果发现了这个，后面只要直接 DP 就可以了。设 $f[i][j]$ 为第 $i$ 个位置属于第 $j$ 个部分的代价，转移时加上每个部分相应的代价即可。