yukicoder : No.1270 Range Arrange Query

想定解じゃないけどゴリ押しで通してしまった。
https://yukicoder.me/problems/no/1270

問題

N要素の整数列Aが与えられる。各要素は1～Nの範囲の整数値を取る。
以下のQ個のクエリにそれぞれ答えよ。

• 区間[L,R]が与えられる。A[L]～A[R]を1～Nの任意の整数に置き換えられるとき、転倒数の最小値を求めよ。

解法

A[L]～A[R]をあえて異なる値にする意味はないので、同じ値にすることとする。
A[L]～A[R]を総当たりするが、その前に以下を済ませておく。

• A[L]～A[R]以外の部分の転倒数を求めておく。
• A[0]～A[L-1]の範囲に、xより大きい値がいくつあるか、という配列B[x]を累積和で求める
• A[R+1]～A[N-1]の範囲に、x未満値がいくつあるか、という配列C[x]を累積和で求める

A[L]～A[R]は同じ値を取るのでこの中で転倒数は0なので、A[L]～A[R]の値を総当たりすれば、B,Cを用いて値1つあたりO(1)で転倒数が求められる。
最初の「A[L]～A[R]以外の部分の転倒数」をクエリ毎に毎回BITを使って求めようとすると、全体が計算量O(NQlogN)でTLEするので、クエリ前にAのprefixとsuffixの転倒数をあらかじめ列挙しておこう。
そうすると前処理にO(NlogN)、クエリ毎にO(NQ)で計O(N(Q+logN))となり間に合う。

int N,Q;
int A[20202];

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;}
};
int B[20202],C[20202];

ll pref[202020],suf[202020];

BIT<int,15> bt;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>A[i];
	
	FOR(i,N) {
		if(i) pref[i]+=pref[i-1];
		pref[i]+=bt(N)-bt(A[i]);
		bt.add(A[i],1);
	}
	ZERO(bt.bit);
	for(i=N-1;i>=0;i--) {
		suf[i]=suf[i+1]+bt(A[i]-1);
		bt.add(A[i],1);
	}
	
	
	FOR(i,Q) {
		int L,R;
		ZERO(B);
		ZERO(C);
		
		cin>>L>>R;
		L--,R--;
		ll ret=(L?pref[L-1]:0)+suf[R+1];
		FOR(j,L) B[A[j]]++;
		for(j=N+1;j>=1;j--) B[j]+=B[j+1];
		for(j=R+1;j<N;j++) {
			ret+=B[A[j]+1];
			C[A[j]]++;
		}
		
		for(j=1;j<=N+1;j++) C[j]+=C[j-1];
		int mi=1<<30;
		for(j=1;j<=N;j++) mi=min(mi,(R-L+1)*(B[j+1]+C[j-1]));
		cout<<mi+ret<<endl;
		
	}
}

まとめ

これ想定解じゃなかったのか…。