526互联

CF1917D Yet Another Inversions Problem 题解

发布时间 2024-01-07 19:45:57作者: SunsetLake

官方题解。

思路

首先可以把 \(a\) 数组分成 \(n\) 块，每块都是长为 \(k\) 的 \(q\) 数组。于是我们可以把答案拆成两部分计算：块内的贡献和块外的贡献。对于块内，\(p_i\) 都是一样的，因此可以直接消去，计算的实际上就是 \(q\) 序列的逆序对数，把这个值 \(\times n\) 就行了。这样就只需要计算块与块之间的答案。我们先固定 \(p\) 的两个元素 \(x\) 和 \(y\)，那么要计算的逆序对就是形如 \(a_i=x\times 2^a\)，\(a_j=y\times 2^b\) 的 \((i,j)\)。因为每个块内都是一个 \(1 \sim k-1\) 的排列，因此把 \(x\) 和 \(y\) 两个块拉出来他们对应项的次幂都是相同的。也就是：\([x, 2x, 4x, \ldots, 2^kx]\) 和 \([y, 2y, 4y, \ldots, 2^ky]\)。这时再考虑合并两个序列（排序）并且计算贡献。这里讨论 \(x<y\) 的情况（\(x>y\) 同理）。

  • 如果 \([\color{blue}{x}\) \(<\color{red}{y}\) \(<\) $ \color{blue}{2x}]\(，那么序列就会长成这样：\)[\color{blue}{x}, \color{red}{y}, \color{blue}{2x}, \color{red}{2y}, \color{blue}{4x}, \color{red}{4y}, \ldots, \color{blue}{2^kx}, \color{red}{2^ky}]$。
  • 如果 \([\color{blue}{2x}\) \(<\color{red}{y}\) \(<\) $ \color{blue}{4x}]\(，那么：\)[\color{blue}{x}, \color{blue}{2x}, \color{red}{y}, \color{blue}{4x}, \color{red}{2y}, \color{blue}{8x}, \color{red}{4y}, \ldots, \color{blue}{2^{k-1}x}, \color{red}{2^{k-2}y}, \color{blue}{2^kx}, \color{red}{2^{k-1}y}, \color{red}{2^ky}]$。
  • 如果 \([\color{blue}{4x}\) \(<\color{red}{y}\) \(<\) $ \color{blue}{8x}]\(，那么：\)[\color{blue}{x}, \color{blue}{2x}, \color{blue}{4x}, \color{red}{y}, \color{blue}{8x}, \color{red}{2y}, \color{blue}{16x}, \color{red}{4y}, \ldots, \color{blue}{2^{k-1}x}, \color{red}{2^{k-3}y}, \color{blue}{2^kx}, \color{red}{2^{k-2}y}, \color{red}{2^{k-1}y}, \color{red}{2^ky}]$。
  • \(\cdots\)

假如 \(x\) 在 \(p\) 中在 \(y\) 的后面，那就应该用 \(y\) 的视角去统计逆序对数，即对于每个红色的项去看它前面有多少个蓝色的项。这样就满足了逆序对顺序的要求，并且不会计算块内的贡献，只会考虑块间的答案，自然不会算重了。如何计算？观察一下规律：如果 \(2^{num-1}x < y < 2^{num}x\)，那么每个红色的 \(y\) 的贡献就是 \(num+(num+1)+(num+2)+\dots +k-1+\underbrace{k+k+\dots +k}_{num \text{个}}\)。这是一个 \(num \sim k-1\) 的等差数列再加上 \(num \times k\)。若 \(x\) 在 \(p\) 中在 \(y\) 的前面，那就该用 \(x\) 的眼光去计数了。通过观察可得，其贡献为 \(\underbrace{0+0+\dots +0}_{num \text{个}} +1+2+\dots +k-num\)。这是 \(1 \sim k-num\) 的等差数列。有了这些结论，就可以 \(O(n^2\log n)\) 算答案了。但是这需要枚举每个块，考虑如何优化这个过程。我们可以直接去枚举 \(x\) 的取值，可以发现对于 \(x\) 产生贡献的 \(y\) 都是成倍增长的，\(y,2y,4y,\dots ,2^ty\)，也就是只会有 \(\log\) 级个数！因此我们可以枚举这些 \(y\) （在 \(p\) 中在 \(x\) 的后面），用树状数组统计他的出现次数，再用上面的结论计算贡献即可。

code

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int t;
const int N=2e5+5,mod=998244353;
int n,p[N],q[N],mx;
ll k,c[N<<1],ans;
int lowbit(int x){
	return x&-x;
}
void clr(){
	for(int i=1;i<=mx;i++)c[i]=0;
}
void add(int id,ll d){
	for(int i=id;i<=mx;i+=lowbit(i))c[i]+=d;
}
ll query(int id){
	ll res=0;
	id=min(id,mx);
	for(int i=id;i;i-=lowbit(i))res+=c[i];
	return res;
}
void solve(){
	cin>>n>>k;
	mx=max(2*n-1,(int)k);
	for(int i=1;i<=n;++i)scanf("%d",&p[i]);
	for(int i=1;i<=k;++i)scanf("%d",&q[i]),q[i]++;//q[i]可能为0，所以统一加1
	clr();
	ans=0;
	for(int i=1;i<=k;++i)add(q[i],1),ans=(ans+i-query(q[i]))%mod;//块内逆序对
	ans=(ans*n)%mod;
	clr();
	for(int i=1;i<=n;++i)add(p[i],1);
	for(int i=1;i<=n;++i){
		int x=p[i];
		ll num=1;
		while(x<2*n){//x<y的情况
			int y=x*2;
			ll cnt=query(y)-query(x);//树状数组计数
			ll len=max(0ll,k-num);
			ans=(ans+(len+1)*len/2%mod*cnt%mod)%mod;
			x*=2;
			num++;
		}
		x=p[i];num=1;
		while(x>1){
			int y=(x+1)/2;//x是奇数
			ll cnt=query(x-1)-query(y-1);
			ll mn=min(num,k);
			ans=(ans+cnt*((k-1+mn)*(k-mn)/2%mod+mn*k%mod)%mod)%mod;
			num++;
			x=y;
		}
		add(p[i],-1);//只计算每个x后面的数的贡献
	}
	cout<<ans<<endl;
} 
int main(){
	cin>>t;
	while(t--)solve();
	return 0;
}