BZOJ1798: [Ahoi2009]Seq 维护序列seq【线段树】

【题目描述】

传送门

【题解】

其实可以看成一个多项式,例如:(x1 * x2+x3) * x4+x5,拆开得到x1 * x2 * x4+x3 * x4+x5
对于L到R都乘上x就变成(a[L]+a[L+1]+...+a[R]) * x,所以PushDown的写法就出来了。
Add[son]=Add[son] * Mul[fa]+Add[fa];
Mul[son]=Mul[son] * mul[fa];
Tre[son]=Tre[fa] * Mul[fa]+Add[fa] * Len;

代码如下

#include<cstdio>
using namespace std;
typedef long long LL;
const int MAXN=1e5+5;
int n,m,P,a[MAXN];
LL Tre[MAXN<<2],Add[MAXN<<2],Mul[MAXN<<2];
#include<cctype>
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;
    return f?ret:-ret;
}
void PushDown(int rt,int Ln,int Rn){
    Add[rt<<1]=(Add[rt<<1]*Mul[rt]%P+Add[rt])%P;
    Add[rt<<1|1]=(Add[rt<<1|1]*Mul[rt]%P+Add[rt])%P;
    Mul[rt<<1]=(Mul[rt<<1]*Mul[rt])%P;
    Mul[rt<<1|1]=(Mul[rt<<1|1]*Mul[rt])%P;
    Tre[rt<<1]=(Tre[rt<<1]*Mul[rt]%P+Add[rt]*Ln%P)%P;
    Tre[rt<<1|1]=(Tre[rt<<1|1]*Mul[rt]%P+Add[rt]*Rn%P)%P;
    Add[rt]=0,Mul[rt]=1;
}
void MO(LL &x){x%=P;}
void PushUp(int rt){MO(Tre[rt]=Tre[rt<<1]+Tre[rt<<1|1]);}
void Build(int rt,int L,int R){
    Add[rt]=0,Mul[rt]=1;
    if(L==R){Tre[rt]=a[L];return;}
    int mid=(L+R)>>1;
    Build(rt<<1,L,mid),Build(rt<<1|1,mid+1,R);
    PushUp(rt);
}
void InsertAdd(int rt,int L,int R,int l,int r,int x){
    if(l<=L&&R<=r){MO(Tre[rt]+=(LL)x*(R-L+1)),MO(Add[rt]+=x);return;}
    int mid=(R+L)>>1;PushDown(rt,mid-L+1,R-mid);
    if(l<=mid) InsertAdd(rt<<1,L,mid,l,r,x);
    if(mid<r) InsertAdd(rt<<1|1,mid+1,R,l,r,x);
    PushUp(rt);
}
void InsertMul(int rt,int L,int R,int l,int r,int x){
    if(l<=L&&R<=r){MO(Tre[rt]*=x),MO(Add[rt]*=x),MO(Mul[rt]*=x);return;}
    int mid=(R+L)>>1;PushDown(rt,mid-L+1,R-mid);
    if(l<=mid) InsertMul(rt<<1,L,mid,l,r,x);
    if(mid<r) InsertMul(rt<<1|1,mid+1,R,l,r,x);
    PushUp(rt);
}
LL Query(int rt,int L,int R,int l,int r){
    if(l<=L&&R<=r) return Tre[rt];
    int mid=(R+L)>>1;LL Sum=0;PushDown(rt,mid-L+1,R-mid);
    if(l<=mid) MO(Sum+=Query(rt<<1,L,mid,l,r));
    if(mid<r) MO(Sum+=Query(rt<<1|1,mid+1,R,l,r));
    return Sum;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    n=read(),P=read();
    for(int i=1;i<=n;i++) a[i]=read();
    m=read();Build(1,1,n);
    for(int i=1;i<=m;i++){
        int typ=read(),L=read(),R=read(),x;
        if(typ==1) InsertMul(1,1,n,L,R,read());else
        if(typ==2) InsertAdd(1,1,n,L,R,read());else printf("%lld\n",Query(1,1,n,L,R));
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部