CF2205D

择要：单调栈

前置芝士：洛谷单调栈模板题
原题指路：CF原题 洛谷翻译版
题意转化

要求删除次数最少，相称于求出一个最长的 cool。
而显然：求最长的 cool 相称于是求最长的单谷序列。
由于多谷则一定有峰，那么还需再删；
而单调序列相称于一端点是谷，故也可以用单谷序列去思量。
云云，原题题意就转化为求最长单谷序列的长度。
而答案最小删除次数则用原分列长度减去此值即可。
思绪

那么怎样求最长单谷序列的长度？
可以想到用单调栈完成。

• 先从左往右扫一遍，维护一个单减栈。
  不难发现，当新参加的元素大于栈顶元素 \(a_x\) 时，栈内元素序列便是 \(a_x\) 左侧含 \(a_x\) 的最大单减序列，而栈的巨细便是其长度。
  
• 再从右往左扫一遍，维护一个单减栈。
  不难发现，当新参加的元素大于栈顶元素 \(a_x\) 时，栈内元素序列便是 \(a_x\) 右侧含 \(a_x\) 的最大单增序列，而栈的巨细便是其长度。
  

对于一个元素 \(a_x\) 而言，把上述的两种序列拼起来，可见就得到了 \(a_x\) 为谷的最大单谷序列。
由于 \(a_x\) 被数了两次，以是 \(a_x\) 为谷的最长单谷序列长度 \(mxl_x =  dl_x + dr_x - 1\)。
留意别忘了每次末了还要处置惩罚留在栈中的元素。
那么就做完了。
举例

这么讲大概有点抽象。我以样例中的一组数据大概模拟一遍该过程。
样例中的一组数据是如许的：
4 1 3 2 5

• 从左到右扫，维护单减栈。
  
  
  
  • 压入 \(4\)，栈内 4。
    
  • 压入 \(1\)，栈内 4 1。
    
  • 压入 \(3\)。
    \(3 > 1\)，以是弹出 \(1\)。
    可见此时栈内的 4 1 就是 \(1\) 左侧含 \(1\) 的最大单减序列。求出相应的有关值。
    栈内 4 3。
    
  • 压入 \(2\)，栈内 4 3 2。
    
  • 压入 \(5\)，栈内全部元素均比它小，以是都弹出，并求出相干对应值。
    栈内 5。
    
  末了弹出栈中全部元素。与前面逻辑同理，此时的每一个元素的 \(dl_x\) 值仍为它即将弹出前的栈的巨细。
  
  
• 从右往左扫，维护单减栈。
  逻辑也是一样的，这里就不赘述了。
  

代码

有解释版本[code]#includeusing namespace std;const int N = 5e5 + 10;int T;int n, a[N];int s[N], tops;int dl[N], dr[N];int ans;int main(){                scanf("%d", &T);        while(T--){                scanf("%d", &n);                for(int i = 1; i  0){                    dl[s[tops]] = tops;                    --tops;                }                                tops = 0;                for(int i = n; i >= 1; --i){                         if(tops < 1){                                s[++tops] = i;                                continue ;                        }                        while(a[s[tops]] < a && tops > 0){                                dr[s[tops]] = tops;                                --tops;                        }                        s[++tops] = i;                }                while(tops > 0){                    dr[s[tops]] = tops;                    --tops;                }                                                int mxl = -1;                for(int i = 1; i = 1; --i){ //从右到左扫，维护单减栈                         if(tops < 1){                                s[++tops] = i;                                continue ;                        }                        while(a[s[tops]] < a && tops > 0){ //记得判断tops                                 dr[s[tops]] = tops;                                --tops;                        }                        s[++tops] = i;                }                while(tops > 0){ //记得处置惩罚栈中剩余元素                     dr[s[tops]] = tops;                    --tops;                }                                                int mxl = -1;                for(int i = 1; i