与 \(k\) 无关的 \(\Theta(n)\) 做法。
首先 \(10^{1000}\) 足够大，不妨把初始集合视为 \(\N_+\)。
模拟赛出了这个的强化版，\(k\le 10^9\)，我们考虑怎么解决这个问题。首先观察到如果 \(a_1\neq 1\) 答案一定为 \(1\)。不妨逆推，我们发现顺着推很简单，如果经过若干轮都没有被淘汰，每一轮每个数 \(x\) 的 \(pos_x\) 就会经过如下转移：\(pos_x\leftarrow pos_x -i\)，其中 \(a_i\) 为最后一个 \(<pos_x\) 的数。
相应地，逆推只需要 \(pos_x\leftarrow pos_x+i\)，其中 \(a_i\) 为最后一个 \(<pos_x +i\) 的数，即 \(a_{i+1}\geq pos_x + i\)。显然递推过程中找到的 \(i\) 是单调不降的（理解：相当于每次抽出没被删掉的放在前面，只需找到每次被放在前面的推导出抽出时的位置，显然这是唯一且递增的），但是可能会有多个相同且冗余的 \(i\)，每次都对 \(pos_x\) 执行 \(+i\) 的操作。
考虑加速这一过程。让 \(pos_x\) 直接加到边界 \(a_{i+1}-1\) 且不能做超过 \(k\) 步所需的步数为 \(p=\min(k,\lfloor\frac{a_{i+1}-1-pos_x}{i}\rfloor)\)，那么 \(pos_x\leftarrow pos_x+p\times i\) 即可，这样对于每个 \(i\) 都只会做 \(\Theta(1)\) 次。最后如果 \(pos_x>a_n\) 且 \(k\neq 0\)，\(pos_x\leftarrow pos_x + k\times n\) 就可以逆推出初始的 \(pos_x\) 值。
时间复杂度 \(\Theta(n)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+5;
int n,k,a[N];
int main(){int Tn;scanf("%d",&Tn);while(Tn--){scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)scanf("%d",&a[i]);if(a[1]!=1){printf("1\n");continue;}LL Pos=1;for(int i=1;i<n;i++)if(Pos<=a[i+1]-i){int p=min(k,(int)(a[i+1]-1-Pos)/i);Pos+=p*i;k-=p;}Pos+=1ll*k*n;printf("%lld\n",Pos);}return 0;
}