Codeforces #301 Div2 E. Infinite Inversions

良い題材だけど、Div2 Eにしては簡単かな。Div1B/Div2Dでいい気がする。
http://codeforces.com/contest/540/problem/E

問題

無限に続く数列P[i]=iがある。
ここでN個のクエリ(A[i],B[i])が与えられる。
各クエリに対し、PのA[i]番目とB[i]番目を反転させる、ということを繰り返す。

最終的なPのinversion数を求めよ。

解法

まずはmap等を使い、クエリに登場するPの添え字のみ現在の値を管理する。
次に、BITを２つ使って以下を順次求めて総和を求める。

• クエリに登場した添え字間のinversion数を求める
  • クエリに登場した数字を座標圧縮すると、BITでinversion数を求める典型問題になる
• クエリに登場しない数とのinversionを求める
  • クエリの結果P[x]=yとなっているとする。
  • この場合、abs(x-y)個のinversionが生じる。ただし前者のクエリに登場した添え字については前者で考慮しているので、x～yのうち、前者で考慮済みの添え字の分は引き算する。
  • こちらも添え字を座標圧縮した上でBITすることで算出可能。

int N;
map<int,int> M,MP;

template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[1<<ME];
	V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	V set(int e,V v) { add(e,v-val[e]);}
};
BIT<ll,20> bt,bt2;

ll ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	while(N--) {
		cin>>x>>y;
		if(M.count(x)==0) M[x]=x;
		if(M.count(y)==0) M[y]=y;
		MP[x]=MP[y]=0;
		swap(M[x],M[y]);
	}
	MP[0]=0;
	x=0;
	FORR(r,MP) r.second=x++;
	
	for(auto it=M.rbegin();it!=M.rend();it++) {
		ret += bt.total(MP[it->second]);
		bt.add(MP[it->second],1);
		ret += abs(it->second-it->first);
		bt2.add(MP[it->first],1);
	}
	for(auto it=M.rbegin();it!=M.rend();it++) {
		if(it->first<it->second) ret -= bt2.total(MP[it->second])-bt2.total(MP[it->first]);
		if(it->first>it->second) ret -= bt2.total(MP[it->first])-bt2.total(MP[it->second]);
	}
	cout<<ret<<endl;
	
}

まとめ

inversionを求める練習という意味で良い問題。