abc439_f F - Beautiful Kadomatsu dp+FIT
动态规划难题
题目链接：https://atcoder.jp/contests/abc439/tasks/abc439_f
题意：
思路：下面和
含义相同，ac代码用树状数组实现前缀和快速查询
通过观察得出的一个结论，由于给出的是排列（permutation 指一个长度为 n 的数组，包含 1 到 n，每个数恰好出现一次。）所以发现每个数字都不一样，每对数构成的几何关系么就是上升要么就是下降，题目中要我们找合法的子序列，也就是从原序列中随机抽出一些数字按原来的顺序排列的出的子序列满足“山谷”数量小于“山峰”数量，山谷山峰就是题目中的y和x的含义，枚举各种情况的子序列x1 x2 x3 x4 ...... xn-1 xn得出在一开始的两个数满足<
和最后两个数满足
>
的子序列就是满足题意的，现在考虑位置 i 上的数作为子序列中的
，对于
我们只需要找比
小的就行，所以统计L[i]表示在i之前小于P[i]的个数，由于是排列，所以R[i]=P[i]-1-L[i]表示在位置i之后小于P[i]的个数，在考虑
之前的序列的结构情况，要么是一个比
小的数，也就是L[i]个数都满足情况，还有就是存在两个数
和
满足
和
并且i < j < i，还有存在其它多位数的情况构成的序列结构满足最终的子序列是满足题意的，我们先考虑位置 i 前面仅有一个和两个元素的情况，对于三个和四个元素的情况可以由一个和两个的情况继承而来。我们可以用变量pre表示位置i 前有多少个序列（大于1个元素构成的前半部分序列）满足使得最终选出的子序列满足题意，那么对于每个位置上的能选出的合法的子序列的个数就是 ( pre+ L[i] ) * R[i]，然后再更新 pre = pre*2 + L [ i ] ；
pre* 2是在做什么？
假设在处理之前，我们已经有了 3 个半成品序列：
,
,
。
现在遇到了，对于这每一个半成品，我们都有两种选择：
不把
放入序列：
,
,
依然是合格的半成品，数量为 pre。
把
放入序列：由于中间部分没有大小限制，放入
后，它们变成了更长的半成品
*,
*,
*，数量也是pre。
所以，原本的pre就变成了 pre* 2。这本质上是在计算子集的数量（每个元素选或不选）。
+ L[i]是在做什么？
除了继承和扩展旧的半成品，我们还会在当前位置新产生一批半成品。
代表在 i 左边有多少个比
小的数。
每一个比
小的数
，j < i , 都可以和
组成一对新的“开头”：S*。
由于
<
，这正好满足了“开头必须上升”的条件。
所以，我们要把这 L[i] 对新生产出来的“长度为 2 的半成品”加入到pre中。
AC代码：
void solve() { ll n;cin>>n; vector<ll>a(n+1),bit(n+1,0),l(n+1,0); auto up=[&](ll id) { while (id<=n)bit[id]++,id+=lowbit(id); }; auto sum=[&](ll id) { ll res=0; while (id)res+=bit[id],id-=lowbit(id); return res; }; ll pre=0,ans=0; rep(i,1,n) { cin>>a[i];l[i]=sum(a[i]);up(a[i]); ll r=a[i]-1-l[i]; ans=add(ans,mul(add(pre,l[i]),r)); pre=add(mul(pre,2),l[i]); } cout<<ans<<endl; }