#include #include #include #include using namespace std; using namespace atcoder; using namespace __gnu_pbds; using ll=long long; using ld=long double; using vll=vector; using vvll=vector; using pll=pair; // using mint=modint; // template // using ordered_map=tree,rb_tree_tag,tree_order_statistics_node_update>; #line 2 "dp/inversion-counting.hpp" #line 2 "data-structure/binary-indexed-tree.hpp" template struct BinaryIndexedTree { int N; vector data; BinaryIndexedTree() = default; BinaryIndexedTree(int size) { init(size); } void init(int size) { N = size + 2; data.assign(N + 1, {}); } // get sum of [0,k] T sum(int k) const { if (k < 0) return T{}; // return 0 if k < 0 T ret{}; for (++k; k > 0; k -= k & -k) ret += data[k]; return ret; } // getsum of [l,r] inline T sum(int l, int r) const { return sum(r) - sum(l - 1); } // get value of k inline T operator[](int k) const { return sum(k) - sum(k - 1); } // data[k] += x void add(int k, T x) { for (++k; k < N; k += k & -k) data[k] += x; } // range add x to [l,r] void imos(int l, int r, T x) { add(l, x); add(r + 1, -x); } // minimize i s.t. sum(i) >= w int lower_bound(T w) { if (w <= 0) return 0; int x = 0; for (int k = 1 << __lg(N); k; k >>= 1) { if (x + k <= N - 1 && data[x + k] < w) { w -= data[x + k]; x += k; } } return x; } // minimize i s.t. sum(i) > w int upper_bound(T w) { if (w < 0) return 0; int x = 0; for (int k = 1 << __lg(N); k; k >>= 1) { if (x + k <= N - 1 && data[x + k] <= w) { w -= data[x + k]; x += k; } } return x; } }; /** * @brief Binary Indexed Tree(Fenwick Tree) */ #line 4 "dp/inversion-counting.hpp" // 転倒数 template long long inversion_counting(const vector& v) { vector xs{v}; sort(begin(xs), end(xs)); xs.erase(unique(begin(xs), end(xs)), end(xs)); int s = xs.size(); BinaryIndexedTree bit(s + 1); long long ans = 0; for (auto& x : v) { int i = lower_bound(begin(xs), end(xs), x) - begin(xs); if (i + 1 != s) ans += bit.sum(i + 1, s - 1); bit.add(i, 1); } return ans; } // 隣接 swap によって v を w に変えるのにかかる手数 (不可能 : -1) template long long swap_distance(const vector& v, const vector& w) { if (v.size() != w.size()) return -1; int N = v.size(); vector> vv(N), ww(N); for (int i = 0; i < N; i++) { vv[i] = make_pair(v[i], i); ww[i] = make_pair(w[i], i); } sort(begin(vv), end(vv)); sort(begin(ww), end(ww)); for (int i = 0; i < N; i++) { if (vv[i].first != ww[i].first) return -1; } vector order(N); for (int i = 0; i < N; i++) { order[vv[i].second] = ww[i].second; } return inversion_counting(order); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); /* 添字をKで割ったあまりでグループを作る、ソートはグループの中のみ行います、それだけで列全体をソートできるかの問題です。できれば、グループごとに転倒数を求めればいい。 */ ll N,K; cin>>N>>K; vll a(N); for(int i=0;i>a[i]; vll b=a; sort(b.begin(),b.end()); ll ans=0; for(int r=0;r