ABC190 F - Shift and Inversions

問題

atcoder.jp

解法

• k=0における転倒数はBITで求められる。
• $a_i$にkを足してmodNをとるという操作は、数列の先頭の要素が削除されて最後尾に追加されるという操作と等しい。
• $a_i$ が削除されると転倒数が$a_i$減り（$a_i$を転倒数として数えられるのは、0から$a_i-1$までなので）、最後尾に追加すると転倒数が$N-1-a_i$増える。そのため、各kにおける転倒数はO(1)で求められる。

コード

#include <bits/stdc++.h>
#include <atcoder/all>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())

using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

void print() {
  cout << endl;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  cout << head;
  if (sizeof...(tail) != 0) cout << " ";
  print(forward<Tail>(tail)...);
}

template <class T>
void print(vector<T> &vec) {
  for (auto& a : vec) {
    cout << a;
    if (&a != &vec.back()) cout << " ";
  }
  cout << endl;
}

template <class T>
void print(vector<vector<T>> &df) {
  for (auto& vec : df) {
    print(vec);
  }
}

template<typename T>
struct BIT {
  int n;
  vector<T> d;
  BIT(int n=0):n(n),d(n+1) {}
  void add(int i, T x=1) {
    for (i++; i <= n; i += i&-i) {
      d[i] += x;
    }
  }
  T sum(int i) {
    T x = 0;
    for (i++; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }
  T sum(int l, int r) {
    return sum(r-1) - sum(l-1);
  }
};


int main() {
  int n;
  cin >> n;
  vi a(n);
  rep(i,n)cin >> a[i];
  BIT<ll> bit(n);
  ll cnt = 0;
  rep(i,n){
    cnt+=i-bit.sum(a[i]);
    bit.add(a[i],1);
  }
  rep(k,n){
    print(cnt);
    cnt = cnt-a[k]+n-1-a[k];
  }
  return 0;
}