原题链接：https://newoj.daimayuan.top/p/5835?tid=6ad1f4e08dcc4dd4642ef88f
思路
-
可以选择dp，然后发现与贪心本质相同。 看到题目有一个很显然的dp：
\[ f[i]=\min_{1 \le j即考虑到第i个位置，最少需要多少次划分。
注意到这个dp数组具有单调性，则从尽量往前的dp状态转移到第i个位置 答案为第n个位置的dp值
-
这个时候其实就已经时贪心了，那么接下来考虑转移条件： 为了表达方便，我们设（x,y)表示从下标从x（含）到y（含）的原数组的有序序列
- 首先需要保证（j+1,i)非降序，因为后续的插入并不会使现在确定的将要插入的序列中的元素相对顺序改变，也就是如果现在出现升序了，以后这两个元素也还是升序。
- 然后需要保证在下标j及之前插入的元素中（之前插入的元素要保证有序，答案才不会不合法），存在两个相邻元素使得他们之间能够放下（j+1,i)
形式化的，假设下标j及之前存在两个相邻元素：x,y，使得\(x\le \min_{j+1 \le k \le i}a_i\)，\(y\ge\min_{j+1 \le k \le i}a_i\) - 转移的j最小
-
那么思路已经考虑完了，如何维护：
- 之前已经确定放下的元素可以直接扔进set中，方便之后查询相对大小，这样可以省掉一颗线段树
- 类似指针，建立一个指针 l（初始为0），表示当前能够合法转移到的最前面的元素下标
- 对于当前元素：
如果当前元素\(a_i\)破坏了以前元素的单调性，那么（l,i)一定无法作为一个新序列进行插入，违反了转移条件2。那么一定将之前的最优转移转移完毕后开启新一段，直接将（l,i-1)插入新序列（也就是插入set)，并将操作数综合\(cnt\)加1记录答案，赋值\(l=i\)，由于之前已经保证合法，可以直接转移。
如果当前元素\(a_i\)并没有破环单调性，但使得set中不存在两元素使得（l,i)能够插入，那么模仿之前，i与（l,i-1)一定不能作为同一个序列插入，直接将之前维护合法的（l,i-1)插入新序列，（l,i-1)插入新序列（也就是插入set)，并将操作数综合cnt加1记录答案。 那么应该如何判断是否存在两元素呢？可以使用set自带的lower_bound和upper_bound判断，对于当前区间，由于单调不降，最大值与最小值一定分别为\(a_i\)和\(a_l\)。仅需查看之前插入的数中第一个大于等于\(a_i\)的元素和第一个大于\(a_l\)的元素是不是同一个即可，特判\(a_i\)=\(a_l\)的情况为可以放。这里分别查询“大于”和“大于等于”的原因是有细节，如果\(a_l\)等于插入的第一大于等于\(a_i\)的元素的第一个已经插入的比它小的元素，那么用“大于等于”会误判，而使用“大于”避免了这样的问题，但这样如果\(a_i\)=\(a_l\)的话也会出问题，那么特判。时间复杂度O（\(\log n\))
如果当前元素完全不在以上两种情况之中，则当前元素可以放在当前将要转移的区间中一起转移，不做任何变动。
-
这样就完成了，对于每个\(i\),都有O（\(\log n\))，则总体复杂度O(\(n\log n\))
代码
#include
using namespace std;
int n;
int a[1000005];
set st;
int f[1000005];
int main()
{freopen("ryo.in","r",stdin);freopen("ryo.out","w",stdout);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];} int l=1;for(int i=1;i<=n;i++){if(a[i-1]<=a[i]){while(l<=i-1&&(a[l]!=a[i]&&st.upper_bound(a[l])!=st.lower_bound(a[i]))){st.insert(a[l]);l++;}f[i]=f[l-1]+1;}else{while(l