自动搬运

查看原文

来自洛谷，原作者为

	UnyieldingTrilobite 直到世界 只剩下闪烁的黑白

搬运于2025-08-24 22:02:09，当前版本为作者最后更新于2020-06-05 20:22:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

好题。

首先肯定是尝试硬上线段树......然后发现每次 operate1 对 operate2 统计量的影响不是很好算......

怎么办？

凉拌。

发现 operate1 其实就是正常的区间加，可以尝试思考一下差分（毕竟没啥思路）。

现在问题就来了：区间加是否能够转化为单点加？

仔细想想，有点问题。

因为要取尛，这就会导致中间的差分数组不一定全部不变，可能会乱七八糟= =。

没办法了= =。

换种思路，主要的混乱在于取尛，那如果把取尛扔进差分数组（也就是原数组开始乱变但是差分数组正常，反正不关心原数组了= =），那是不是 operate1 就水掉了？

至少先干掉一个。

再想想，这个差分数组要推回原序列其实也不是很难= =。

也就是前缀和取尛。

那，既然差分数组都是正的，什么样的位置会对 operate2 产生贡献？

也就是前缀和计算到后一个数的结果反而比前一个数大？

也就是一路加过去之后，取尛把它变小了，也就是“溢出”了。

观察到我们可以把 operate2 的区间转化为两个前缀之差。

所以只需要解决一路前缀和加到某个数“溢出”了几次。

好好想想，到这里已经水了，自行思考吧。

没思考出来的可以继续看。

就是不取尛前缀和加到这里，除以 $p$ 下取整的值。

为什么？自行思考，或者画个栗子膜你吧。

嗯到这里就没了= =。

BIT维护，Over.

几个事情：

1. 还是有点懵的建议再理理，或者画画样例，或者找我问，或者换个题解。

2. 怎么想到的？真就玄学呗= =。反正我是拍脑瓜想出来的，这题思路也算是对新手比较不友好（吧？可能我菜）。

最后是代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+9;
int n,m,p;
int bit[N],raw[N];//raw即原差分数组，用来判断单点加该加多少
void update(int pos,int val){
	for(raw[pos]=(raw[pos]+val)%p;pos<=n;pos+=pos&-pos)bit[pos]+=val;
}//点更新
int query(int pos){
	int ret=0;
	while(pos)ret+=bit[pos],pos&=pos-1;
	return ret;
}//前缀和查询
signed main(){
	cin>>n>>m>>p;
	for(int i=1,prv=0,x;i<=n;++i)cin>>x,update(i,(x-prv+p)%p),prv=x;//直接更新差分数组
	for(int num,l,r,c;m;--m){
		cin>>num>>l>>r;
		if(num==1)cin>>c,c%=p,++r,update(l,raw[l]+c>=p?c-p:c),update(r,raw[r]>=c?-c:p-c);//点更新
		else cout<<query(r)/p-query(l)/p<<endl;//前缀和相减
	}
	return 0;
}//Over.

祝大家AC！