自动搬运

查看原文

来自洛谷，原作者为

	Piggy343288 Where is my right path to go on.

搬运于2025-08-24 22:48:22，当前版本为作者最后更新于2023-06-23 11:18:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先我们考察 LIS 长度为 $n-1$ 的数列的性质。可以发现，这必定是 $1,2,3,\cdots,n$ 中拎出一个不听话的元素甩到其他地方去，剩下的元素依次补齐所构成的。这意味着，最多只有一个元素满足 $a_i-i\ge2$，更具体的，不考虑只对邻项交换的排列（即形如 $1,2,3,\cdots,i,i-1,\cdots,n$），每个满足要求的排列都有且仅有一个元素满足 $a_i-i\ge 2$。

接下来对所有钦定了值的元素进行考察。这意味着下文中我们已经默认了 $a_i\not=-1$。

• 所有 $a_i=i$。那么我们只能对下标的空隙部分做操作。也就是假设相邻的两个下标分别为 $i,j$，那么这一段对答案的贡献是 $(j-i-2)^2$。不难写出如下的代码：

int cur = 0;
for(int i = 1; i <= n; i++){
	if(!~a[i]) cur++;
	else if(cur){
		ans += pow(cur - 1, 2);
		cur = 0;
	}
}
if(cur) ans += pow(cur - 1, 2);

• 存在 $|a_i-i|\ge 2$。因为这样的 $i$ 只能有一个，所以如果找到多个这样的下标直接 cout<<0<<"\n" 走人。即使仅有一个这样的 $i$，合法的也最多只能有一个排列。因此判断一下是否合法即可。不难写出下面的代码：

int p = -1;
for(int i = 1; i <= n; i++){
	if(!~a[i]) continue;
	if(abs(a[i] - i) >= 2){
		if(~p) return false;
		else p = i;
	}
}
if(~p){
	//found one abs(a[i] - i) >= 2
	if(a[p] > p){
		int l = p, r = a[p];
		for(int i = 1; i <= n; i++){
			if(!~a[i]) continue;
			if((i < l || i > r) && a[i] != i) return false;
			if((i > l && i <= r) && a[i] != i - 1) return false;
		}			
	}else{
		// just a reversion of a[p] > p...
		int l = a[p], r = p;
		for(int i = 1; i <= n; i++){
			if(!~a[i]) continue;
			if((i < l || i > r) && a[i] != i) return false;
			if((i >= l && i < r) && a[i] != i + 1) return false;
		}
	}
}

• 存在 $a_i=i+1,a_{i+1}=i$。这种比较好判断，而且也最多只能存在一个这样的 $i$。

int cnt = 0;
for(int i = 1; i <= n; i++){
	if(a[i] != i && ~a[i]){
		if(a[i] == i + 1 && a[i + 1] == i) i++, cnt++;
		else return false;				
	}
}
if(!cnt) return false;

在写代码的时候，我把上述两个情况合并在一起了。因为它和下面的情况相差较大，但这两个本质是一个情况，即指定了开头所提到的“不听话的元素”。

• 存在一段 $a_i=i+1$ 或一段 $a_i=i-1$。注意判断仅能存在一个这样的段！因此我们不难写出下面的代码，其中 $flag$ 标志了目前在什么阶段（进入段前，段中，第一段后）。

int flag = 0;
p = 0;
for(int i = 1; i <= n; i++){
	if(!~a[i]) continue;
	if(a[i] == i){
		if(flag == 1) flag = 2;// signal if i is out of the offset area.
	}else{
		// a[i] != i
		r = i;
		if(flag == 0){
			//no offset currently
			p = a[i] - i;
			l = i, flag = 1;// into the offset area;
		}else{
			if(flag == 1){
				if(a[i] - i != p) return false;
			}else{
				assert(flag == 2); return false;// out of the offset area and found another section,
				// which is impossible to generate any valid solution in this occasion.
			}
		}
	}
}
return true;

int lcnt = 0, rcnt = 0;
for(int i = l - 1; i && !~a[i]; i--) lcnt++;
for(int i = r + 1; i <= n && !~a[i]; i++) rcnt++;
ans = 1ll * lcnt * rcnt;
ans += (~p ? rcnt : lcnt);

把几段代码融合一下，就得到了此题的代码。完整代码不给！