题解 P8102 [LCOI RI]Cow Insertion

题目传送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
#include
#include
#include
#include
#include
#include
#define int long long
#define orz cout<<"lkp AK IOI!"<= 1) res += b[i - m + 1] - c[i - m + 1];
        Ans = max(Ans, ans + res);
    }
    printf("%lld\n", Ans);
    return 0;
}