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

· · 题解

我这个解法的不同之处在于通过指针来访问线段树上的其他节点，感觉这样逻辑会更清晰一点。

还有觉得楼下milkfilling说的不对，考虑加法优先的话应该是tag2（他的add）会出现精度问题，但tag1（他的mul）不会，他正好说反了。

1.我们在【模板1】的基础上考虑在区间上乘x 2.直接想到加一个tag2来表示乘多少 3.考虑你每个node有d,tag1,tag2这三个属性，如何维护该区间的值。

a)先乘再加：想到区间和=dtag1+tag2len（那么我们应该怎样维护tag1和tag2保证其正确性呢），一个非常朴素的想法是每次【乘法修改】tag1=x。但这样是不对的，因为此时你该区间和上乘个x，即区间和=x，应当是（dtag1+tag2len)x，所以修改应该是tag1=x和tag2*=x；对于每次【加法修改】，我们应当不改变tag1，tag2+=x。

b)先加再乘：还有另一种维护区间和的方式即，区间和=(d+tag2len)tag1，这个时候我们思考应该怎样修改tag1,tag2保证其答案正确。对于每次【乘法修改】,tag1=x，tag2不变；对于每次【加法修改】(d+tag2len)tag1+xlen=(d+len(x/tag1+tag2))tag1，即tag2+=x/tag1，tag1不变。

以上是这道题的核心部分，附上代码：

#include<iostream>
#define MAXN 100000 
#define LL long long
using namespace std;

int top;
struct node{
    int l,r;
    LL d,tag1,tag2;//tag1乘，tag2加
    node *ls,*rs;
}pool[4*MAXN];
LL a[MAXN+5],N,M,P; 

node* buildT(int l,int r){
    node* p=pool+(++top);
    if(l==r){
        p->l=p->r=l;
        p->d=a[l]%P;
        p->tag1=1;
        return p;
    }
    p->tag1=1;
    p->l=l; p->r=r;
    p->ls=buildT(l,(l+r)/2); p->rs=buildT((r+l)/2+1,r);
    p->d=(p->ls->d+p->rs->d)%P;
    return p;
}

LL getData(node *p){
    return (p->d*p->tag1%P+p->tag2*(p->r-p->l+1)%P)%P;
}

//pushdown的本质是根据运算的优先级，维护算法正确性
//区域加法在query时pushdown可以因为+3 +5 先加3还是先加5对答案没有区别；但区域乘法在update时就要pushdown因为+3 *5 先后顺序有区别 
void pushdown(node *p){
    if(p->tag1==1 && p->tag2==0) return;
    p->d=getData(p);
    //如果这个时候rs或ls的tag上有值，那么说明这些操作是在p上有操作之前的（因为之前一直有push down）。所以他们享有被tag1乘的权利 
    p->rs->tag1=p->rs->tag1*p->tag1%P;
    p->rs->tag2=(p->rs->tag2*p->tag1%P+p->tag2)%P;

    p->ls->tag1=p->ls->tag1*p->tag1%P;
    p->ls->tag2=((p->ls->tag2*p->tag1)%P+p->tag2)%P;

    p->tag1=1; p->tag2=0;
    return;
}

LL query(node* p,int l,int r){
    if(p->l==l && p->r==r){
        return getData(p);
    }
    pushdown(p);
    int mid=(p->l+p->r)/2;
    if(r<=mid)   return query(p->ls,l,r);
    if(l>mid)    return query(p->rs,l,r);
    return  (query(p->ls,l,mid)+query(p->rs,mid+1,r))%P;  
}

void changePlus(node* p,int l,int r,LL dv){
        if(p->l==l && p->r==r){
            p->tag2=(p->tag2+dv)%P;
            return;
        }
        pushdown(p);
        int mid=(p->l+p->r)/2;
        if(r<=mid) changePlus(p->ls,l,r,dv);
        else if(l>mid) changePlus(p->rs,l,r,dv);
        else{
            changePlus(p->ls,l,mid,dv);
            changePlus(p->rs,mid+1,r,dv);
        }
        p->d=(getData(p->ls)+getData(p->rs))%P;
}

void changeTimes(node* p,int l,int r,LL dv){

        if(p->l==l && p->r==r){
            p->tag1=p->tag1*dv%P;
            p->tag2=p->tag2*dv%P;
            return;
        }
        pushdown(p);
        int mid=(p->l+p->r)/2;
        if(r<=mid) changeTimes(p->ls,l,r,dv);
        else if(l>mid) changeTimes(p->rs,l,r,dv);
        else{
            changeTimes(p->ls,l,mid,dv);
            changeTimes(p->rs,mid+1,r,dv);
        }
        p->d=( getData(p->ls)+getData(p->rs) )%P;
}

int main(){
    cin>>N>>M>>P;
    for(int i=1;i<=N;i++) cin>>a[i];
    node* root=buildT(1,N);

    for(int i=1;i<=M;i++){
        int op,x,y; cin>>op>>x>>y;
        if(op==1){
            LL k; cin>>k;
            changeTimes(root,x,y,k);
        }
        else if(op==2){
            LL k; cin>>k;
            changePlus(root,x,y,k);
        }
        else cout<<query(root,x,y)<<endl;
    }
    return 0;
}