题目
题目链接：https://www.luogu.com.cn/problem/P5609
双倍经验：http://codeforces.com/problemset/problem/1172/F
Nauuo 是一个喜欢编程的女孩子。有一天她在做一道题，要求计算一些数的和对一个数 (p) 取模的结果。
她写出了如下的代码，然后获得了 WA 的评测结果。
她很快发现了 bug——ModAdd 函数只对 ([0,p)) 中的数起作用，但是这个问题中的数有可能不在这个范围之内。她对这个错误的函数很好奇，所以她想知道它的运行结果。
然而，原来的代码运行得太慢了，所以她来找你求助。
给定数组 (a_1,a_2,…a_n) 和一个数 (p)，有 (m) 个询问，每次给定两个数 (l) 和 (r)，你需要计算函数 Sum(a,l,r,p) 的返回值。函数 Sum 的定义在上面的伪代码中已经给出。
注意，在上面的代码中，整数不会越界。
(nleq 10^6;mleq 2 imes 10^5;-10^9leq a_i,pleq 10^9)。
思路
同 CF1172F。
维护一棵线段树，区间 ([l,r]) 记一个范围为 ([0,r-l+1]) 的数组 (a)，其中 (a_i) 表示在经过这个区间后，如果要减去 (i) 个 (p)，那么进来的数至少是多少。
总的空间是 (O(n)) 的，考虑怎么维护这个东西。
注：下文 (a_i) 为左子树的，(a_j) 为右子树的，(a_{i+j}) 为当前区间 ([l,r]) 的。
对于左子树中的 (a_i)，它能和右子树的 (a_j) 合并，当且仅当 (a_{i+1}-1) 经过左边的区间后 (geq a_j)，也就是 (a_{i+1}-1+ ext{sum}_{lc}-ipgeq a_j)。
对于一组可以合并的 (i,j)，它们对区间 ([l,r]) 的贡献是 (a_{i+j}=min(a_{i+j},max(a_i,a_j+ip- ext{sum}_{lc})))。因为并不是 ([a_i,a_{i+1})) 中所有数都可以和 (a_j) 合并，而 (max) 后面那部分就是计算进入左子树前至少需要多大才可以进入右子树。
具体如何合并的话，考虑一个 (a_j)，它能和满足 (a_{i+1}-1+ ext{sum}_{lc}-ipgeq a_j) 的 (i) 合并，显然 (i) 越小越优。所以我们只需要对于每一个 (a_j) 求出对应的 (a_i)。
猜测随着 (j) 的增大，(i) 是单调不减的。那么只需要证明 (a_{i+1}-1+ ext{sum}_{lc}-ip) 是单调不减的，即 (a_{i+1}-a_igeq p)。
因为我们已经保证了 (a_i) 是最小的可以减 (i) 次 (p) 的数字，所以在 (a_i) 经过左子树的时候一定存在一个时刻为 (0)，否则一定可以再减小。所以如果想再多减去一个 (p)，原来进来的数就至少需要再增加 (p)。
于是就可以直接双指针扫一下来合并了。建线段树的复杂度即为 (O(nlog n))。
对于一个询问，直接拆成 (O(log n)) 个区间，每次在区间内二分即可。
时间复杂度 (O(nlog n+mlog^2 n))。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000010;
const ll Inf=1e18;
int n,m,p,b[N];
ll ans;
struct SegTree
{
ll sum[N*4];
vector<ll> a[N*4];
void pushup(int x)
{
sum[x]=sum[x*2]+sum[x*2+1];
for (int i=0,j=0;i<a[x*2].size();i++)
{
if (j) j--;
for (;j<a[x*2+1].size();j++)
{
if (a[x*2][i+1]-1+sum[x*2]-1LL*i*p<a[x*2+1][j]) break;
a[x][i+j]=min(a[x][i+j],max(a[x*2][i],a[x*2+1][j]+1LL*i*p-sum[x*2]));
}
}
}
void build(int x,int l,int r)
{
a[x].push_back(-Inf);
for (int i=1;i<=r-l+2;i++)
a[x].push_back(Inf);
if (l==r)
{
sum[x]=b[l]; a[x][1]=p-b[l];
return;
}
int mid=(l+r)>>1;
build(x*2,l,mid); build(x*2+1,mid+1,r);
pushup(x);
}
void query(int x,int l,int r,int ql,int qr)
{
if (ql<=l && qr>=r)
{
int k=upper_bound(a[x].begin(),a[x].end(),ans)-a[x].begin()-1;
ans=ans+sum[x]-1LL*k*p;
return;
}
int mid=(l+r)>>1;
if (ql<=mid) query(x*2,l,mid,ql,qr);
if (qr>mid) query(x*2+1,mid+1,r,ql,qr);
}
}seg;
int main()
{
// freopen("data.txt","r",stdin);
scanf("%d%d%d",&n,&m,&p);
for (int i=1;i<=n;i++) scanf("%d",&b[i]);
seg.build(1,1,n);
while (m--)
{
int l,r; ans=0;
scanf("%d%d",&l,&r);
seg.query(1,1,n,l,r);
printf("%lld
",ans);
}
return 0;
}