SP2940题解

啃论文的时候论文里面的题。

题意：

1. 区间加
2. 询问区间前缀和之和的最值。

我们先弱化一下问题：将“区间”二字去掉。

我们思考一下一个点可能成为答案的条件。假设现在总共进行的区间加操作令整个序列加上了 \(k\)，那么 \(i\) 比 \(j\) 厉害的条件就是：

\[s_j +j \times k \leq s_i+i \times k \]

\[(j-i) \times k \leq s_i-s_j \]

\[k \leq \frac {s_i-s_j} {j-i} \]

\[\frac {s_i-s_j}{i-j} \leq -k \]

注意到这里类似斜率，相当于将位置 $ i $ 看做一个点 $ (i,s_i) $ 后对整个序列建立凸壳，每次查询时在凸壳上二分。

回到原问题上，我们只需要维护出整个区间的凸壳即可。

但是维护整个区间的凸壳过于困难，考虑分块，将整个区间拆成几个散块和一堆块，对大块维护凸壳，散块直接暴力。

区间加只需要大块打标记，散块重构凸包即可。

设块长为 \(B\)。复杂度是 \(O(n\log n+m(\frac n B\log n+B)+m(\frac n B+B)\)，取 \(B=\sqrt {n\log n}\) 即可得到复杂度 \(O(n\log n+m\sqrt {n\log n})\)。

但是不知道为什么取 \(B=\sqrt n\) 跑得更快。。。

#include
#include
#include
typedef long long ll;
const int M=50005,B=225;
int n,m,p,L[M/B+5],R[M/B+5],id[M],pos[M];ll S[M/B+5];char X[1<<24|1],Y[1<<24|1],*p1=X,*p2=Y;
inline ll max(const ll&a,const ll&b){
	return a>b?a:b;
}
struct Block{
	int n,len,tag,a[B+5],id[B+5];ll s[B+5];
	inline void Update(){
		for(int i(1);i<=n;++i)a[i]+=tag,s[i]=s[i-1]+a[i];s[n+1]=-1e18/2;tag=0;
	}
	inline ll Query(){
		int L(1),R(len),mid,ans(0);
		while(L<=R){
			mid=L+R>>1;
			if(s[id[mid]]+id[mid]*tag<=s[id[mid+1]]+id[mid+1]*tag)L=mid+1,ans=mid;
			else R=mid-1;
		}
		return s[id[ans+1]]+1ll*id[ans+1]*tag;
	}
	inline void Build(){
		Update();len=0;
		for(int i=1;i<=n;++i){
			while(len>1&&(s[i]-s[id[len]])*(id[len]-id[len-1])>=(s[id[len]]-s[id[len-1]])*(i-id[len]))--len;
			id[++len]=i;
		}
		id[len+1]=n+1;
	}
}block[M/B+5];
inline void update(){
	for(int i=1;(i-1)*p