kmjp's blog

競技プログラミング参加記です

Codeforces #404 Div2 E. Anton and Permutation

計算量に自信がなかったけど、正解できてよかった。
http://codeforces.com/contest/785/problem/E

問題

初期状態でA={1,2,....,N}である数列Aが与えられる。
ここにQ個のクエリが与えられる。
各クエリはL,Rの2値で構成され、AのL番目とQ番目の要素をswapすることを意味する。

各クエリを順に行うとき、それぞれクエリ後の数列の転倒数を求めよ。

解法

なんか過去にもDiv2 Eで転倒数の問題が出ている。
Codeforces #301 Div2 E. Infinite Inversions - kmjp's blog
Codeforces #388 Div2 E. Inversions After Shuffle - kmjp's blog

1回スワップするたびに転倒数がどう変化するかを考える。
まず、Aから要素A[i]を取り除いたとき、転倒数がどう減少するかを考える。
その場合、A[0..(i-1)]のうちA[i]より大きい要素の数と、A[(i+1)..(N-1)]のうちA[i]より小さい要素の数だけ転倒数が減少する。
逆にA[i]が追加された場合、同様の数だけ転倒数が増加する。

これがわかると、スワップする処理では

  • A[L]を取り除く (その際の転倒数の減少分を計算する)
  • A[R]を取り除く (その際の転倒数の減少分を計算する)
  • R番目にA[L]を追加する (その際の転倒数の増分を計算する)
  • L番目にA[R]を追加する (その際の転倒数の増分を計算する)
  • A[L]とA[R]のスワップによる転倒数の変化分を計算する

を順に行うことで転倒数の変化の差分がわかる。

個々の処理では、区間においてある数値より大きい/小さい要素の数を高速に求められればよい。
そこは平方分割を用いることで、1クエリO(√N*logN)、全体でO(Q*√N*logN)で済ませることができる。

int N,Q;
int A[201010];
int L,R;
const int D=500;
vector<int> V[500];

void erase(int id,int v) {
	int b=id/D;
	int i;
	FOR(i,V[b].size()) if(V[b][i]==v) {
		V[b].erase(V[b].begin()+i);
		return;
	}
}

void add(int id,int v) {
	int b=id/D;
	int i;
	FOR(i,V[b].size()) if(v<V[b][i]) {
		V[b].insert(V[b].begin()+i,v);
		return;
	}
	V[b].push_back(v);
}

int getmore(int id,int v) {
	int i,j;
	int ret=0;
	FOR(i,500) {
		if(id<(i+1)*D) {
			for(j=i*D;j<id;j++) if(A[j]>v && A[j]!=1<<20) ret++;
			break;
		}
		else {
			ret += V[i].end()-lower_bound(ALL(V[i]),v);
		}
	}
	return ret;
}
int getless(int id,int v) {
	int i,j;
	int ret=0;
	FOR(i,500) {
		if(id<(i+1)*D) {
			for(j=i*D;j<id;j++) if(A[j]<v) ret++;
			break;
		}
		else {
			ret += lower_bound(ALL(V[i]),v)-V[i].begin();
		}
	}
	return ret;
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) {
		A[i]=i+1;
		add(i,A[i]);
	}
	
	ll ret=0;
	
	while(Q--) {
		cin>>L>>R;
		L--,R--;
		if(L==R) {
			cout<<ret<<endl;
			continue;
		}
		if(L>R) swap(L,R);
		
		if(A[L]<A[R]) ret--;
		else ret++;
		
		ret-=getmore(R,A[R]);
		ret-=A[R]-1-getless(R,A[R]);
		ret-=getmore(L,A[L]);
		ret-=A[L]-1-getless(L,A[L]);
		erase(R,A[R]);
		erase(L,A[L]);
		
		swap(A[L],A[R]);
		add(R,A[R]);
		add(L,A[L]);
		ret+=getmore(R,A[R]);
		ret+=A[R]-1-getless(R,A[R]);
		ret+=getmore(L,A[L]);
		ret+=A[L]-1-getless(L,A[L]);
		
		cout<<ret<<endl;
	}
}

まとめ

平方分割はいつもTLが心配になる。