题解 P4635 【[SHOI2011]改进代码】

· · 题解

好题。

首先肯定是尝试硬上线段树......然后发现每次 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！