是 Ynoi 捏。
建一棵线段树，线段树上每个节点维护一个长度为 \(len\) 的 DP 数组 \(f_i\) 表示 \(v\) 最少需要多少才能使得从左往右将 \(v\) 与区间中的数进行图中的相加操作后会减掉至少 \(i\) 次 \(p\)。
如果我们能预处理出 \(f_i\)，那么查询是容易的，直接找到对应的区间然后 lower_bound 一下即可知道经过这个区间的操作后 \(v\) 会变成多少。单次查询复杂度 \(O(\log^2n)\)，在 \(n\) 比较大 \(q\) 比较小的情况下刚好能过。
考虑怎么求出 \(f_i\)。难点在于子区间的合并，我们假设从 \(f,g\) 合并得到 \(h\)，那么有 \(\max(f_x,g_y-(suml-xp))\to h_{x+y}\)，这里有个前提是 \(f_{x+1}-1+suml-xp\ge g_y\)，即最大的满足经过左子区间后会减恰好 \(x\) 次 \(p\) 的数经过左子区间的操作后要比 \(g_y\) 大。这样暴力是平方的，考虑优化。猜决策点满足单调性，这是因为 \(f_x-g_y+suml-xp\) 是单调的，所以肯定一段负一段正，最优决策点肯定在正负的交界处。而 \(f_x-g_y+suml-xp\) 的单调性的证明就等价于证明 \(f_{x+1}-f_x\ge p\)，感性理解一下是因为 \(f_x\) 是最小的初始值，所以到达某个分界点的时候 \(v\) 的值肯定是 \(0\)，因此如果你想再多减一个 \(p\) 就至少需要让初始值提高 \(p\)。
这样你用 two pointers 进行合并的过程即可，时间复杂度 \(O(n\log n+q\log^2n)\)。
const int MAXN=1e6;
const ll INF=1e18;
int n,qu,p,a[MAXN+5];
struct node{int l,r;ll sum;vector<ll>nd;}s[MAXN*4+5];
void pushup(int k){
s[k].sum=s[k<<1].sum+s[k<<1|1].sum;
for(int i=1;i<=s[k].r-s[k].l+1;i++)s[k].nd[i]=INF;s[k].nd[0]=-INF;
for(int x=0,y=0;x<s[k<<1].nd.size();x++){
if(y==s[k<<1|1].nd.size())--y;
while(y<s[k<<1|1].nd.size()){
ll mxv=(x+1==s[k<<1].nd.size())?INF:(s[k<<1].nd[x+1]-1-1ll*x*p+s[k<<1].sum);
if(mxv<s[k<<1|1].nd[y]){if(y)y--;break;}
chkmin(s[k].nd[x+y],max(s[k<<1].nd[x],s[k<<1|1].nd[y]+1ll*x*p-s[k<<1].sum));
++y;
}
}
// printf("[%d,%d]\n",s[k].l,s[k].r);
// for(int i=0;i<s[k].nd.size();i++)printf("nd[%d]=%lld\n",i,s[k].nd[i]);
}
void build(int k,int l,int r){
s[k].l=l;s[k].r=r;s[k].nd.resize(r-l+2);
if(l==r){s[k].sum=a[l];s[k].nd[0]=-INF;s[k].nd[1]=p-a[l];return;}
int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k);
}
ll query(int k,int l,int r,ll x){
if(l<=s[k].l&&s[k].r<=r){
int cnt=upper_bound(s[k].nd.begin(),s[k].nd.end(),x)-s[k].nd.begin()-1;
return x+s[k].sum-1ll*cnt*p;
}
int mid=s[k].l+s[k].r>>1;
if(r<=mid)return query(k<<1,l,r,x);else if(l>mid)return query(k<<1|1,l,r,x);
else return query(k<<1|1,mid+1,r,query(k<<1,l,mid,x));
}
int main(){
scanf("%d%d%d",&n,&qu,&p);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
build(1,1,n);
while(qu--){
int l,r;scanf("%d%d",&l,&r);
printf("%lld\n",query(1,l,r,0));
}
return 0;
}