专栏文章

题解：P13754 【MX-X17-T3】Distraction

GGarry_HJR
P13754题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mio9zpzv
此快照首次捕获于
2025/12/02 15:47
3 个月前
此快照最后确认于
2025/12/02 15:47
3 个月前
查看原文

题目描述

给定一个 1∼n1\sim n 的排列 p1,p2,…,pnp_1,p_2,\ldots,p_n。定义位置 ii 的权值 viv_i 为 (∑j=1i−1[pj>pi]+∑j=i+1n[pi>pj]) mod 2(\sum_{j=1}^{i-1}[p_j>p_i]+\sum_{j=i+1}^n [p_i>p_j])\bmod 2，其中 [pj>pi][p_j>p_i] 的值为若 pj>pip_j>p_i 则为 11 否则为 00。排列的权值是 ∑i=1nvi\sum_{i=1}^n v_i。
为了使排列的权值最大，现在可以最多执行一次操作，操作是把一个数从排列中拿出来，再把它插入排列中任意一个位置，过程中要保持剩下数的相对顺序不变。
求可以得到的最大的排列权值。
2≤n,∑n≤5×1062 \le n,\sum n\le 5\times 10^6。

思路分析

寻找入手点

古人云：“打蛇打七寸。”
首先我们思考一下题目中给定的式子 (∑j=1i−1[pj>pi]+∑j=i+1n[pi>pj]) mod 2(\sum_{j=1}^{i-1}[p_j>p_i]+\sum_{j=i+1}^n [p_i>p_j])\bmod 2 是什么意思。
发现对于 j<ij<i 的部分要求 pj>pip_j>p_i，而 i>ji>j 的部分要求 pi>pjp_i>p_j，也就是对于 pip_i 来说逆序对的个数。
然后，总的贡献就是每一项的逆序对个数与 22 取模后相加。
那么我们得首先知道怎么求出每一项的贡献。

初步尝试

看到贡献和逆序对有关，数据又比较大，立刻想到逆序对的快速求法。
常见方法有归并排序和树状数组两种，如果不清楚，可以移步这里，（但本题实际上不需要）。
现在我们知道个数了，自然能统计出原始排列的贡献。
但是我们还要考虑怎么移动这个问题，如果直接去枚举起终点，然后重新计算的话，复杂度将会达到 Θ(n3log⁡n)\varTheta(n^3\log n)，直接炸飞到远在光年之外的深渊。

反思与重推

所以，我们看到这样的题目，不要一开始就去想怎么往板子上去套，否则往往会得到一堆“治标不治本”的做法。
我们考虑把这个个数清晰地表示出来：令左边比 pip_i 大的有 xx 个，那么左边比它小的就有 (i−1−x)(i-1-x) 个。
同时由于这是个排列，比 pip_i 小的数一共有 (pi−1)(p_i-1) 个，那么左边有 (i−1−x)(i-1-x) 个了，右边自然就有 (pi−1)−(i−1−x)(p_i-1)-(i-1-x) 个。
整理一下，左边的逆序对个数（比 pip_i 大的数的个数）就是 xx，右边的逆序对个数（比 pip_i 小的数的个数）就是 pi−i+xp_i-i+x。
一个位置的逆序对总个数就是 pi−i+x+x=pi−i+2xp_i-i+x+x=p_i-i+2x。
那么贡献是个数对 22 取模后的结果，不难看出 2x2x 是偶数，对 22 取模就是 00。
也就是说我们一开始知道左右边多少个是没用的，此时贡献是 (pi−i) mod 2(p_i-i)\bmod 2，和 xx 完全无关。
那么原始排列的贡献就是 ∑i=1n(pi−i) mod 2\sum_{i=1}^n (p_i-i)\bmod 2，现在考虑移动。

进一步探索

