[NOIP 2021 多校联训 Round 2]I love sort
该加训了啊。
题意简述
给定序列 \(\{ a_i\}\),你可以将这个序列分割成 \(K\) 组，对于每组的元素 \(\{ a_i\}\) 的下标都是连续的。
现在你可以对每组的元素进行排序，将组内元素排成单调不递减的形式，排序后你要使得整个序列的所有元素也处于单调不递减的状态，求 \(K\) 的最大值可以为多少。
考虑进行分段操作后的情况，第 \(i\) 段的最小值一定不小于前一段最大值。
开个栈，最大值和最小值不好记录就把这两个参数扔栈里用 pair 记录。
初始栈顶值为 {a[1],a[1]}。
从 \(2\) 开始枚举每个数，当这个数小于栈顶的最大值，就是需要合并的情况，不断更新最小值和最大值和弹出，最后再加入。
#include<bits/stdc++.h>
using namespace std;
int a[1000100];
stack<pair<int,int>> s;
int main(){int n;cin>>n;for(int i=1;i<=n;i++) {cin>>a[i];}s.push({a[1],a[1]});//minn maxnint ans=1;for(int i=2;i<=n;i++) {pair<int,int> t={a[i],a[i]};while(!s.empty()&&a[i]<s.top().second) {t.first=min(t.first,s.top().first);t.second=max(t.second,s.top().second);s.pop();}s.push(t);}cout<<s.size();return 0;
}