很菜。
CF1905C
考虑先找到原串中的字典序最大串，这个直接单调栈求出。然后我们对这个字串 \(t\) 执行操作，\(t\) 是不上升的所以肯定能排好序，我们在找 \(t\) 的时候顺便记录下 \(t\) 在原串中的位置，然后把排好序的 \(t\) 放回去判断，如果是不下降的则输出排好 \(t\) 所需的次数，正确性手玩得到。
CF1905D
先求出原排列的前缀 mex 然后考虑循环移位后产生的影响以及怎么维护这个序列。手模，向左移位时将所有大于 \(a_i\) 的前缀 mex 变成 \(a_i\)，注意最后一个 mex 一定是 \(n\)，操作过程珂以用一个 deque 维护，但是直接维护是 \(O(n^{\mathbf{\small{2}}})\) 的，观察到在移位过程中会有很多连续相同的mex，考虑记录下每个 mex 的个数把他们缩在一起，具体而言在 deque 里存一个二元组 \((x,y)\) 表示有 \(y\) 个 \(x\)，每次弹出掉队首，对于队尾 \(>a_i\) 的元素暴力全部弹出，并插入一个 \((a_i,x)\) 表示 \(x\) 个 \(a_i\)，再插入一个 \(n\)，复杂度均摊 \(O(n)\)。注意实现细节。
点击查看代码
for(int i=1;i<=n;++i){
xx x=(xx){a[i],0};
sum-=q.front().val,q.front().cnt--;
if(!q.front().cnt) q.pop_front();
while(!q.empty()&&q.back().val>=a[i]){
sum-=q.back().val*q.back().cnt;
x.cnt+=q.back().cnt;
q.pop_back();
}
q.push_back(x);
q.push_back((xx){n,1});
sum+=x.val*x.cnt+n;
ans=max(ans,sum);
}