发现还是很难一步知道正确复杂度的做法，那么我们循序渐进，先考虑较高时间复杂度的方法，再考虑如何优化。
枚举起终点是我们能够想到的最朴素的方法，初遇本题时，我们粗暴地求逆序对，结果就因为每次需要重新计算贡献栽在了这里。
但是现在我们不一样了，我们有了一个和左右逆序对个数完全无关的计算公式 (pi−i) mod 2(p_i-i)\bmod 2。
因此，我们可以假设把 plp_l 移动到了 rr，记作 [l,r][l,r]。
则对于 [1,l−1][1,l-1] 和 [r+1,n][r+1,n] 的贡献还是不变的，因此有 (∑i=1l−1(pi−i) mod 2)+(∑i=r+1n(pi−i) mod 2)(\sum_{i=1}^{l-1}(p_i-i)\bmod 2)+(\sum_{i=r+1}^n (p_i-i)\bmod 2)。
那么我们考虑涉及到 [l,r][l,r] 的贡献，对于 i∈[l+1,r]i\in [l+1,r] 的 pip_i，它们都向前移了一格，即 (pi−i)→(pi−(i−1))(p_i-i)\to (p_i-(i-1))，在模 22 的意义下，就是结果改变了，00 变成了 11，11 变成了 00，即 (∑i=l+1r(pi−i+1) mod 2)(\sum_{i=l+1}^r (p_i-i+1)\bmod 2)。
最后就是 i=li=l，这个需要特别判断了，贡献就是 (pl−r) mod 2(p_l-r)\bmod 2。

阶段性分析

我们现在又会了如何求出贡献，分析一下，枚举的话是 Θ(n2)\varTheta(n^2)，然后单步检验是 Θ(n)\varTheta(n) 的，总复杂度变成了 Θ(n3)\varTheta(n^3)，比上一把的 Θ(n3log⁡n)\varTheta(n^3\log n) 好了一些，但相对于 10610^6 而言，依然堕入于最深邃的谷底。
现在我们要考虑怎么优化了。

深入优化

我们知道，整个的排列 pp 自始至终就放在那里，没有说给定 qq 个操作然后修改这种的字眼，因此我们没有必要一遍一遍地去单步检验。
看到这是区间贡献，我们可以利用“未雨绸缪”的思想进行预处理，也就是求出前缀和，这样把单步检验的复杂度变成 Θ(1)\varTheta(1)。
令 pre1i=(∑j=1i(pi−i) mod 2)pre1_{i}=(\sum_{j=1}^i (p_i-i)\bmod 2)，则 pre0i=i−pre1ipre0_i=i-pre1_i。
这样我们就是要求
max⁡l=1n−1max⁡r=l+1n(∑i=1l−1(pi−i) mod 2)+((pl−r) mod 2)+(∑i=l+1r(pi−i+1) mod 2)+(∑i=r+1n(pi−i) mod 2)\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=1n−1max⁡r=l+1n(pre1l−1+pre1n−pre1r+pre0r−pre0l+(pl−r) mod 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)
复杂度降到了 Θ(n2)\varTheta(n^2)，但是还是不行。
观察我们要求的，pre1npre1_n 和 l,rl,r 完全无关，−pre1r,pre0r-pre1_r,pre0_r 都只和 rr 有关，我们可以把它们提出去并交换两个和式。
max⁡r=2n(pre0r−pre1r)+max⁡l=1r−1(pre1l−1−pre0l+(pl−r) mod 2)\max_{r=2}^{n}(pre0_r-pre1_r)+\max_{l=1}^{r-1}(pre1_{l-1}-pre0_l+(p_l-r)\bmod 2)
这里面，pre1l−1,−pre0lpre1_{l-1},-pre0_l 都只和 ll 有关，可以一边扫描一边维护前缀 max⁡\max。
最难的是这个 (pl−r) mod 2(p_l-r)\bmod 2，它非常的讨厌，与 l,rl,r 都有关。
但是，由于它是 (pl−r) mod 2(p_l-r)\bmod 2 后的结果，只有 00 和 11 这两种情况，具体还和 pl,rp_l,r 的奇偶性有关：当 pl,rp_l,r 奇偶性一致时，无任何贡献，而奇偶性不一致时，有 11 的贡献。
这里 rr 的奇偶性我们是知道的，因此只要分别维护 plp_l 是奇数和偶数的前缀 max⁡\max 即可。
我们的复杂度现在就降成了 Θ(n)\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. 从“简单”逐步去走向“复杂”。要想跑首先得会走。这个阶段的题目，正解不是我们一眼就能望穿的，往往需要从朴素的暴力开始，一步一步地尝试和优化来得出。不能“一口吃个胖子”。
    这个题目，我们从枚举起终点开始，从单步转移 Θ(n)\varTheta(n) 到未雨绸缪预处理 Θ(1)\varTheta(1)，从枚举两个端点的 Θ(n2)\varTheta(n^2) 到发现贡献值的相关性分奇偶讨论降到 Θ(n)\varTheta(n)，每一步都凝结着我们一点点思考，一点点深入的成果。
完结撒花啦！希望帮助到大家！如果有笔误欢迎下方留言！

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...