自动搬运

查看原文

来自洛谷，原作者为

	Drifty zzzzzzᙆᙆᙆᙆᙆᙆ

搬运于2025-08-24 23:03:30，当前版本为作者最后更新于2024-09-01 10:09:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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;
}