题解 P3373 【【模板】线段树 2】

· · 题解

这题有两种更新操作，所以下传标记可以设两个，一个加法，一个乘法，根据乘法分配率，可以得出（自己证明或者看楼下）：

（1）当某段区间乘一个数时，两个下传标记都要乘这个数

（2）当某段区间加一个数时，加法下传标记加上这个数

下传时，应该先乘再加。

好像很容易的样子，结果我一开始总是30分，查了半天发现初始化搞错了。

接着一直70分，弄了半天还是WA 3个点，估计我是为数不多的只WA 最后3个点的。

后来一生气，把下传操作的条件删了，就...过了。。。

猛然想起有可能乘一个负数或0，还有可能加负数或0

唉，只能说我太弱了

附代码

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
long long n,m,mod,a,x,y,k,s[100002];
typedef struct{
    long long g,fc,fj;
}P;
P p[400002];
void pushdown(int root,int begin,int end,int mid){
    p[root*2].g*=p[root].fc;p[root*2+1].g*=p[root].fc;
    p[root*2].g+=p[root].fj*(mid-begin+1);p[root*2+1].g+=p[root].fj*(end-mid);
    p[root*2].fc*=p[root].fc;p[root*2+1].fc*=p[root].fc;
    p[root*2].fj*=p[root].fc;p[root*2+1].fj*=p[root].fc;
    p[root*2].fj+=p[root].fj;p[root*2+1].fj+=p[root].fj;
    p[root].fc=1;p[root].fj=0;
    p[root*2].g%=mod;p[root*2].fc%=mod;p[root*2].fj%=mod;
    p[root*2+1].g%=mod;p[root*2+1].fc%=mod;p[root*2+1].fj%=mod;
}
void gengxinc(int root,int begin,int end,int begin2,int end2,long long z){
    if (begin>end2 || end<begin2)return;
    if (begin>=begin2 && end<=end2)
    {
        p[root].g=p[root].g*z%mod;
        p[root].fc=p[root].fc*z%mod;
        p[root].fj=p[root].fj*z%mod;
        return;
    }
    int mid=(begin+end)/2;pushdown(root,begin,end,mid);
    gengxinc(root*2,begin,mid,begin2,end2,z);
    gengxinc(root*2+1,mid+1,end,begin2,end2,z);
    p[root].g=(p[root*2].g+p[root*2+1].g)%mod;
}
void gengxinj(int root,int begin,int end,int begin2,int end2,long long z){
    if (begin>end2 || end<begin2)return;
    if (begin>=begin2 && end<=end2)
    {
        p[root].g=(p[root].g+z*(end-begin+1))%mod;
        p[root].fj=(p[root].fj+z)%mod;
        return;
    }
    int mid=(begin+end)/2;pushdown(root,begin,end,mid);
    gengxinj(root*2,begin,mid,begin2,end2,z);
    gengxinj(root*2+1,mid+1,end,begin2,end2,z);
    p[root].g=(p[root*2].g+p[root*2+1].g)%mod;
}
long long query(int root,int begin,int end,int begin2,int end2){
    if (begin>end2 || end<begin2)return 0;
    if (begin>=begin2 && end<=end2)return p[root].g;
    int mid=(begin+end)/2;pushdown(root,begin,end,mid);
    return (query(root*2,begin,mid,begin2,end2)+query(root*2+1,mid+1,end,begin2,end2))%mod;
}
void csh(int root,int begin,int end){
    p[root].fc=1;p[root].fj=0;
    if (begin==end)
    {
        p[root].g=s[begin];
        return;
    }
    int mid=(begin+end)/2;
    csh(root*2,begin,mid);csh(root*2+1,mid+1,end);
    p[root].g=p[root*2].g+p[root*2+1].g;
}
int main()
{
    scanf("%lld%lld%lld",&n,&m,&mod);
    for (int i=1;i<=n;i++)
    scanf("%lld",&s[i]);
    csh(1,1,n);
    for (int i=0;i<m;i++)
    {
        scanf("%lld%lld%lld",&a,&x,&y);
        if (a==1)
        {
            scanf("%lld",&k);
            gengxinc(1,1,n,x,y,k);
        }
        else if (a==2)
        {
            scanf("%lld",&k);
            gengxinj(1,1,n,x,y,k);
        }
        else printf("%lld\n",query(1,1,n,x,y));
    }
    return 0;
}