Link.
Description.
定义函数 (f(x)) 为 return x<p?x:x-p。
给定长度为 (n(nle 10^6)) 的数列 (a_i(a_iin[-10^9,10^9]))，有 (m(mle 2 imes 10^5)) 次询问。
每次询问给定一个区间，初始 (ans=0)，每次 (ansleftarrow f(ans+a_i))，问从左到右遍历后 (ans) 的答案。
Solution.
相当于你有一个前缀和序列，有一条线，初始在 (p)，每次撞到这条线线就增高 (p)。
问最后线的位置。
然额还是很难做。
相当于每个位置是一个机器，吞进去一个数，吐出来一个数。
其实是一个分段函数，如果吞进去的数 (in[-infty,p-a_i]) 就不会 (-p) 否则就会。
可以考虑用线段树维护。
一个区间的分段函数段数是区间长度的，同时线段树区间总长度是 (O(nlog n)) 的。
然后每次 (O(len)) 双指针合并就行了。
Coding.
点击查看代码
//Coded by Kamiyama_Shiki on 2021.11.09 {{{
//是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
f?x=-x:x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}//}}}
const int N=1000005;int n,q;ll p,a[N];
struct segm{vector<ll>v;ll sm;int ln;}T[N<<2];
inline void pushup(int x)
{
int ls=x<<1,rs=x<<1|1;T[x].sm=T[ls].sm+T[rs].sm;
T[x].v.resize(T[x].ln+2),T[x].v[0]=-1e18;
for(int i=1;i<=T[x].ln+1;i++) T[x].v[i]=1e18;
for(int il=0,ir=0;il<=T[ls].ln;il++)
{
if(ir>T[rs].ln) ir--;
for(;ir<=T[rs].ln;ir++)
{
ll nw=T[rs].v[ir]+il*p-T[ls].sm;
if(T[ls].v[il+1]-1-il*p+T[ls].sm<T[rs].v[ir]) {ir?ir--:0;break;}
T[x].v[il+ir]=min(T[x].v[il+ir],max(T[ls].v[il],nw));
}
}
}
inline void build(int x,int l,int r)
{
T[x].ln=r-l+1;if(l^r) build(x<<1,l,(l+r)>>1),build(x<<1|1,((l+r)>>1)+1,r),pushup(x);
else T[x].sm=a[l],T[x].v.resize(3),T[x].v[0]=-1e18,T[x].v[1]=p-a[l],T[x].v[2]=1e18;
}
inline int fndps(vector<ll>&v,ll w) {return upper_bound(v.begin(),v.end(),w)-v.begin()-1;}
inline ll query(int x,int l,int r,int dl,int dr,ll dc)
{
int md=(l+r)>>1;if(dl<=l&&r<=dr) return dc+T[x].sm-p*fndps(T[x].v,dc);
if(dr<=md) return query(x<<1,l,md,dl,dr,dc);
else if(dl>md) return query(x<<1|1,md+1,r,dl,dr,dc);
else return query(x<<1|1,md+1,r,dl,dr,query(x<<1,l,md,dl,dr,dc));
}
int main()
{
read(n,q,p);for(int i=1;i<=n;i++) read(a[i]);
build(1,1,n);for(int l,r;q--;) read(l,r),printf("%lld
",query(1,1,n,l,r,0));
return 0;
}