bzoj 4881: [Lydsy1705月赛]线段游戏

链接：https://www.lydsy.com/JudgeOnline/problem.php?id=4881

一个正解比较优秀的题，但是可以被各种乱搞搞过的题。。
首先题目的意思就是要你分成两个上升子序列问你有多少方案

先说一个复杂的方法
考虑DP，$f_i$表示第一个子序列以i结尾且$[1,i?1]$里面第二个子序列的最后一位比$i+1$小的方案有多少个
那么答案就是我们从后往前扫，如果$[i,n]$是递增的，那么就加上$f_i$
至于转移，可以枚举第二个子序列的最后一个$j$，那么显然要满足$[j+1,i]$是递增的，那么$f_i$就加上$f_j$
容易发现$j$是连续的一段
那么$j$就要满足两个限制，第一个是$a_j<a_i+1$，第二个是$L<=j<=i?1$
对于权值开个树状数组维护即可

然后说一个可能没那么复杂的方法
考虑找到全串的最大值的位置，设为$A$
那么显然$A$和$[A+1,n]$必须分为两段
把这两段的开头设为$A$,$B$
然后把$[A,n]$删掉，变为一个子问题
考虑把两段合并
设前面一段的最大值位置为$now$，这个的第二段是now1（当然有不存在的情况，随便判判就好了）
那么有两个合并方法，第一个是$now$接在$A$前面，第二个是接在$B$前面
容易发现，第一个是一定可以接上的，如果可以接上第二个，那么就有两个接法，否则就是一个
不难发现，相接以后，两个方案都等价于A变为now，如果有now1的话，B变为now1，否则不变
无解的情况当且仅当$[now1,A]$不是递增的，暴力判就好了
容易发现，整个过程是线性的，如果用基数排序实现排序的话就可以做到$O(n)$了

最后说一下正解的方法
如果最长下降子序列>=3，那么就就显然无解了
那么剩下就都是有解的
把这个判掉，考虑一个暴力做法
就是逆序对之间连边，那么答案就是$2^{|联通块个数|}$
容易发现边数是$O(n^2)$的
但其实，如果你从前往后扫，对于每一个连通块，显然只需要记录最大值就够了
因此得到一个做法，就是每扫到一个数，就把之前比他大的都拿出来，合并成一个最大的丢回去
最后看看有多少个元素，就是连通块的个数了
整个过程可以用一个set来维护，那么复杂度就是$O(nlogn)$了

以上就是本题暂时能想到的三个方法，各位看官挑一个自己喜欢的做法吧。。
我个人就是第二个。。但感觉代码贴出来就不好看了，那么就自己实现吧（雾