CF1172F Nauuo and Bug & P5609 做题记录

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

现在给定长 $n$ 的数组 $a$ 和 $p$，要求 $q$ 次询问 $\text{sum}(a,l_i,r_i,p)$ 的值。

$1\le n\le 10^6$，$1\le m\le 2\times 10^5$，$1\le p\le 10^9$，$|a_i|\le 10^9$。

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

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

考虑如何合并 $u$ 的左右儿子，$c_{ls,x}$ 和 $c_{rs,y}$ 可以贡献到 $c_{u,x+y}$ 当且仅当：

$c_{ls,x+1}-1+sum_{ls}-xp\ge c_{rs,y}$

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

那么对于一对合法的 $x,y$ 有：

$c_{u,x+y}=\min(c_{u,x+y},\max(c_{ls,x},c_{rs,y}-sum_{ls}+xp))$

但是直接做是 $O(n^2)$ 的，发现：

$c_{u,x+1}\ge c_{u,x}+p$

因为 $c_{u,x}$ 是减 $x$ 次 $p$ 的最小的数，它经过区间时每一次 $MODADD$ 的结果的最大值一定是 $0$，那么想要让它减多一次 $p$ 就至少要给它加上 $p$。

那么对于合法的 $x,y$，设 $f(x,y)=\max(c_{ls,x},c_{rs,y}-sum_{ls}+xp)$，则一定有：

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

因为：

$c_{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)<c_{ls,x+1}=f(x+1,y-1)$。

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

时间复杂度 $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;
}