专栏文章

题解：P12391 「RiOI-6」帝国少女

CCybher
P12391题解参与者 4已保存评论 4

文章操作

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

当前评论
4 条
当前快照
1 份
快照标识符
@mipfr733
此快照首次捕获于
2025/12/03 11:16
3 个月前
此快照最后确认于
2025/12/03 11:16
3 个月前
查看原文

P12391 「RiOI-6」帝国少女 题解

思路产生

首先显然 m>2m>2 和 m=2m=2 是两种情况需要分讨。

我们先考虑 m>2m>2 的情况：

有一个贪心策略就是对于任意一段相同的数的连续段，都把在这个连续段中的偶数位的数变成一个不同于其左右相邻的数。
比如 2 1 1 1 1 1 1 2 就要变成 2 1 2 1 2 1 3 2。
这个贪心策略的正确性是显然的，因为对于任意一对相邻且相同的数，都要选择一个选择其中一个，给成另一个数字，因为我们的可以选择换成的数字至少有 33 个，一定可以做到改完后和左右相邻的数各不相同。我们只需要考虑怎么做可以让相邻的数对尽可能少。对于奇数长度的段我们都改变偶数位的数一定更优的，而对于偶数长度的段我们改变偶数位的数一定是不劣的。
有了贪心策略，我们就要想怎么才能在时间复杂度限制内求出答案。
我们考虑每一个数对会对多少个子段产生贡献。我们求出来每一个子段的左端点的有多少种取法，右端点有多少种取法，这样根据乘法原理，我们就能求出来能让点对做出贡献的子段数。
对于右端点，只要大于等于点对的右端点是都能取的。
对于左端点，在小于点对左端点的同时，还要满足让点对的右端点成为一段连续相同的数的连续段的偶数位。
这些都是可求的，根据连续段长度奇偶分讨一下就好了。

我们接下来考虑 m=2m=2 的情况

m=2m=2 和 m>2m>2 的情况有一个显著的不同就是：可以选择换成的数字只有了两种选择，这样就会导致我们贪心策略出现问题，因为你无法保证只把连续段的偶数换成另一个数就能保证合法。
比如按照原来的贪心策略：2 1 1 1 1 1 1 2 就要变成 2 1 2 1 2 1 2 2 然后你就发现假了。
这该怎么办？
考虑把所有的 22 都替换成 00，这样对于一个子区间，我们都要转换成 0101010…0101010 \dots 或者 1010101…1010101\dots
感觉 0101 交替有点抽象。我们直接把原序列上的所有偶数位的数全部都 0101 反转，这样我们就只需要求把一段区间变成全 11 或者全 00 就好了。
这样我们又有了一个贪心策略：对于一个子区间，11 的个数多就把区间所有 00 变成 11， 00 的个数多就把区间所有 11 变成 00。
那么我们就把题转化成了求：
∑i=1n∑j=ing⁡(i,j)\sum\limits_{i=1}^{n}\sum\limits_{j=i}^{n}\operatorname{g}(i,j)
这里 g⁡(i,j)\operatorname{g}(i,j) 表示对于从 ii 到 jj 的子区间，00 的个数和 11 的个数较小值。
我们前缀和分别维护出区间 00 和 11 的个数，然后枚举区间，这样 O(n2)O(n^2) 的做法就做好了，拿到 6060 分。
考虑优化。设子区间有 aa 个 00 和 bb 个 11，那么有： min⁡(a,b)=a+b−∣a−b∣2\min(a,b)=\dfrac{a+b-|a-b|}2 而我们要求的所有子区间最小值之和可转化为： (∑(a+b)−∑∣a+b∣)2\dfrac{(\sum (a+b) - \sum |a+b|)}2
其中 ∑(a+b)\sum (a+b) 代表的是所有子区间长度之和，∑(a+b)\sum (a+b) 代表的是所有子区间 00 和 11 数量差的绝对值之和。
对于前者我们发现长度为 11 的区间有 nn 个，长度为 22 的区间有 n−1n-1 个，长度为 33 的区间有 n−2n-2 个，以此类推……
那么前者其实就是：
=∑i=1nn×i−∑i=1ni2+∑i=1ni=n(n+1)22−n(n+1)(2n+1)6+n(n+1)2=n(n+1)(n+2)2=\sum\limits_{i=1}^nn\times i-\sum\limits_{i=1}^ni^2+\sum\limits_{i=1}^n i\\ =\frac{n(n+1)^2}2-\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}\\ =\frac{n(n+1)(n+2)}{2}
那么下面就是求后者了。
我们再进行进一步的转化：
将 00 视作 −1-1，则子区间的 11 和 00 的个数差就等于该区间的和。我们再做一下前缀和。设前缀和数组为 ss 问题就又转换成了对于所有的 i<ji<j 的 ∣s[j]−s[i]∣|s[j]-s[i]| 的和。
我们考虑拆绝对值。
对于每个s[j]s[j]，贡献值为： ∑i<j∣s[j]−s[i]∣\sum_{i<j}|s[j]-s[i]|
拆分为两部分：
  • s[j]>s[i]s[j] > s[i]：贡献为 s[j]−s[i]s[j] - s[i]，总贡献为 s[j]×s[j]\times 较小元素的个数 −- 较小元素的和。
  • s[j]≤s[i]s[j] \le s[i]：贡献为 s[i]−s[j]s[i] - s[j]，总贡献为较大元素的和 −s[j]×-s[j]\times 较大元素的个数。
