自动搬运

查看原文

来自洛谷，原作者为

	cf_x I love X

搬运于2025-08-24 23:03:15，当前版本为作者最后更新于2025-08-14 16:47:55，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目大意

给出三个正整数 $n$，$p$，$q$ 和序列 $A_i$，选择一个区间进行排序，求区间排序后 $A_q-A_p$ 最大可以是多少。

核心思路

首先我们知道对于区间 $[L,R]$，只要区间没有包含 $p, q$，那么这种排序是无意义的。

因为我们想要让 $A_q-A_p$ 最大，所以我们有两种方式。

• 让 $A_p$ 尽量小。
• 让 $A_q$ 尽量大。

我们先解决让 $A_p$ 尽量小的问题。我们发现对 $[p,r],r\in[p,n]$ 排序是最优的。为什么呢？

• 当最小值的下标在 $[p,n]$ 之间时，如果你排的是 $[p-1,n]$，那么最小值就跑到了 $p-1$ 的位置上，那么答案会变小。所以不是最优的。
• 当最小值的下标在 $[1,p-1]$ 之间时，这个最小值只会在排序区间的最左边，而不能来到 $p$ 的位置上（提示：最小值的下标在 $[1,p-1]$ 之间哦）。

同理，让 $A_p$ 尽量大的问题也是一样的思路。

非核心思路

当我们排 $[p, q+1]$ 时。这时，不应该是找最大值，而是次大的，因为最大值在 $q+1$ 上。

其余同理。

代码

最后代码如下：

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+10;

int n, p, q;
int a[N];
multiset<int, greater<int> > st1; // 可能有重复元素
multiset<int> st2;

signed main() {
    cin >> n >> p >> q;
    for (int i = 1;i<= n;i++) {
        cin >> a[i];
    }
    int ans = a[q]-a[p]; 
    int minn = 2e9;
    for (int i = p;i<= q;i++) {
        minn = min(minn, a[i]);
        st1.insert(a[i]);
        if (i == q) continue;
        ans = max(ans, a[q]-minn);
    } ans = max(ans, (*st1.begin()) - minn);
    int now = *st1.begin();
    for (int i = q+1;i<= n;i++) {
        minn = min(minn, a[i]);
        if (a[i] >= now) {
            ;
        } else {
            st1.insert(a[i]);
            st1.erase(st1.begin());
            now = *st1.begin();
        }
        ans = max(ans, now - minn);
    }
    int maxn = 0;
    for (int i = q;i>= p;i--) {
        maxn = max(maxn, a[i]);
        st2.insert(a[i]);
        if (i == p) continue;
        ans = max(ans, maxn-a[p]);
    } now = *st2.begin();
    ans = max(ans, maxn-now);
    for (int i = p-1;i>= 1;i--) {
        maxn = max(maxn, a[i]);
        if (a[i] <= now) {
        } else {
            st2.insert(a[i]);
            st2.erase(st2.begin());
            now = *st2.begin();
        }
        ans = max(ans, maxn-now);
    }
    cout << ans << endl;
    return 0;
}