前言

我好菜。

Solution

对偶数位置的 $a_i$ 取反，因为贡献为负。

首先是贪心，我们从前往后遍历，当遍历到的区间的最大子段和 $\ge k$ 时，我们应该切一刀。现在考虑维护这一过程，先形式化以上过程：从前往后枚举 $i$，设 $s$ 为以 $i$ 结尾的最大子段和，$ans$ 为当前答案，更新如下：

意思是更新最大子段和，并切下尽量多的 $k$ 丢到答案中。观察这一过程，我们发现，若 $s$ 始终不为负，那么变化是好算的。设过程中 $\sum a_i=sum$，那么

关键在于 $s<0$ 的情况，但这时 $s$ 会取 $\max$ 到 $0$，再继续往后遍历。这可以视作重新开始，于是将整个过程分为若干段，每段从 $s=0$ 开始，一直到 $s<0$ 结束，然后重置 $s=0$，开启下一段。

若我们将每走一段看做“跳”，那么从任意点开始“跳”的路径是确定的，所以倍增预处理出来，查询时倍增跳即可。预处理的方法：列出式子，用颜色均摊或线段树维护，时间复杂度 $O(n\log n)$。

代码

这里使用线段树。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
inline LL read()
{
	char c=getchar();
	LL f=1,x=0;
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
	return x*f;
}
inline void print(LL x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
const int N=5e5+5;
int n,m,q,f[N][19];
LL k,a[N],s[N],sum[N],c[N*3],g[N][19];
struct Segment_Tree
{
	int tr[N*3<<2];
	void update(int p,int s,int t,int l,int r,int x)
	{
		if(s>=l&&t<=r){tr[p]=x;return;}
		int mid=(s+t)>>1;
		if(l<=mid) update(p<<1,s,mid,l,r,x);
		if(r>mid) update(p<<1|1,mid+1,t,l,r,x);
	}
	int query(int p,int s,int t,int x)
	{
		int res=tr[p];
		if(!res) res=n+1;
		if(s==t) return res;
		int mid=(s+t)>>1;
		if(x<=mid) return min(res,query(p<<1,s,mid,x));
		return min(res,query(p<<1|1,mid+1,t,x));
	}
}tr;
inline void upd(LL l,LL r,int x)
{
	if(l>r) return;
	l=lower_bound(c+1,c+1+m,l)-c;
	r=lower_bound(c+1,c+1+m,r)-c;
	tr.update(1,1,m,l,r,x);
}
inline LL lca(int l,int r)
{
	int now=l-1;
	LL res=0;
	for(int i=18;i>=0;i--)
		if(f[now][i]<=r) res+=g[now][i],now=f[now][i];
	res+=(sum[r]-sum[now])/k;
	return res;
}
int main()
{
	n=read();
	q=read();
	k=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++)
	{
		if(i&1) s[i]=(s[i-1]+a[i]%k)%k;
		else s[i]=(s[i-1]-a[i]%k+k)%k,a[i]=-a[i];
		sum[i]=sum[i-1]+a[i];
	}
	c[++m]=k-1;
	for(int i=1;i<=n;i++) c[++m]=max(s[i-1],s[i-1]+a[i]+k),c[++m]=s[i-1]+a[i],c[++m]=s[i-1];
	sort(c+1,c+1+m);
	m=unique(c+1,c+1+m)-(c+1);
	for(int i=n;i>=0;i--)
	{
		int o=lower_bound(c+1,c+1+m,s[i])-c;
		f[i][0]=(o>m?n+1:tr.query(1,1,m,o));
		if(!i) break;
		upd(max(s[i-1],s[i-1]+a[i]+k)+1,k-1,i);
		upd(s[i-1]+a[i]+1,s[i-1],i);
	}
	for(int i=0;i<=n;i++) g[i][0]=(sum[f[i][0]-1]-sum[i])/k;
	for(int i=1;i<19;i++)
		for(int j=0;j<=n;j++)
		{
			if(f[j][i-1]>n) f[j][i]=n+1,g[j][i]=g[j][i-1];
			else f[j][i]=f[f[j][i-1]][i-1],g[j][i]=g[j][i-1]+g[f[j][i-1]][i-1];
		}
	while(q--)
	{
		int l,r;
		l=read();
		r=read();
		print(lca(l,r));
		putchar('\n');
	}
	return 0;
}