我们可以开两个权值树状数组分别记录次数和总和，由于前缀和数组可能有负数，所以不要忘了离散化一下。
然后在枚举 jj 的同时，快速求出所有上文所提到的较小元素的个数，较大元素个数，较小元素的和，较大元素的和。然后每求出一个 jj 的贡献再把 jj 加到权值树状数组里面。
最后根据公式求一下就好了，最后时间复杂度是O(nlog⁡n)O(n\log n)。
附上代码。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int a[N],s[N],b[N];
int lowbit(int x){
	return x&(-x);
}
struct Tree{
	int n;
	vector<int> tr;
	Tree(int n):n(n),tr(n+2){}
	void update(int x,int c){
		for (;x<=n;x+=lowbit(x)) tr[x]+=c;
	}
	int query(int x){
		int res=0;
		for (;x;x-=lowbit(x)) res+=tr[x];
		return res;
	}
};
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	if(m>2){
		int ans=0;
		int nw=0,len=0;
		for(int i=1;i<n;i++){
			if(a[i]==nw){
				len++;
			}else{
				nw=a[i];
				len=1;
			}
			if(a[i]==a[i+1]){
				if(len%2==0){
					ans+=(len/2)*(n-i);
				}else{
					ans+=(len/2+(i-len)+1)*(n-i);
				}
			}			
		}
		cout<<ans<<"\n";
	}else{
		for(int i=1;i<=n;i++){
			if(a[i]==2)a[i]=0;
		}
		for(int i=2;i<=n;i+=2){
			a[i]^=1;
		}
		for (int i=1;i<=n;i++) a[i]=(a[i]==0?1:-1);
		for(int i=1;i<=n;i++){
			s[i]=a[i]+s[i-1];
			b[i]=s[i];
		}
		sort(b+1,b+n+1);
		int tot=unique(b+1,b+n+1)-b-1;
		Tree cnt(tot),sum(tot);
		int ans=0;
		for (int i=0;i<=n;i++){
			int x=s[i];
			int k=lower_bound(b+1,b+tot+1,x)-b;
			int cl=cnt.query(k-1),sl=sum.query(k-1);
			int ct=cnt.query(tot),st=sum.query(tot);
			int cs=ct-cl,ss=st-sl;
			ans+=x*cl-sl+ss-x*cs;
			cnt.update(k,1);
			sum.update(k,x);
		}
		cout<<(n*(n+1)*(n+2)/6-ans)/2;
	}
}

评论

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

正在加载评论...