维护序列

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2680 字
n个数模P；1tgc区间乘c；2tgc区间加
一本通
练习
正文

/*
原题：一本通 4.3 练习 3 维护序列 (AHOI 2009)
题意：n 个数模 P；1 t g c 区间乘 c；2 t g c 区间加 c；3 t g 询问区间和模 P。
思路：线段树维护区间和，带乘法、加法两个懒标记；下推时先乘后加，所有和与标记都对 P 取模。
复杂度：时间 O((n+M) log n)，空间 O(n)。
易错点：两个标记有顺序（乘要同时作用到 add）；任何中间乘积先 %P 防溢出；P 是给定模数。
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll a[N];
ll sum[N*4];
ll mul[N*4];
ll add[N*4];
int len[N*4];
ll P;
void apply_mul(int node,ll c){
    sum[node]=sum[node]*c%P;
    mul[node]=mul[node]*c%P;
    add[node]=add[node]*c%P;
}
void apply_add(int node,ll c){
    sum[node]=(sum[node]+c*len[node])%P;
    add[node]=(add[node]+c)%P;
}
void pushdown(int node){
    if(mul[node]!=1||add[node]!=0){
        apply_mul(node*2,mul[node]);
        apply_add(node*2,add[node]);
        apply_mul(node*2+1,mul[node]);
        apply_add(node*2+1,add[node]);
        mul[node]=1;
        add[node]=0;
    }
}
void build(int node,int l,int r){
    mul[node]=1;
    add[node]=0;
    len[node]=r-l+1;
    if(l==r){
        sum[node]=a[l]%P;
        return;
    }
    int mid=(l+r)/2;
    build(node*2,l,mid);
    build(node*2+1,mid+1,r);
    sum[node]=(sum[node*2]+sum[node*2+1])%P;
}
void update_mul(int node,int l,int r,int ql,int qr,ll c){
    if(ql<=l&&r<=qr){
        apply_mul(node,c);
        return;
    }
    pushdown(node);
    int mid=(l+r)/2;
    if(ql<=mid){
        update_mul(node*2,l,mid,ql,qr,c);
    }
    if(qr>mid){
        update_mul(node*2+1,mid+1,r,ql,qr,c);
    }
    sum[node]=(sum[node*2]+sum[node*2+1])%P;
}
void update_add(int node,int l,int r,int ql,int qr,ll c){
    if(ql<=l&&r<=qr){
        apply_add(node,c);
        return;
    }
    pushdown(node);
    int mid=(l+r)/2;
    if(ql<=mid){
        update_add(node*2,l,mid,ql,qr,c);
    }
    if(qr>mid){
        update_add(node*2+1,mid+1,r,ql,qr,c);
    }
    sum[node]=(sum[node*2]+sum[node*2+1])%P;
}
ll query(int node,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        return sum[node];
    }
    pushdown(node);
    int mid=(l+r)/2;
    ll res=0;
    if(ql<=mid){
        res=(res+query(node*2,l,mid,ql,qr))%P;
    }
    if(qr>mid){
        res=(res+query(node*2+1,mid+1,r,ql,qr))%P;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n>>P;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    int M;
    cin>>M;
    while(M--){
        int op,t,g;
        cin>>op>>t>>g;
        if(op==1){
            ll c;
            cin>>c;
            update_mul(1,1,n,t,g,c%P);
        }else if(op==2){
            ll c;
            cin>>c;
            update_add(1,1,n,t,g,c%P);
        }else{
            cout<<query(1,1,n,t,g)<<"\n";
        }
    }
    return 0;
}
维护序列

正文

一本通·提高篇的其它内容
