【题解】CF1852A Ntarsis' Set

ricky_lin / 2023-09-05 / 原文

考虑我们先手模一下样例：

\[\begin{cases} 1&3&5&6&7\\ 2&8&10&11&12\\ 4&13&15&16&17 \end{cases} \]

???一脸疑惑，有什么规律吗？真有，但是很难看出来捏。

正难则反，我们考虑如果知道操作一次后一个数的位置，我们可以很容易推出，操作之前它的位置：

\[\begin{cases} 1&2&3&4&5&6&\cdots\\ 2&4&8&9&10&11&\cdots\\ 4&9&13&14&15&16&\cdots\\ \end{cases} \]

你考虑如果最后的答案比较小的话还可以用一个数组存下每次操作前的位置。

但是，显然最后的答案很大，我们必须找到规律。

我们假设在操作后的序列中是第 $i$ 个，操作前是第 $j$ 个，那么一定满足 $\forall k\leq j-i,a_k \leq j$ 在这个情况下每次让 $j$ 最大即可，具体方法可以看 e.g / code。

e.g.

以第二个测试点为例:

最后一次操作时，操作数组为 $[1, 3, 5, 6, 7]$，$ans$ 的位置为 $1$。遍历操作数组，操作数组中第一个元素 $1 = 1$，所以将 $ans$ 的位置向后移动，变为 $2$。继续遍历，发现操作数组中第二个元素 $3 > 2$，已经不能继续将 $ans$ 往后移动，那么第二次操作后在第 $1$ 个位置的数，第二次操作前在第 $2$ 个位置

倒推倒数第二次操作时，$ans$ 的位置为 $2$。遍历操作数组，操作数组中第一个元素为 $1 < 2$，将 $ans$ 位置后移至 $3$。继续遍历，操作数组中第二个元素为 $3 = 3$，将 $ans$ 位置后移至 $4$。继续遍历，操作数组中第三个元素为 $5 > 4$，那么第一次操作后在第 $2$ 个位置的数，操作前在第 $4$ 个位置

倒推倒数第三次操作的方法相同，最后 $ans$ 的位置变为 $9$，即为答案。

具体可以看code（代码中二分没有必要）：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN = 2e5 + 8;
int T;
int n,k;
ll lft;
int a[NN];
ll erf(ll x){
	ll l = lft,r = n,ans = lft;
	while(l <= r){
		int mid = (l + r) / 2;
		if(a[mid] <= x) ans = mid,l = mid + 1;
		else r = mid - 1;
	}
	return ans;
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&k);
		for(int i = 1; i <= n; ++i) scanf("%d",&a[i]);
		ll now = 1,get = 0,pre = 0;
		lft = 0;
		for(int i = 1; i <= k; ++i){
			get = pre = 0;
			while(pre != (get = erf(now + get))) pre = get,lft = max(lft,get);
			now += pre;
		}
		printf("%lld\n",now);
	}
}