Fishingprince Plays With Array Again

XChara · 2024-03-05 17:28:36 · 个人记录

当你不会线性规划但是真的很想会这道题。

题意：

定义一个数列的 f(a) 如下：

你可以在一段连续 t(t\in R^+) 时间内，执行如下一种操作：

• 选择 1\le i<n，a_i\leftarrow a_i-xt，a_{i+1}\leftarrow a_{i+1}-yt

• 选择 1\le i<n，a_i\leftarrow a_i-yt，a_{i+1}\leftarrow a_{i+1}-xt

首先，考虑如何求 f(a)，问题相当于我们需要给每个数加上一个非负实数，使得之后的数列能够恰好减成全 0

不妨设 x<y，考虑一个贪心：对于 a_1，它能让 a_2 减去的范围是 [\frac xya_1,\frac yxa_1]，那么进而能推出 a_2 能让 a_3 减去的范围，设该范围为 [L_i,R_i]

我们可以写出一个暴力求数组 arr 的 f 值的代码：

double l=0,r=0,ans=0;
for(int i=1;i<=n;++i)
{
    ans+=arr[i];
    if(l>arr[i])ans+=l-arr[i];
    l=min(l,arr[i]);r=min(r,arr[i]);
    l=arr[i]-l;r=arr[i]-r;
    swap(l,r);
    l*=X/Y;r*=Y/X;
}
ans+=l;
return ans/(X+Y);

看起来很对，就不证明了。

考虑优化这件事情。

这可以视作我们有两个值，一个在奇数位置作为 l，在偶数位置作为 r，另一个反之，两部分是独立的。

而每个位置做的事情相当于一个分段函数，也就是说这是分段函数的复合。

进一步观察，我们发现不管分段函数怎么复合，任意一段区间复合出来的分段函数复合出来一定只有三段：一段常函数，接上一段一次函数，再接上一段常函数

（可以考察变量初值不断增加时产生的影响，其能影响到最后输出值的一定是一段区间，即中间不碰到任意一个 min 的区间，此时输出值与初始值显然是一次函数的关系）

但是此时还有一个问题：对 ans 产生的贡献的分段函数可能有很多段，我们无法保证。

注意到在一次函数的段，由于没有碰到任意一个 min，所以对 ans 的贡献一定是 0

那么我们可以采用楼房重建的思路，提前求出两段常函数对应值输入进右儿子产生的贡献，这样如果输入值在常函数段，我们只需要递归左儿子，如果在一次函数段，我们只需要递归右儿子

在线段树维护这些信息即可，由于是楼房重建，所以是 O(n\log^2n)

然后你点开题解，发现一个代码长度比你短好几倍的 O(n\log n) 做法，并开始思考这一切是否值得。