Codeforces #240 Div1 C. Mashmokh and Reverse Operation

これは自力で解けはしたけどTLEスレスレ。
http://codeforces.com/contest/414/problem/C

問題

正の整数Nに対し、2^N要素の数列Aが与えられる。

ここでM個のクエリが与えられる。
各クエリは数値qからなっており、qに対してAの要素を先頭から2^q要素ごとの2^(N-q)個の塊に分割する。
そして個々の塊の中の並び順を反転し、再び結合して2^N要素の数列Aに戻す。

各クエリ実行後におけるA中のinversion数、すなわち値の大小が降順になってしまっている要素対の数を返せ。

解法

数値qに対する反転処理は、以下のように考えることができる。
p

int N,M,L;
ll A[2000000];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	BIT(){clear();};
	void clear() {ZERO(bit);};
	V total(int entry) {
		V s=0;
		entry++;
		while(entry>0) s+=bit[entry-1], entry -= entry & -entry;
		return s;
	}
	void update(int entry, V val) {
		entry++;
		while(entry <= (1<<ME)) bit[entry-1] += val, entry += entry & -entry;
	}
};
BIT<int,21> bt;

ll RV[2][20];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	L=1<<N;
	map<int,int> MM;
	
	FOR(i,L) {
		cin>>A[i];
		MM[A[i]]=0;
	}
	i=0;
	ITR(it,MM) it->second=++i;
	FOR(i,L) A[i]=MM[A[i]];
	
	FOR(i,N) {
		int step=(1<<i);
		bt.clear();
		for(j=0;j<L;j+=step*2) {
			FOR(k,step) bt.update(A[j+k+step],1);
			FOR(k,step) RV[0][i]+=bt.total(A[j+k]-1);
			FOR(k,step) bt.update(A[j+k+step],-1);
			FOR(k,step) bt.update(A[j+k],1);
			FOR(k,step) RV[1][i]+=bt.total(A[j+k+step]-1);
			FOR(k,step) bt.update(A[j+k],-1);
		}
	}
	
	cin>>M;
	int mask=0;
	while(M--) {
		cin>>i;
		mask ^= (1<<i)-1;
		
		ll ret=0;
		FOR(i,N) ret+=RV[(mask>>i)&1][i];
		_P("%lld\n",ret);
	}
	
}

まとめ

自力で解けてよかった。