线段树的板子

shadowice1984 · 2018-04-04 20:50:02 · 个人记录

这里是shadowice自用的板子

然后会有一些毒瘤压行的行为方便考试的时候自己写，就酱。

tips:请采用假标记写法，处理多关键标记的时候非常好使，这里以区间加区间乘为参考

#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e5+10;typedef long long ll;const ll mod=1e9+7;
struct linetree
{
    ll val[4*N];ll add[4*N];ll mult[4*N];
    inline void pushdown(int p)
    {
        add[p<<1]=(add[p]*mult[p]+add[p<<1])%mod;
        add[p<<1|1]=(add[p]*mult[p]+add[p<<1|1])%mod;
        mult[p<<1]=mult[p<<1]*mult[p]%mod;
        mult[p<<1|1]=mult[p<<1|1]*mult[p]%mod;
        val[p<<1]=(val[p<<1]*mult[p]+add[p])%mod;
        val[p<<1|1]=(val[p<<1|1]*mult[p]+add[p])%mod;
    }
    inline void setadd(int p,int l,int r,int dl,int dr,ll plus)
    {
        if(dl==l&&dr==r){val[p]=(val[p]+plus)%mod;add[p]=(add[p]+plus)%mod;return;}
        int mid=(l+r)/2;pushdown(p);
        if(dl<mid){setadd(p<<1,l,mid,dl,min(dr,mid),plus);}
        if(mid<dr){setadd(p<<1|1,mid,r,max(dl,mid),dr,plus);}
        val[p]=(val[p<<1]+val[p<<1|1])%mod;
    }
    inline void setmul(int p,int l,int r,int dl,int dr,ll mul)
    {
        if(dl==l&&dr==r){val[p]=val[p]*mul%mod;mult[p]=mult[p]*mul%mod;return;}
        int mid=(l+r)/2;pushdown(p);
        if(dl<mid){setmul(p<<1,l,mid,dl,min(dr,mid),mul);}
        if(mid<dr){setmul(p<<1|1,mid,r,max(dl,mid),dr,mul);}
        val[p]=(val[p<<1]+val[p<<1|1])%mod;
    }
    inline ll sum(int p,int l,int r,int dl,int dr)
    {
        if(dl==l&&dr==r){return val[p];}int mid=(l+r)/2;pushdown(p);ll res=0;
        if(dl<mid){res=(res+sum(p<<1,l,mid,dl,min(dr,mid)))%mod;}
        if(mid<dr){res=(res+sum(p<<1|1,mid,r,max(dl,mid),dr))%mod;}
        return res;
    }
    inline void build(int p,int l,int r)
    {
        mul[p]=1;if(r-l==1){scanf("%lld",&val[p]);return;}int mid=(l+r)/2;
        build(p<<1,l,mid);build(p<<1|1,mid,r);val[p]=(val[p<<1]+val[p<<1|1])%mod;
    }
}lt;