题解：P13754 【MX-X17-T3】Distraction
Garry_HJR
·
·
题解
题目描述
给定一个 1\sim n 的排列 p_1,p_2,\ldots,p_n。定义位置 i 的权值 v_i 为 (\sum_{j=1}^{i-1}[p_j>p_i]+\sum_{j=i+1}^n [p_i>p_j])\bmod 2，其中 [p_j>p_i] 的值为若 p_j>p_i 则为 1 否则为 0。排列的权值是 \sum_{i=1}^n v_i。
为了使排列的权值最大，现在可以最多执行一次操作，操作是把一个数从排列中拿出来，再把它插入排列中任意一个位置，过程中要保持剩下数的相对顺序不变。
求可以得到的最大的排列权值。
## 思路分析
### 寻找入手点
古人云：“打蛇打七寸。”
首先我们思考一下题目中给定的式子 $(\sum_{j=1}^{i-1}[p_j>p_i]+\sum_{j=i+1}^n [p_i>p_j])\bmod 2$ 是什么意思。
发现对于 $j<i$ 的部分要求 $p_j>p_i$，而 $i>j$ 的部分要求 $p_i>p_j$，也就是对于 $p_i$ 来说逆序对的个数。
然后，总的贡献就是每一项的逆序对个数与 $2$ 取模后相加。
那么我们得首先知道怎么求出每一项的贡献。
### 初步尝试
看到贡献和逆序对有关，数据又比较大，立刻想到逆序对的快速求法。
常见方法有归并排序和树状数组两种，如果不清楚，[可以移步这里，（但本题实际上不需要）](https://www.luogu.com.cn/problem/P1908)。
现在我们知道个数了，自然能统计出原始排列的贡献。
但是我们还要考虑**怎么移动**这个问题，如果直接去枚举起终点，然后重新计算的话，复杂度将会达到 $\varTheta(n^3\log n)$，直接炸飞到远在光年之外的深渊。
### 反思与重推
所以，我们看到这样的题目，不要一开始就去想怎么往板子上去套，否则往往会得到一堆“治标不治本”的做法。
我们考虑把这个个数清晰地表示出来：令左边比 $p_i$ 大的有 $x$ 个，那么左边比它小的就有 $(i-1-x)$ 个。
同时由于这是个排列，比 $p_i$ 小的数一共有 $(p_i-1)$ 个，那么左边有 $(i-1-x)$ 个了，右边自然就有 $(p_i-1)-(i-1-x)$ 个。
整理一下，左边的逆序对个数（比 $p_i$ 大的数的个数）就是 $x$，右边的逆序对个数（比 $p_i$ 小的数的个数）就是 $p_i-i+x$。
一个位置的逆序对总个数就是 $p_i-i+x+x=p_i-i+2x$。
那么贡献是个数对 $2$ 取模后的结果，不难看出 $2x$ 是偶数，对 $2$ 取模就是 $0$。
也就是说我们一开始知道左右边多少个是没用的，此时贡献是 $(p_i-i)\bmod 2$，和 $x$ 完全无关。
那么原始排列的贡献就是 $\sum_{i=1}^n (p_i-i)\bmod 2$，现在考虑移动。
### 进一步探索
发现还是很难一步知道正确复杂度的做法，那么我们循序渐进，先考虑较高时间复杂度的方法，再考虑如何优化。
枚举起终点是我们能够想到的最朴素的方法，初遇本题时，我们粗暴地求逆序对，结果就因为每次需要重新计算贡献栽在了这里。
但是现在我们不一样了，我们有了一个和左右逆序对个数完全无关的计算公式 $(p_i-i)\bmod 2$。
因此，我们可以假设把 $p_l$ 移动到了 $r$，记作 $[l,r]$。
则对于 $[1,l-1]$ 和 $[r+1,n]$ 的贡献还是不变的，因此有 $(\sum_{i=1}^{l-1}(p_i-i)\bmod 2)+(\sum_{i=r+1}^n (p_i-i)\bmod 2)$。
那么我们考虑涉及到 $[l,r]$ 的贡献，对于 $i\in [l+1,r]$ 的 $p_i$，它们都向前移了一格，即 $(p_i-i)\to (p_i-(i-1))$，在模 $2$ 的意义下，就是结果改变了，$0$ 变成了 $1$，$1$ 变成了 $0$，即 $(\sum_{i=l+1}^r (p_i-i+1)\bmod 2)$。
最后就是 $i=l$，这个需要特别判断了，贡献就是 $(p_l-r)\bmod 2$。
### 阶段性分析
我们现在又会了如何求出贡献，分析一下，枚举的话是 $\varTheta(n^2)$，然后单步检验是 $\varTheta(n)$ 的，总复杂度变成了 $\varTheta(n^3)$，比上一把的 $\varTheta(n^3\log n)$ 好了一些，但相对于 $10^6$ 而言，依然堕入于最深邃的谷底。
现在我们要考虑怎么优化了。
### 深入优化
我们知道，整个的排列 $p$ 自始至终就放在那里，没有说给定 $q$ 个操作然后修改这种的字眼，因此我们没有必要一遍一遍地去单步检验。
看到这是区间贡献，我们可以利用“未雨绸缪”的思想进行预处理，也就是求出前缀和，这样把单步检验的复杂度变成 $\varTheta(1)$。
令 $pre1_{i}=(\sum_{j=1}^i (p_i-i)\bmod 2)$，则 $pre0_i=i-pre1_i$。
这样我们就是要求
$$
\max_{l=1}^{n-1}\max_{r=l+1}^n (\sum_{i=1}^{l-1}(p_i-i)\bmod 2)+((p_l-r)\bmod 2)+(\sum_{i=l+1}^r(p_i-i+1) \bmod 2)+(\sum_{i=r+1}^n(p_i-i)\bmod 2)
$$
化为
$$
\max_{l=1}^{n-1}\max_{r=l+1}^n(pre1_{l-1}+pre1_n-pre1_r+pre0_r-pre0_l+(p_l-r)\bmod 2)
$$
复杂度降到了 $\varTheta(n^2)$，但是还是不行。
观察我们要求的，$pre1_n$ 和 $l,r$ 完全无关，$-pre1_r,pre0_r$ 都只和 $r$ 有关，我们可以把它们提出去并交换两个和式。
$$
\max_{r=2}^{n}(pre0_r-pre1_r)+\max_{l=1}^{r-1}(pre1_{l-1}-pre0_l+(p_l-r)\bmod 2)
$$
这里面，$pre1_{l-1},-pre0_l$ 都只和 $l$ 有关，可以一边扫描一边维护前缀 $\max$。
最难的是这个 $(p_l-r)\bmod 2$，它非常的讨厌，与 $l,r$ 都有关。
但是，由于它是 $(p_l-r)\bmod 2$ 后的结果，只有 $0$ 和 $1$ 这两种情况，具体还和 $p_l,r$ 的奇偶性有关：当 $p_l,r$ 奇偶性一致时，无任何贡献，而奇偶性不一致时，有 $1$ 的贡献。
这里 $r$ 的奇偶性我们是知道的，因此只要分别维护 $p_l$ 是奇数和偶数的前缀 $\max$ 即可。
我们的复杂度现在就降成了 $\varTheta(n)$，这一刻，我们终于抵达了成功的彼岸。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
inline long long _(){long long f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();} return f*x;}
inline void __(long long x,int opt){int top=0;char cnt[85];if(x<0)putchar('-'),x=-x;do{top++;cnt[top]=x%10+48;x/=10;}while(x);for(int i=top;i>=1;i--)putchar(cnt[i]);if(opt==1)putchar(' ');if(opt==2)putchar('\n');}
int t;
int n;
int a[5000005];
int pre[5000005][2];
int maxx[2];
int main() {
t=_();
while(t--){
n=_();
for(int i=1;i<=n;i++)a[i]=_();
for(int i=1;i<=n;i++){
pre[i][0]=pre[i-1][0]+((a[i]-i)%2==0);
pre[i][1]=pre[i-1][1]+((a[i]-i)%2!=0);
}
maxx[0]=-0x3f3f3f3f;maxx[1]=-0x3f3f3f3f;
int ans=pre[n][1];
for(int r=1;r<=n;r++){
if(r%2){
ans=max(ans,pre[n][1]+pre[r][0]-pre[r][1]+maxx[0]+1);
ans=max(ans,pre[n][1]+pre[r][0]-pre[r][1]+maxx[1]);
}
else{
ans=max(ans,pre[n][1]+pre[r][0]-pre[r][1]+maxx[0]);
ans=max(ans,pre[n][1]+pre[r][0]-pre[r][1]+maxx[1]+1);
}
if(a[r]%2)maxx[1]=max(maxx[1],pre[r-1][1]-pre[r][0]);
else maxx[0]=max(maxx[0],pre[r-1][1]-pre[r][0]);
}
cout<<ans<<endl;
}
return 0;
}
```
## 大总结
写了这么多，来总结一下。
这个题目从发现是逆序对，再到发现和逆序对无关，再到分析每一个部分的贡献，最后一步步优化时间复杂度，思维链可谓是一环扣一环。
最后，让我们站在宏观的“上帝视角”，走一遍这个题该走的路。
1. 将“未知”归属于“已知”。未知往往是我们所抵触的，当我们化未知为已知时，一种满足感和归属感会激励我们继续走下去。
对于这个题目存在的式子，我们可以把它解析出我们已知的“逆序对”。
2. 从“已知”中寻找出“未知”。知道这个东西已知后，我们一定不能去钻“思维定势”的死胡同，要善于从司空见惯的事物中推导，研究出新的事物，而不是一味地尝试自己曾经走过的路。
例如这个题目，我们最后可以推导出它与左右两个逆序对个数是无关的，然后我们才能考虑去如何交换位置。
3. 从“简单”逐步去走向“复杂”。要想跑首先得会走。这个阶段的题目，正解不是我们一眼就能望穿的，往往需要从朴素的暴力开始，一步一步地尝试和优化来得出。不能“一口吃个胖子”。
这个题目，我们从枚举起终点开始，从单步转移 $\varTheta(n)$ 到未雨绸缪预处理 $\varTheta(1)$，从枚举两个端点的 $\varTheta(n^2)$ 到发现贡献值的相关性分奇偶讨论降到 $\varTheta(n)$，每一步都凝结着我们一点点思考，一点点深入的成果。
完结撒花啦！希望帮助到大家！如果有笔误欢迎下方留言！