計算量に自信がなかったけど、正解できてよかった。
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が心配になる。