一、题目
二、解法
直接上线段树维护，其实可以把每一个区间看成一个函数 \(f(x)\)，表示如果传进来的初值是 \(x\) 那么得到的值是 \(f(x)\)，如果我们成功维护出每个区间的 \(f(x)\) 那么只需要进行 \(\log\) 次函数运算得到答案。
不难发现 \(f(x)\) 是分段的，设 \(c_i\) 表示减去次数 \(=i\) 的最小初始值，那么 \(x\in[c_i,c_{i+1})\) 时减去的数量时 \(i\cdot p\)，而且 \(i\) 的取值只有 \(r-l+1\) 种，这启示我们可以去维护 \(c_i\)
考虑怎么通过左右子树合并得到 \(c_i\)，设左子树为 \(lc_i\) 右子树为 \(rc_i\)，枚举在左边减少了 \(x\) 次，在右边减少了 \(y\) 次。那么可以转移到 \(c_{x+y}\) 的条件是 \(lc_{x+1}-1+lsum-xp\geq rc_y\)，也就是左边的最大初值进行运算的结果要能满足右边的最小初值，转移：
\[c_{x+y}\leftarrow \max(lc_x,rc_y-lsum+xp) \]暴力合并是 \(O(len^2)\) 的，这时候可以找一找有关转移点的结论了。
结论：在都合法的情况下，从 \((x,y)\) 转移比 \((x+1,y-1)\) 更优，可以考虑推导一下不等式：
\[lc_{x+1}-1+lsum-xp\geq rc_y \] \[lc_{x+1}>rc_y+xp-lsum \] \[\max(lc_{x+1},rc_{y-1}-lsum+(x+1)p)>\max(lc_{x},rc_y+xp-lsum) \]那么在合法的情况下我们取最小的 \(x\) 转移即可，如果不合法我们增大 \(x\) 即可，用双指针维护。那么预处理的时间复杂度 \(O(n\log n)\)，每次计算需要二分，所以复杂度是 \(O(m\log^2n)\)
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 4000005;
#define int long long
const int inf = 1e18;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,p,x,a[M],s[M];vector<int> f[M];
void up(int i,int l,int r)
{
int mid=(l+r)>>1;
s[i]=s[i<<1]+s[i<<1|1];
for(int x=0,y=0;x<=mid-l+1;x++)
{
if(y==r-mid+1) y--;
for(;y<=r-mid;y++)
{
int nd=f[i<<1][x+1]-1+s[i<<1]-x*p;
if(nd<f[i<<1|1][y]) {y--;break;}
f[i][x+y]=min(f[i][x+y],max(f[i<<1][x]
,f[i<<1|1][y]+x*p-s[i<<1]));
}
}
}
void build(int i,int l,int r)
{
f[i].resize(r-l+3);
for(int j=2;j<=r-l+2;j++) f[i][j]=inf;
f[i][0]=-inf;f[i][1]=p-a[l];
if(l==r) {s[i]=a[l];return ;}
int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
up(i,l,r);
}
void ask(int i,int l,int r,int L,int R)
{
if(L>r || l>R) return ;
if(L<=l && r<=R)
{
int y=upper_bound(f[i].begin(),f[i].end(),x)
-f[i].begin()-1;x+=s[i]-p*y;
return ;
}
int mid=(l+r)>>1;
ask(i<<1,l,mid,L,R);
ask(i<<1|1,mid+1,r,L,R);
}
signed main()
{
n=read();m=read();p=read();
for(int i=1;i<=n;i++) a[i]=read();
build(1,1,n);
while(m--)
{
int l=read(),r=read();
x=0;ask(1,1,n,l,r);
printf("%lld\n",x);
}
}