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

· · 题解

说实话，我觉得线段树的码量比较大，容易出现细节错误，尤其是这个有加也有乘（我就因为把某一个l写成了r而惨烈地wa了好久）

看到题解很多大佬是直接贴代码什么的，因为每个人码风都不太一样看起来会比较晕，我想简单讲讲怎么样让乘法和加法的lazy tag兼容以及一些细节，代码不重要，大佬们已经给出很多了。

  1. 因为乘法实际上可以视为多次的加法，所以lazy tag依然适用。也可以通过乘法分配律来理解：

    sum[l,r]*k=(a[l]+...+a[r])*k

    如何又加又乘呢？ 在这里我定义加法lazy tag为add，乘法为mul，初始化add=0，mul=1

  2. 由于乘的优先级比较高，我们考虑在处理/传递lazy tag的时候要先用mul。因为这样就不会使add影响到优先级较高的mul。 再考虑一个顺序问题：如果先打上mul，那么后面加的标记不会对之前造成影响；如果先打上add，在处理lazy tag的时候是先乘的，就导致加的部分没有一起乘上去。所以，当 打上/乘上 新的mul的时候，要对add进行一个更新，乘以这个mul,这样结果才会正确。所以对mul进行操作的时候也要一并更新add

p3372线段树1理解及代码

//更新部分代码，除了关键部分和取模几乎和线段树1都是一样的
const int maxn=10000+10;
int a[maxn];
struct SegmentTree
{
    int l,r;//左右端点
    int L,R;//左右儿子
    ll dat,mul,add;//存储的数据、乘的标记、加的标记
    #define l(x) b[x].l
    #define r(x) b[x].r
    #define L(x) b[x].L
    #define R(x) b[x].R
    #define dat(x) b[x].dat
    #define mul(x) b[x].mul
    #define add(x) b[x].add
    SegmentTree(){mul=1;add=0;}
}b[maxn*4];
//此处省略初始化函数
void spread(int pos)//先看下面的函数
{
    if (mul(pos)!=1)
    {
        dat(L(pos))=(dat(L(pos))*mul(pos))%p;
        dat(R(pos))=(dat(R(pos))*mul(pos))%p;
        mul(L(pos))=(mul(L(pos))*mul(pos))%p;
        mul(R(pos))=(mul(R(pos))*mul(pos))%p;
        mul(pos)=1;
    }
    //关键：更新add
    if (add(pos))//这部分由于要取模有点乱，实际上跟普通线段树一样，只是加了个取模，可以不看
    {
        dat(L(pos))=(dat(L(pos))+add(pos)*(r(L(pos))-l(R(pos))+1))%p;
        dat(R(pos))=(dat(R(pos))+add(pos)*(r(R(pos))-l(R(pos))+1))%p;
        add(L(pos))=(add(L(pos))+add(pos))%p;
        add(R(pos))=(add(R(pos))+add(pos))%p;
        add(pos)=0;
    }
}
void change(int pos,int l,int r,ll val,int opt)
{
    if (l<=l(pos)&&r(pos)<=r)//如果处在被修改的区间中就进入修改
    {
        if (opt==1)//修改mul
        {
            add(pos)*=val;
            dat(pos)*=val;
            mul(pos)*=val;
            add(pos)%=p;
            dat(pos)%=p;
            mul(pos)%=p;
        }//关键：更新add（如果前面没有add也不影响，依然是0）
        else//修改add
        {
            add(pos)+=val;
            dat(pos)+=val*(r(pos)-l(pos)+1);
            add(pos)%=p;
            dat(pos)%=p;
        }
        return ;
    }
    spread(pos);
    int mid=(l(pos)+r(pos))>>1;
    if (l<=mid)
        change(L(pos), l, r, val, opt);
    if (r>mid)
        change(R(pos), l, r, val, opt);
    dat(pos)=(dat(L(pos))+dat(R(pos)))%p;
}