线段树相关-阿里云开发者社区

开发者社区> 开发与运维> 正文

线段树相关

简介: 模板链接: 支持区间加减,乘。询问区间和。 要注意的几点: 1.输出格式!!!! 2.$printf("")$语法要写对,不然的话能过编辑,半天调不出来。 3.位运算的时候$>>1$和$

模板链接:

支持区间加减,乘。询问区间和。

要注意的几点:

1.输出格式!!!!

2.$printf("")$语法要写对,不然的话能过编辑,半天调不出来。

3.位运算的时候$>>1$和$<<1$和$<<1|1$分清……

4.将什么$val[p]+=……,val[p]%=mod$ 要写到一句的时候,一定要记得$val[p]=val[p]+……$,不是$val[p]=……$

好了,这$4$点调了一上午$……$

代码奉上

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int mod;
struct linetree{
    long long val[400010];
    long long lazyp[400010];
    long long lazym[400010];
    inline void update(int p,int l,int r)
    {
        val[p]=(val[p]*lazym[p])%mod,
        val[p]=(val[p]+(r-l)*lazyp[p])%mod;
        return ;
    }
    inline void pushdown(int p,int l,int r)
    {
        update(p,l,r);
        if(r-l>1)
        {
            lazyp[p<<1]=(lazyp[p<<1]*lazym[p]+lazyp[p])%mod,
            lazym[p<<1]=(lazym[p<<1]*lazym[p])%mod;
            lazyp[p<<1|1]=(lazyp[p<<1|1]*lazym[p]+lazyp[p])%mod,
            lazym[p<<1|1]=(lazym[p<<1|1]*lazym[p])%mod;            
        }lazyp[p]=0,lazym[p]=1;

        return ;
    }
    inline int build(int p,int l,int r)
    {
        lazym[p]=1;
        if(r-l==1) {scanf("%lld",&val[p]),val[p]%=mod;return val[p];}
        int mid=l+r>>1;
        if(mid>l) val[p]=(val[p]+build(p<<1,l,mid))%mod;
        if(mid<r) val[p]=(val[p]+build(p<<1|1,mid,r))%mod;
        return val[p];
    }
    void setpluse(int p,int l,int r,int dl,int dr,long long pluse)
    {
        if(lazyp[p]!=0||lazym[p]!=1) pushdown(p,l,r);
        if(l==dl&&r==dr){lazyp[p]=(lazyp[p]+pluse)%mod,pushdown(p,l,r);return ;}
        int mid=l+r>>1;
        if(mid>dl) setpluse(p<<1,l,mid,dl,min(mid,dr),pluse);else pushdown(p<<1,l,mid);
        if(mid<dr) setpluse(p<<1|1,mid,r,max(dl,mid),dr,pluse);else pushdown(p<<1|1,mid,r);
        val[p]=val[p<<1]+val[p<<1|1];
        return ;
    }
    void setmulty(int p,int l,int r,int dl,int dr,long long multy)
    {
        if(lazyp[p]!=0||lazym[p]!=1) pushdown(p,l,r);
        if(l==dl&&r==dr)
        {lazyp[p]=(lazyp[p]*multy)%mod,lazym[p]=(lazym[p]*multy)%mod,pushdown(p,l,r);return ;}
        int mid=l+r>>1;
        if(mid>dl) setmulty(p<<1,l,mid,dl,min(mid,dr),multy);else pushdown(p<<1,l,mid);
        if(mid<dr) setmulty(p<<1|1,mid,r,max(dl,mid),dr,multy);else pushdown(p<<1|1,mid,r);
        val[p]=(val[p<<1]+val[p<<1|1])%mod;
        return ;
    }
    int sum(int p,int l,int r,int dl,int dr)
    {
        if(lazyp[p]!=0||lazym[p]!=1) pushdown(p,l,r);
        if(l==dl&&r==dr) return val[p];
        int mid=l+r>>1;int res=0;
        if(mid>dl) res+=sum(p<<1,l,mid,dl,min(dr,mid));
        if(mid<dr) res+=sum(p<<1|1,mid,r,max(dl,mid),dr);
        res%=mod;
        return res;
    }

}lt;
int n,m,t;
int u,v,opt;
signed main()
{
    scanf("%d%d%d",&n,&m,&mod);
    lt.build(1,0,n);
    for(int i=1;i<=m;i++)
    {

        scanf("%d%d%d",&opt,&u,&v);
        if(opt==1) {scanf("%d",&t);lt.setmulty(1,0,n,u-1,v,t);}
        if(opt==2) {scanf("%d",&t);lt.setpluse(1,0,n,u-1,v,t);}
        if(opt==3) {printf("%d\n",lt.sum(1,0,n,u-1,v));}
    }
    return 0;
}

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章