CF455E Function

CF455E Function

按照题意模拟容易发现，这玩意就是在 \([r - l, r]\) 区间内可重复选择数字求最小值，但是有个特殊要求也就是如果，你从 \(i\) 开始选，那么 \([i, r]\) 都必须至少选 \(1\) 个。

容易发现，肯定尽量重复选小的 \(val_i\)。也就是答案是 \(s_r - s_i + (l-r+i) \cdot a_i\)。(\(s\) 为前缀和。)

然后可以知道 \(i\) 一定是 \([r-l, r]\) 区间中最小的。

• 如果有 \(j \in (i, r] \ \& \ val_j \le val_i\) 显然 \([j, r]\) 贡献一致。当选择区间在 \([j,r]\) 时，多余出来的数选其中最小值也就是 \(val_j\) 最优。

• \([i+1, r]\) 各选一个，剩下全选 \(val_i\) 根据上面显然最优。

当 \(i \lt j\) 时，并且选 \(i\) 比选 \(j\) 更优秀。

那么 \(s_r - s_i + (l - r + i) \cdot a_i \le s_r - s_j + (l - r + j) \cdot a_j\)

\((l-r)(a_i-a_j) \lt (s_i - i \cdot a_i) - (s_j - j \cdot a_j)\)

整理可以得到 \(l - r \gt \dfrac{(s_i - i \cdot a_i) - (s_j - j \cdot j \cdot a_j)}{a_i - a_j}\)

注意 \(a_i \lt a_j\)。

然后就维护一个凸包（单调栈维护）。

因为斜率不单调，所以不能用单调队列。

每次找到起点，终点，然后二分斜率随便做。

/*
	Name: CF455E
	Author: Gensokyo_Alice
	Date: 2020/11/17
	Description:
*/
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include