自动搬运

查看原文

来自洛谷，原作者为

	Suzt_ilymtics 公主与玫瑰，随时待骑士归来 | AFO | SDUer

搬运于2025-08-24 22:36:00，当前版本为作者最后更新于2022-02-06 19:39:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

同步发表在我的博客

题目传送ww

看到这个牛棚的开心值的计算方法，显然要用单调队列去处理，这样的话，对于一个已知的牛棚，我们可以在 $\mathcal O(n)$ 的时间内计算出整个牛棚的开心值。

我们考虑枚举能插的每一个位置。

借助单调队列模拟这个过程的话可以做到 $\mathcal O(n^2)$，期望得分 $30$。

考虑优化，发现在放 $i$ 位置和 $i+1$ 位置的时候很多位置的贡献是不会变化的，那我们只考虑变化了的。

我们考虑在第 $x$ 和第 $x+1$ 个牛之间插入一个牛。

以 $n = 6, m = 3, x = 3$ 为例。

插之前： ###### ；插之后：###x###。

# 从左到右编号 $1 \sim 6$。

我们发现 $[2,4], [3,5]$ 的贡献变成了 $[2,x], [3,4], [x, 5]$ 这三个区间。

后面这三个区间的贡献可以表示成原序列中三个长度为 $2$ 的区间和插入的 $x$ 去 $\max$ 求和贡献。

我们可以用单调队列两次分别预处理出每个长度为 $m$ 的区间的贡献和每个长度为 $m-1$ 的区间的贡献。

然后，我们从前到后枚举插入的位置 $x$ （序列中第 $x$ 个元素的后面）的时候，发现这些有贡献的区间的范围是不断右移的，根据 $x,m$ 就可以确定出这个范围，然后用类似双指针的写法更新即可。

因为所有预处理包括后面的枚举插入位置都是 $\mathcal O(n)$ 的，所以总复杂度为 $\mathcal O(n)$，期望得分 $100$。

更多细节看代码吧。

/*
Work by: Suzt_ilymtics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define int long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 5e6+5;
const int INF = 1e9+7;
const int mod = 1e9+7;

int n, m, A;
int res = 0, Ans = 0, ans = 0;
int a[MAXN];
int b[MAXN], c[MAXN];
int q[MAXN], head = 1, tail = 0;

int read() {
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0', ch = getchar();
    return f ? -s : s;
}

signed main()
{
    n = read(), m = read(), A = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    for(int i = 1; i < m; ++i) {
        while(head <= tail && a[q[tail]] < a[i]) tail --;
        q[++tail] = i;
    }
    for(int i = m; i <= n; ++i) {
        while(head <= tail && q[head] < i - m + 1) head ++;
        while(head <= tail && a[q[tail]] < a[i]) tail --;
        q[++tail] = i;
        b[i - m + 1] = a[q[head]];
    }
    head = 1, tail = 0;
    int p = m - 1;
    for(int i = 1; i < p; ++i) {
        while(head <= tail && a[q[tail]] < a[i]) tail --;
        q[++tail] = i;
    }
    for(int i = p; i <= n; ++i) {
        while(head <= tail && q[head] < i - p + 1) head ++;
        while(head <= tail && a[q[tail]] < a[i]) tail --;
        q[++tail] = i;
        c[i - p + 1] = a[q[head]];
    }
    for(int i = 1; i <= n - p + 1; ++i) {
        c[i] = max(c[i], A);
    }
    for(int i = 1; i <= n - m + 1; ++i) ans += b[i];
    // 短区间长度为 m-1，个数为 m
    // 长区间长度为 m，个数为 m - 1
    // 若，插 i, i + 1 之间，所涉短区间为 [i - m + 2, i + 1]，所涉长区间为 [i - m + 2, i] 
    for(int i = 0; i <= n; ++i) {
        res -= b[i], res += c[i + 1];
        if(i - m + 1 >= 1) res += b[i - m + 1] - c[i - m + 1];
        Ans = max(Ans, ans + res);
    }
    printf("%lld\n", Ans);
    return 0;
}