给定一个如图所示的计算方法:
现在给定长 的数组 和 ,要求 次询问 的值。
,,,。
设 表示 经过区间 后要减多少次 ,发现这个是分成 段的分段函数。
直接线段树,设 表示最小的 满足经过节点 对应的区间后减了 次 ,那么空间复杂度是 的,询问时可以直接二分找到应该减去的值,单次询问时间复杂度 。
考虑如何合并 的左右儿子, 和 可以贡献到 当且仅当:
因为在区间 是经过左区间要减 次 的最大的数。
那么对于一对合法的 有:
但是直接做是 的,发现:
因为 是减 次 的最小的数,它经过区间时每一次 的结果的最大值一定是 ,那么想要让它减多一次 就至少要给它加上 。
那么对于合法的 ,设 ,则一定有:
因为:
所以 。
由于 所以若 合法则 也一定合法,那么能动 就尽量先动 即可。
时间复杂度 ,代码如下:
// 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;
}