【BZOJ2122】工作评估（分块）

题目链接

• 给定两个长度为 \(n\) 的序列 \(b_{1\sim n}\) 和 \(c_{1\sim n}\)。
• 定义 \(h_a(x,y)=\begin{cases}a&y=x-1,\\\min\{h_a(x,y-1)+b_y,c_y\}&y\ge x\end{cases}\)。
• \(q\) 次询问，每次给定 \(l,r,a\)，求 \(\max_{l\le x\le y\le r}h_a(x,y)\)。
• \(1\le n,m\le5\times10^4\)，\(0\le a_i\le10^5\)，\(|b_i|\le 10^4\)

\(f(x,y,v)\)

定义 \(f(x,y,v)\) 表示一个初始值为 \(v\) 的数在经过 \([x,y]\) 中的操作后将得到的值（操作指先加 \(b_i\)，再向 \(c_i\) 取 \(\min\)）。

首先有一个显然的性质：若 \(v_1 < v_2\)，则 \(f(x,y,v_1)\le f(x,y,v_2)\)。因为更大的数代进去肯定不会使答案变小。

其次，可以发现这个过程中无非两种情况：

• 曾经向某个 \(c_i\) 取 \(\min\) 过。则最终得到的值就相当于 \(c_i\) 经过 \([i+1,y]\) 中的操作后的值，与 \(v\) 无关。故此时的取值就等于 \(f(x,y,INF)\)。
• 不曾向任何 \(c_i\) 取 \(\min\) 过。则 \(f(x,y,v)=v+\sum_{i=x}^yb_i\)。

如果向 \(c\) 取 \(\min\) 过，则 \(v+\sum_{i=x}^yb_i\) 一定大于 \(f(x,y,INF)\)；反之，若不曾取 \(\min\)，\(v+\sum_{i=x}^yb_i\) 一定小于 \(f(x,y,INF)\)。

也就是说，\(f(x,y,v)=\min\{f(x,y,INF),v+\sum_{i=x}^yb_i\}\)。

其中 \(f(x,y,INF)\) 和 \(\sum_{i=x}^yb_i\) 在 \(x,y\) 确定时都是已知的（不妨分别记作 \(g\) 和 \(s\)），也就是说 \(f(x,y,v)=\min\{g,v+s\}\)。

分块处理+二分求值

对于每个块，我们直接抠出所有区间，分别求出它们的 \(g,s\)。

显然，如果一个区间 \(g,s\) 全大于等于另一个区间的 \(g,s\)，那么后者就是一个无用的区间。

将那些有用的区间按 \(g\) 升序，那么也就按 \(s\) 降序。

每次询问代入一个 \(v\) 得到的最大的 \(f(x,y,v)\)，只需要二分找到 \(g,v+s\) 大小关系发生变化的位置 \(x\)。则小于等于 \(x\) 的部分较小值都取 \(g\)，在 \(x\) 处取最大值；大于 \(x\) 的部分较小值都取 \(v+s\)，在 \(x+1\) 处最大值。因此只要比较这两个位置上的值，取较大的那个即可。

这样就能求出块内答案。

然后考虑块间答案，由于代入的值越大得到的值也就越大，所以我们只需要知道经过前面的部分能够得到的最大值。

可能通过前面的最大值与当前块的一段前缀操作得到答案，只要在预处理时抠出每个块的所有前缀类似前面那样二分一下即可。

新的最大值可能是前面的最大值经过当前块所有操作。但也可能是当前块的一段后缀，只要在预处理时抠出每个块的所有后缀类似前面那样二分一下即可。

代码：\(O(n\sqrt n\log n)\)

#include
#define Tp template
#define Ts template
#define Rg register
#define RI Rg int
#define Cn const
#define CI Cn int&
#define I inline
#define W while
#define N 50000 
#define SN 225
using namespace std;
int n,a0,nw,ans,sz,bl[N+5],b[N+5],c[N+5],t1[SN+5],t2[SN+5],t3[SN+5];
struct S {int g,s;I bool operator < (Cn S& o) Cn {return g^o.g?g>1,f[mid].g