不参加でした。
https://yukicoder.me/problems/no/694
問題
N要素の整数列Aが与えられる。
Aを1つずつrotateしつつ転倒数を随時答えよ。
解法
まずAを座標圧縮し、BITを使って初期状態の転倒数を数えよう。
以後1つずつrotateしつつ転倒数の差分を計算していく。
数列の先頭要素A[0]を末尾に移動した場合、A[0]>A[i]となるiの数だけ転倒数が減少後、A[0]<A[i]となるiの数だけ転倒数が増加するので、その分をBITで数えていけばよい。
int N; int A[505050]; 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;} }; BIT<ll,20> bt; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; vector<int> V; V.push_back(-1); FOR(i,N) cin>>A[i],V.push_back(A[i]); sort(ALL(V)); V.erase(unique(ALL(V)),V.end()); ll ret=0; FOR(i,N) { A[i]=lower_bound(ALL(V),A[i])-V.begin(); ret+=bt(N+1)-bt(A[i]); bt.add(A[i],1); } cout<<ret<<endl; FOR(i,N-1) { ret-=bt(A[i]-1); ret+=bt(N+1)-bt(A[i]); cout<<ret<<endl; } }
まとめ
これはまぁ簡単。