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

· · 题解

想法

线段树的内容大同小异：标记；节点；建树；修改；查询。

而标记的定义与区间修改呈一一对应。

考虑封装一个操作结构体，以及修改单节点函数，将标记下传和节点修改联合起来。

思路清晰，代码简单。

实现

标记

struct Mark{                //操作结构体
    LL a,b;                 //乘数，加数
    Mark(LL a,LL b):        //构造函数
        a(a),   b(b){}  
}non=Mark(1,0);             //空标记
bool operator ==(const Mark x,const Mark y){
    return x.a==y.a&&x.b==y.b;
}

节点

struct Node{
    int l,r,len;        //区间左右端点、长度
    LL sum;             //区间和
    Mark tag;           //标记
    Node *lc,*rc;       //子区间指针
}res[400003],*rt;       //资源栈，根指针
    int ressum;         //资源栈指针

前置函数

合并区间
void merge(Node L,Node R,Node &T){
    T.sum=(L.sum+R.sum)%p;              //注意取模
}
修改节点
讨论本题区间信息的修改方式

当区间[l,r]每个数乘上M，再加上A时，有

\sum_{i=l}^{r}(Ma_{i}+A)=M\sum_{i=l}^{r}a_{i}+A(r-l+1)
讨论本题标记的叠加方式

当某个数x原本乘上M，加上A，现在再乘上M'，再加上A'时，有

M'(Mx+A)+A'=M'Mx+M'A+A' 
void f(Node &rt,Mark opt){              //节点引用；操作结构体
    if(opt==non)
        return ;                        //无效操作
    rt.sum=( ( rt.sum*opt.a )%p
            +( rt.len*opt.b )%p )%p;    //修改区间信息
    Mark tmp=rt.tag;
    rt.tag.a=(tmp.a*opt.a)%p;
    rt.tag.b=( (opt.a*tmp.b)%p
              + opt.b )%p;              //标记叠加
}
标记下传
void spread(Node &rt){      //节点引用
    f(*(rt.lc),rt.tag);     //修改左子区间
    f(*(rt.rc),rt.tag);     //修改右子区间
    rt.tag=non;             //父节点标记清空

建树

void build(Node &rt,int l,int r){   //节点引用
    rt.l=l; rt.r=r;
    rt.tag=non; rt.len=r-l+1;       //基本信息赋值
    if(l==r){                       //叶子节点
        rt.sum=a[l];                //叶子信息初始化
        return ;
    }
    rt.lc=&res[++ressum];
    rt.rc=&res[++ressum];
    int mid=(l+r)>>1;
    build(*(rt.lc),l,       mid);   //递归初始化左子区间
    build(*(rt.rc),mid+1,   r);     //递归初始化右子区间
    merge(*(rt.lc),*(rt.rc),rt);    //信息合并
}

修改

void fupd(Node &rt,int l,int r,Mark opt){   
                                //节点引用；更新区间；操作结构体
    if(l<=rt.l&&rt.r<=r){       //当前节点全包于更新区间
        f(rt,opt);              //直接修改节点
        return ;
    }                           //更新区间不全包当前节点
    spread(rt);                 //标记下传
    int mid=(rt.l+rt.r)>>1;
    if(l<=mid)
        fupd(*(rt.lc),l,r,opt); //递归修改左子节点
    if(r>mid)
        fupd(*(rt.rc),l,r,opt); //递归修改右子节点
    merge(*(rt.lc),*(rt.rc),rt);    //子节点信息合并
}

查询

Node fqry(Node &rt,int l,int r){    //节点引用；询问区间
    if(r<rt.l||rt.r<l)              //越界询问
        return res[ressum+1];       //返回空值
    if(l<=rt.l&&rt.r<=r)            //当前节点全包于询问区间
        return rt;                  //直接返回
                                    //询问区间不全包当前节点
    spread(rt);                     //标记下传
    int mid=(rt.l+rt.r)>>1;
    if(r<=mid)                      //询问区间全包于左子区间
        return fqry(*(rt.lc),l,r);  //递归查询左子区间
    if(l>mid)                       //询问区间全包于右子区间
        return fqry(*(rt.rc),l,r);  //递归查询右子区间
    Node L,R,T;                     //询问区间横跨
    L=fqry(*(rt.lc),l,r);           //递归查询左子区间
    R=fqry(*(rt.rc),l,r);           //递归查询右子区间
    merge(L,R,T);                   //询问区间信息合并
    return T;
}

主程序

int main(){
    scanf("%d%d%lld",&n,&m,&p);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);                    //读入
    rt=&res[1]; ressum=1;
    build(*rt,1,n);                             //建树
    int typ,l,r;
    LL k;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&typ,&l,&r);
        if(typ==3)
            printf("%lld\n",fqry(*rt,l,r).sum); //询问
        else {
            scanf("%lld",&k);                   //修改
            if(typ==1)
                fupd(*rt,l,r,Mark(k,0));    //乘上k再加上0
            else 
            if(typ==2)
                fupd(*rt,l,r,Mark(1,k));    //乘上1再加上k
        }
    }
    return 0;
}