[线段树][多标记][欧拉降幂] ZOJ 3998 Yet Another Data Structure Problem

题目链接

题意：

给一个长度1e5的序列，两种操作：操作1 把区间内元素都乘以一个v，操作2：把区间内元素都变为原来的k次方

然后有1e5个询问，问 $[l,r]$ 之间的区间积

题解：

线段树上双标记问题。维护两个 $lazy tag$ ，一个负责次幂一个负责乘，其实相当一个加法和一个乘法然后求区间和。我这里维护的思路是每次都保证维护的点是一个 $k*(a_l a_{l+1}… a_{r} )^w$ 这样一种形式。这样的话每次标记下传的时候，先把w的次幂传下去，注意这时候儿子的k也要变成 $k_{son}^w$ ,然后再把k传下去，即给儿子的 $k_{son}$ 再乘上 $k$ ，这两个顺序搞清楚之后就很好写了。

wa点是，维护$w$次幂对质数取模的时候不能写 $\%mod$ ，而应该用欧拉定理降幂， $\%(mod-1)$ 貌似我因为这个错过很多次了听说用BSGS预处理的话会更快不过我没试过emmm

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;

typedef long long ll;
const int mod=1e9+7;
const int maxn = 2e5+5;

ll pws[maxn<<2],vs[maxn<<2],mus[maxn<<2];

ll qpow(ll a,ll b){
    ll res=1;
    a%=mod;
    while(b){
        if(b&1){
            //res=(res*a)%mod;
            res*=a;
            res=(res>=mod?res%mod:res);
        }
        //a=(a*a)%mod;
        a=a*a;
        a=(a>=mod?a%mod:a);
        b>>=1;
    }
    return res;
}

void build(int o,int l,int r){
    if(l==r){
        scanf("%lld",&mus[o]);
        vs[o]=1;
        pws[o]=1;
        return ;
    }
    int mid=((l+r)>>1);
    vs[o]=pws[o]=1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    mus[o]=(mus[o<<1]*mus[o<<1|1])%mod;
}

//k*m^w
void pushdown(int o,int l,int r){
    if(pws[o]!=1){
        pws[o<<1]=(pws[o<<1]*pws[o])%(mod-1);
        pws[o<<1|1]=(pws[o<<1|1]*pws[o])%(mod-1);
        vs[o<<1]=qpow(vs[o<<1],pws[o]);
        vs[o<<1|1]=qpow(vs[o<<1|1],pws[o]);
        mus[o<<1]=qpow(mus[o<<1],pws[o]);
        mus[o<<1|1]=qpow(mus[o<<1|1],pws[o]);
        pws[o]=1;
    }
    if(vs[o]!=1){
        int mid=(l+r)>>1;
        vs[o<<1]=(vs[o<<1]*vs[o])%mod;
        vs[o<<1|1]=(vs[o<<1|1]*vs[o])%mod;
        mus[o<<1]=(mus[o<<1]*qpow(vs[o],mid-l+1))%mod;
        mus[o<<1|1]=(mus[o<<1|1]*qpow(vs[o],r-mid))%mod;
        vs[o]=1;
    }
}

void pushup(int o){
    mus[o]=(mus[o<<1]*mus[o<<1|1])%mod;
}

ll op,val,pl,pr;
void update(int o,int l,int r){
    if(pl<=l&&r<=pr){
        if(op==1){
            vs[o]=(vs[o]*val)%mod;
            mus[o]=(mus[o]*qpow(val,r-l+1))%mod;
        }
        else{
            vs[o]=qpow(vs[o],val);
            pws[o]=(pws[o]*val)%(mod-1);
            mus[o]=qpow(mus[o],val);
        }
        return ;
    }
    pushdown(o,l,r);
    int mid=(l+r)>>1;
    if(pl<=mid) update(o<<1,l,mid);
    if(mid<pr) update(o<<1|1,mid+1,r);
    pushup(o);
}


ll query(int o,int l,int r){
    if(pl<=l&&r<=pr){
        return mus[o];
    }
    int mid=(l+r)>>1;
    pushdown(o,l,r);
    ll res=1;
    if(pl<=mid) res=(res*query(o<<1,l,mid))%mod;
    if(mid<pr)  res=(res*query(o<<1|1,mid+1,r))%mod;
    return res;
}

int main() {
    // freopen("test_.in","r",stdin);
    // freopen("2.txt","w",stdout);
	int T,n,q;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&q);
        build(1,1,n);
        while(q--){
            scanf("%lld%lld%lld",&op,&pl,&pr);
            if(op==3){
                printf("%lld\n",query(1,1,n));
            }
            else{
                scanf("%lld",&val);
                update(1,1,n);
            }
        }
    }
	return 0;
}
/*

*/