首先我们考察 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);
把几段代码融合一下，就得到了此题的代码。完整代码不给！