Description

给出一个长度为n的序列a和一个整数p

有m组询问，每组询问给出一个区间\([l,r]\)

你需要给出下面这个过程的结果

ans = 0 for i from l to r{    ans = ans + a[i]    if ans > p then ans = ans - p;}return ans

\(n\leq 10^6\)

\(m<=2\times10^5\)

\(p\leq10^9\)

\(-10^9\leq a_i\leq10^9\)

Solution

显然一个区间内至多只会减区间长度次p

也就是说如果我们设一个函数\(f(x)\)为初始为x，经过区间\([l,r]\)后的答案，那么\(f(x)\)显然由\(r-l+2\)段斜率为1的一次函数构成，且相邻两段之间截距差为p

更进一步的，可以发现每一段的长度是\(O(p)\)的

那么我们可以考虑用线段树维护函数，对于每个线段树区间记下每段的端点，查询很简单，直接从0开始加上这一段的贡献，并在下一个区间中二分属于那一段即可。

关键是建树

考虑左子区间和右子区间已经建好，考虑将它们合并，实际上就是一个函数复合的过程。

具体实现来说，枚举左子区间的所有段，计算出相应的值域区间，然后右边用一个指针找合法的右段。

由于每一段的长度均为\(O(p)\)，因此每次指针动的位置数是常数级的。

总的时间复杂度为\(O(n\log n+m\log^2 n)\)

可以参考程序。

Code

//Copyright Reserved by BAJim_H#include 
    
     #define fo(i,a,b) for(int i=a;i<=b;++i)#define fod(i,a,b) for(int i=a;i>=b;--i)typedef long long LL;const int N=2000005;const LL INF=(LL)1e16;using namespace std;vector
     
       f[N];int t[N][2],d[200],a[N],n,n1,mo,q;LL sm[N];template 
      
       void read(I &x){    x=0;char ch=getchar();I v=1;    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();    if(ch=='-') v=-1,ch=getchar();    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    x=x*v;}void build(int k,int l,int r){    if(l==r) {f[k].push_back(-INF),f[k].push_back(mo-a[l]);sm[k]=a[l];return;}    int mid=(l+r)>>1;    t[k][0]=++n1,build(t[k][0],l,mid);    t[k][1]=++n1,build(t[k][1],mid+1,r);    int x=t[k][0],y=t[k][1],rx=f[x].size(),ry=f[y].size();    f[k].resize(rx+ry-1,INF);           for(int i=0,j=0;i
       
        0&&f[y][j]>yl) j--;        while(j
        
         <=yl) j++;        if(j) j--;        while(j
         
          <=yr) f[k][i+j]=min(f[k][i+j],max(xl,f[y][j]-sm[x]+(LL)i*mo)),j++; } f[k][0]=-INF; sm[k]=sm[t[k][0]]+sm[t[k][1]];}void find(int k,int l,int r,int x,int y){ if(x<=l&&r<=y) {d[++d[0]]=k;return;} int mid=(l+r)>>1; if(x<=mid) find(t[k][0],l,mid,x,y); if(y>mid) find(t[k][1],mid+1,r,x,y);}LL query(int x,int y){ d[0]=0;find(1,1,n,x,y); LL c=0; fo(i,1,d[0]) c+=sm[d[i]]-(LL)mo*(upper_bound(f[d[i]].begin(),f[d[i]].end(),c)-f[d[i]].begin()-1); return c;}int main(){ cin>>n>>q>>mo; fo(i,1,n) read(a[i]); n1=1; build(1,1,n); fo(i,1,q) { int x,y; read(x),read(y); printf("%lld\n",query(x,y)); }}