Solution Of P11015 Inversion Pair

· · 题解

Solution

我们注意到对于任意长度为 k 的序列 p，都有：

\mathrm{W}(p) \ge \sum^{k - 1}_{i=1}\mathrm{W}(\{p_i,p_{i+1}\})

证明显然。

因此我们对于每一次 (x, y) 的询问，不妨令 x\le y，则最短走法即为一步一步走：x\rightarrow x+1\rightarrow \dots\rightarrow y-1\rightarrow y。前缀和维护即可。

AC-Code

以下是 Drifty 给出的实现。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 3e5 + 7;
int a[N], n, q, s[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    cin >> n >> q;
    for (int i=1; i<=n; i++) 
        cin >> a[i], s[i] = s[i - 1] + (a[i] < a[i - 1]);
    for (int x, y; q--; ) {
        cin >> x >> y;
        if (x > y) swap(x, y);
        cout << s[y] - s[x] << '\n';
    }
    return 0;
}