SP2940题解

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

题意：

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

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

我们思考一下一个点可能成为答案的条件。假设现在总共进行的区间加操作令整个序列加上了 $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<iostream>

#include<cctype>

#include<cmath>

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<n;++i)S[i]=S[i-1]+block[i].s[id[R[i]]]+1ll*id[R[i]]*block[i].tag;

}

inline void Modify(const int&l,const int&r,const int&x){

	const int&q=pos[l],&p=pos[r];int i;

	if(q==p){

		for(i=l;i<=r;++i)block[q].a[id[i]]+=x;block[q].Update();block[q].Build();

	}

	else{

		for(i=q+1;i<=p-1;++i)block[i].tag+=x;

		for(i=l;i<=R[pos[l]];++i)block[q].a[id[i]]+=x;block[q].Update();block[q].Build();

		for(i=L[pos[r]];i<=r;++i)block[p].a[id[i]]+=x;block[p].Update();block[p].Build();

	}

	update();

}

inline ll Query(const int&l,const int&r){

	const int&q=pos[l],&p=pos[r];int i;ll ans(-1e18/2);

	if(q==p){

		for(i=l;i<=r;++i)ans=max(ans,S[q-1]+block[q].s[id[i]]+id[i]*block[q].tag);

	}

	else{

		for(i=q+1;i<=p-1;++i)ans=max(ans,block[i].Query()+S[i-1]);

		for(i=l;i<=R[pos[l]];++i)ans=max(ans,S[q-1]+block[q].s[id[i]]+id[i]*block[q].tag);

		for(i=L[pos[r]];i<=r;++i)ans=max(ans,S[p-1]+block[p].s[id[i]]+id[i]*block[p].tag);

	}

	return ans;

}

inline int read(){

	int n(0);bool typ(false);char s;

	while(!isdigit(s=*p1++))typ|=s==45;while(n=n*10+(s&15),isdigit(s=*p1++));return typ?-n:n;

}

inline void write(ll n){

	static char s[18];int top(0);if(n<0)*p2++=45,n=-n;

	while(s[++top]=n%10^48,n/=10);while(*p2++=s[top--],top);

}

signed main(){

	std::cin.read(X,sizeof X);

	int i,x,l,r,opt;p=sqrt(n=read());for(i=1;(i-1)*p<n;++i)L[i]=(i-1)*p+1,R[i]=i*p;

	for(i=1;i<=n;++i)pos[i]=(i-1)/p+1,block[pos[i]].a[id[i]=i-L[pos[i]]+1]=read();R[pos[n]]=n;

	for(i=1;(i-1)*p<n;++i)block[i].n=R[i]-L[i]+1,block[i].Update(),block[i].Build();update();

	m=read();while(m--)opt=read(),l=read(),r=read(),opt?write(Query(l,r)),void(*p2++=10):Modify(l,r,read());

	std::cout.write(Y,p2-Y);

}

巴特西

SP2940题解

最新文章

热门文章