ABC262F
*2334
卡手的构造题，不是很难想，主要是细节比较多。
题意
给定一个排列 \(p\)。你可以最多执行 \(k\) 次操作。
- 删除一个数。
- 将 \(p\) 中末尾的数移到开头。
找出字典序最小的 \(p\)。
题解
显然我们需要贪心地把靠前的位置放上较小的数，考虑怎么把这些小数放到前面去。
不妨先考虑怎么最小化第一位。我们可以在 \(k\) 次操作内将其移到最终排列开头的位置有：
- 第 \(1\) 至第 \(k\) 位。只要删掉前面的所有数就好。注意整个过程中不能也没必要执行任何移动操作。
- 第 \(n-k+1\) 至第 \(n\) 位。后面的数可以选择移到开头，也可以选择直接删掉，但是在处理完目标位置之后就不能再执行移动操作了。
容易发现，这两类位置是“互斥”的。即，你只能从中选择一种方式构造第一位。显然，我们会选择最小的那一位。
但是由于可能出现 \(\frac{n}{2} \le k\) 的情况，即两个位置集合有交集，导致同一个位置可能有两个构造方式，故需要对两种情况分类讨论。
先来看第一种情况。
由于没有移动，所以等价于直接在原排列上删除 \(k\) 个数然后最小化字典序，直接用单调队列推一次就好了。
具体就是维护一个单调队列，但是全程只能弹出 \(k\) 次，再多就不弹了。由于字典序的性质可以证明这样做的正确性是对的。注意如果最后维护完发现弹出次数还有剩余，即只删除了小于 \(k\) 个数，那么就需要接着从末尾弹直到把次数用完。
原因是字典序中，原串前缀的字典序小于原串。
这样得到的单调队列即为第一种情况下的答案。
再看第二种情况。
我们一定会从第 \(n-k+1\) 至第 \(n\) 位中选择最小的那一位，设该位为 \(p\)。
然后可以发现第 \(p+1\) 位至第 \(n\) 位都是需要操作的，要么被删除要么被移走，不然我们没办法将 \(p\) 移动到开头。
既然怎样都是要操作的，操作次数省不掉，那么我们在找到 \(p\) 之后直接对 \(p\) 至 \(n\) 维护一个标准的单调队列就可以了。单调队列中的元素将被保留至答案中的开头，所以这样可以最小化答案的前面部分。但是这一段中的末尾元素有可能会被后面接上的第 \(1\) 至第 \(p-1\) 位干掉，这个接下来再做。
对于第 \(1\) 至第 \(p-1\) 位，我们还剩下 \(k-(n-p+1)\) 次操作。我们要最小化这个部分的字典序——那么就转化为了第一种情况，做一遍只能弹出 \(k-(n-p+1)\) 次的单调队列即可。对于这部分的末尾同第一部分处理，也是有多余操作就弹到用完为止。
然后我们发现这样的单调队列的第一位是有可能比前面 \(p\) 至 \(n\) 位得到的单调队列的末尾更优的，所以要检查一下，如果更优那么第 \(p\) 至 \(n\) 位得到的单调队列就需要弹出末尾元素。
最后把 \(p\) 至 \(n\) 位得到的单调队列和 \(1\) 至 \(p-1\) 位的单调队列拼起来就是这种情况下的答案。
最后，比较两种情况下答案的字典序，选择更优的打印即可。
时间复杂度 \(O(n)\) 。
代码
相对简单，但是有不少细节。
const ll maxn=2e5+5;
ll n,k,a[maxn];
ll q[maxn],tp;
ll b[maxn],hd;
vector<ll>ans1;
vector<ll>ans2;
void solve(){
n=R,k=R;
for(ll i=1;i<=n;i++){
a[i]=R;
}
// 第一种情况
for(ll i=1,cnt=0;i<=n;i++){
while(tp&&a[i]<a[q[tp]]&&cnt<k)tp--,cnt++;//最多弹出k次
q[++tp]=i;
if(i==n){
while(tp&&cnt<k)cnt++,tp--;//注意在最后一位的剩余操作
}
}
for(ll i=1;i<=tp;i++)ans1.push_back(a[q[i]]);//记录答案
// 第二种情况
tp=0;
a[n+1]=1ll<<60;
ll p=n+1;
//找到 p
for(ll i=n;i>n-k;i--){
if(a[i]<a[p])p=i;
}
//单调队列，弹出次数不会超过k次
for(ll i=p;i<=n;i++){
while(tp&&a[i]<a[q[tp]])tp--;
q[++tp]=i;
}
k-=(n-p+1);//减去已经消耗的次数
for(ll i=1;i<p;i++){
while(hd&&k&&a[b[hd]]>a[i])hd--,k--;
b[++hd]=i;//第 1 至 p-1 位的单调队列
}
while(k)hd--,k--;//如果操作次数还有剩余，同第一种情况
while(hd&&tp&&a[q[tp]]>a[b[1]])tp--;//如果更优
for(ll i=1;i<=tp;i++)ans2.push_back(a[q[i]]);
for(ll i=1;i<=hd;i++)ans2.push_back(a[b[i]]);//记录答案
if(ans1<ans2)for(auto it:ans1)wk(it);
else for(auto it:ans2)wk(it);//选择更优的打印
return ;
}