310-01-ACOJ-0864 : 奶牛赛跑

题目大意：

有$n$头奶牛，在一个圆形的赛跑场地里赛跑。所有奶牛同时从起点出发，奶牛的速度都是匀速的，其中第$i$头牛的速度为$v_i$，跑道的长度为单位$1$。当跑得最快那头奶牛跑完$k$圈之后，比赛就结束了。

有时候，跑得快的奶牛可以比跑得慢的奶牛多绕赛场几圈，从而在一些时刻超过慢的奶牛。这就是最令观众激动的套圈事件了。请问在整个比赛过程中，套圈事件一共会发生多少次呢？

题解：

对于这道题，很显然可以直接求解（小学问题），然后要考虑的是如何降低计算的时间复杂度（原来是$O(n^2)$。

由于每一个奶牛的追击追击次数可以显然得到：$\lfloor \frac {(v_i - v_j)}{v}k\rfloor$，所以要求的就是$\sum_{1≤j<i≤n}\lfloor\frac {v_i - v_j}{v}k\rfloor$。

那么采用整数与小数分离的思想计算：（对于负数向下取整是更小，所以对于$-0. ~…$向下取整为$-1$）

$$
\begin {align*}
&\frac {(v_i-v_j)} {v} k = A + \alpha \\
\Rightarrow~&\frac {v_ik}v - \frac {v_jk}v = A_i + \alpha_i - (A_j + \alpha_j) \\
\Rightarrow~&\sum_{1≤j<i≤n}\lfloor\frac {v_i - v_j}{v}k\rfloor = \sum_{1≤j<i≤n}(A_i - A_j)+\sum_{1≤j<i≤n}\lfloor\alpha_i - \alpha_j\rfloor \\
&\sum_{1≤j<i≤n}(A_i - A_j) \\
=~&\sum_{1≤i≤n}[(i - 1)A_i - (n - i)A_i] = \sum_{1≤i≤n}(i - 1 - n + i) A_i = \sum_{1≤i≤n}(2i - 1 - n)A_i
\end {align*}
$$

而可以发现$\sum_{1≤j<i≤n} \lfloor \alpha_i - \alpha_j\rfloor$就是求$\alpha$序列的逆序对个数。

而对于求逆序对同样可以进行优化（因为小数求逆序对需要进行离散化，很烦），令$\alpha_i’ = v_i \times k \mod v_n$，这非常好证明。

正解：

#include <iostream>
#include <algorithm>
#define int long long

using namespace std;

int n, k;
const int maxn = 1000005;
int v[maxn];
int A[maxn], a[maxn];

struct node {
    int id, val;
} B[maxn];

int T[maxn];

int lb(int i) { return i & (-i); }

bool cmp(node a, node b) {
    if (a.val == b.val) return a.id < b.id;
    return a.val < b.val;
}

void add(int i, int d) {
    while (i <= n + 100) {
        T[i] += d;
        i += lb(i);
    }
}

int sum(int i) {
    int ans = 0;
    while (i > 0) {
        ans += T[i];
        i -= lb(i);
    }
    return ans;
}

signed main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i ++) cin >> v[i];
    sort(v + 1, v + 1 + n);
    int ans = 0;
    for (int i = 1; i <= n; i ++) {
        A[i] = v[i] * k / v[n]; a[i] = v[i] * k % v[n];
        ans += (2 * i - 1 - n) * A[i];
        B[i] = (node) {i, a[i]};
    }
    sort(B + 1, B + 1 + n, cmp);
//  for (int i = 1; i <= n; i ++) cout << B[i].id << " " << B[i].val << endl;
    for (int i = 1; i <= n; i ++) {
        int p = sum(B[i].id - 1);
        ans -= (i - 1 - p);
        add(B[i].id, 1);
    }
    cout << ans << endl;
    return 0;
}