Codeforces #917 : Div2 D. Yet Another Inversions Problem

Div2とはいえ余り出来の良くなかった回。
https://codeforces.com/contest/1917/problem/D

問題

1～(2N-1)のN個の奇数からなる整数列Pと、0～(K-1)のPermutation Qが与えられる。
ここから、以下のNK要素の数列Aを考える。
A[i*k+j]=P[i]*2^Q[j]

この数列の転倒数を求めよ。

解法

P[i]とP[j]は高々N倍しか差がないので、Q[j]の部分の差がO(log(N))以上ある場合は、P[i]とP[j]の差が何であれ、Qの部分の違いによって転倒数になるかどうか決まる。

Pの各要素に対し、手前の他のPの要素から定まるのAの値に対し、Qの値が-log(N)～log(N)の差があるとき、それぞれ転倒数を求めて行こう。

int T,N,K;
int P[202020];
int Q[202020];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> Ps[19],Qs;
const ll mo=998244353;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		
		ll ret=0;
		FOR(i,N) cin>>P[i];
		FOR(i,K) {
			cin>>Q[i];
			// 同一P内
			(ret+=1LL*N*(Qs(K)-Qs(Q[i])))%=mo;
			Qs.add(Q[i],1);
		}
		
		// Qが18以上の場合必ず勝つ
		if(K>=20) {
			ret+=1LL*N*(N-1)/2%mo*(1LL*(K-19)*(K-19+1)/2%mo)%mo;
			ret%=mo;
		}
		FOR(i,N) {
			for(j=-18;j<=18;j++) {
				ll pat=K-abs(j);
				if(pat<=0) continue;
				if(j>=0) {
					ll tar=min(2*N+1LL,(ll)P[i]<<j);
					(ret+=1LL*pat*(Ps[0](2*N+1LL)-Ps[0](tar)))%=mo;
				}
				else {
					(ret+=1LL*pat*(Ps[-j]((1<<19)-1)-Ps[-j](P[i])))%=mo;
				}
			}
			FOR(j,19) {
				ll a=min(((1LL<<19)-1),(ll)P[i]<<j);
				Ps[j].add(a,1);
			}
		}
		
		cout<<ret%mo<<endl;
		
		FOR(i,19) {
			for(j=1;j<=2*N-1;j+=2) {
				ll a=min(((1LL<<19)-1),(ll)j<<i);
				Ps[i].add(a,-1);
			}
		}
		FOR(i,K) Qs.add(i,-1);
		
	}
		
}

まとめ

面倒なだけで余り面白さはないかも…。