CF1172F Nauuo and Bug & P5609 做题记录

给定一个如图所示的计算方法:

现在给定长 nn 的数组 aapp,要求 qq 次询问 sum(a,li,ri,p)\text{sum}(a,l_i,r_i,p) 的值。

1n1061\le n\le 10^61m2×1051\le m\le 2\times 10^51p1091\le p\le 10^9ai109|a_i|\le 10^9

F(x,l,r)F(x,l,r) 表示 xx 经过区间 [l,r][l,r] 后要减多少次 pp,发现这个是分成 rl+1r-l+1 段的分段函数。

直接线段树,设 cu,xc_{u,x} 表示最小的 xx 满足经过节点 uu 对应的区间后减了 xxpp,那么空间复杂度是 O(nlogn)O(n\log n) 的,询问时可以直接二分找到应该减去的值,单次询问时间复杂度 O(nlog2n)O(n\log ^2n)

考虑如何合并 uu 的左右儿子,cls,xc_{ls,x}crs,yc_{rs,y} 可以贡献到 cu,x+yc_{u,x+y} 当且仅当:

cls,x+11+sumlsxpcrs,yc_{ls,x+1}-1+sum_{ls}-xp\ge c_{rs,y}

因为在区间 cls,x+11c_{ls,x+1}-1 是经过左区间要减 xxpp 的最大的数。

那么对于一对合法的 x,yx,y 有:

cu,x+y=min(cu,x+y,max(cls,x,crs,ysumls+xp))c_{u,x+y}=\min(c_{u,x+y},\max(c_{ls,x},c_{rs,y}-sum_{ls}+xp))

但是直接做是 O(n2)O(n^2) 的,发现:

cu,x+1cu,x+pc_{u,x+1}\ge c_{u,x}+p

因为 cu,xc_{u,x} 是减 xxpp 的最小的数,它经过区间时每一次 MODADDMODADD 的结果的最大值一定是 00,那么想要让它减多一次 pp 就至少要给它加上 pp

那么对于合法的 x,yx,y,设 f(x,y)=max(cls,x,crs,ysumls+xp)f(x,y)=\max(c_{ls,x},c_{rs,y}-sum_{ls}+xp),则一定有:

f(x,y)<f(x+1,y1)f(x,y)<f(x+1,y-1)

因为:

cls,x+11+sumlsxpcrs,ycrs,ysumls+xp+1cls,x+1crs,ysumls+xp<cls,x+1c_{ls,x+1}-1+sum_{ls}-xp\ge c_{rs,y}\\ c_{rs,y}-sum_{ls}+xp+1\le c_{ls,x+1}\\ c_{rs,y}-sum_{ls}+xp<c_{ls,x+1}\\

所以 f(x,y)<cls,x+1=f(x+1,y1)f(x,y)<c_{ls,x+1}=f(x+1,y-1)

由于 cu,x+1cu,x+pc_{u,x+1}\ge c_{u,x}+p 所以若 x,yx,y 合法则 x+1,yx+1,y 也一定合法,那么能动 yy 就尽量先动 yy 即可。

时间复杂度 O(nlogn+mlog2n)O(n\log n+m\log^2n),代码如下:

// Problem: Nauuo and Bug
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1172F
// Memory Limit: 1000 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

const int S=1000005;

int n,m;
long long p,a[S];
long long sum[S<<2];
vector<long long> c[S<<2];

inline void merge(int u)
{
	int ls=u<<1,rs=u<<1|1;
	sum[u]=sum[ls]+sum[rs];
	int lc=c[ls].size()-1,rc=c[rs].size()-1;
	for(int i=1;i<=lc+rc;i++) c[u][i]=1e17;
	for(int x=0,y=0;x<=lc;x++)
	{
		if(y>rc) y--;
		while(y<=rc)
		{
			if(x!=lc&&c[ls][x+1]-1+sum[ls]-x*p<c[rs][y])
			{
				if(y>0) y--;
				break;
			}
			c[u][x+y]=min(c[u][x+y],max(c[ls][x],c[rs][y]-sum[ls]+x*p));
			y++;
		}
	}
}

void build(int u,int l,int r)
{
	c[u]=vector<long long>(r-l+2,0);
	c[u][0]=-1e17;
	if(l==r) return sum[u]=a[l],c[u][1]=p-a[l],void();
	int mid=l+r>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	merge(u);
}

long long que(int u,int l,int r,int L,int R,long long val)
{
	if(l>R||r<L) return val;
	if(l>=L&&r<=R) return val+sum[u]-(upper_bound(c[u].begin(),c[u].end(),val)-c[u].begin()-1)*p;
	int mid=l+r>>1;
	return que(u<<1|1,mid+1,r,L,R,que(u<<1,l,mid,L,R,val));
}

int main()
{
	scanf("%d%d%lld",&n,&m,&p);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,1,n);
	while(m--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%lld\n",que(1,1,n,l,r,0));
	}
	return 0;
}