M_sea

洛谷2023 [AHOI2009]维护序列
Luogu算法线段树板子。代码#include <algorithm> #include <io...
扫描右侧二维码阅读全文
13
2017/11

洛谷2023 [AHOI2009]维护序列

Luogu

算法

线段树板子。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
typedef long long LL;
const LL N=100001;
inline LL read() {
    LL X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}
LL a[N];
LL n,m,p;
struct Segment_Tree { //线段树
    LL sumv[N<<2],addv[N<<2],mulv[N<<2];
#define lson (o<<1)
#define rson (o<<1|1)
    inline void pushup(LL o) { sumv[o]=(sumv[lson]+sumv[rson])%p; } //上传信息
    inline void pushdown(LL o,LL l,LL r) { //下放标记
        if (mulv[o]!=1) { //注意要更新的东西
            mulv[lson]*=mulv[o]; mulv[lson]%=p;
            mulv[rson]*=mulv[o]; mulv[rson]%=p;
            addv[lson]*=mulv[o]; addv[lson]%=p;
            addv[rson]*=mulv[o]; addv[rson]%=p;
            sumv[lson]*=mulv[o]; sumv[lson]%=p;
            sumv[rson]*=mulv[o]; sumv[rson]%=p;
            mulv[o]=1;
        }
        if (addv[o]!=0) {
            LL mid=(l+r)>>1;
            addv[lson]+=addv[o]; addv[lson]%=p;
            addv[rson]+=addv[o]; addv[rson]%=p;
            sumv[lson]+=addv[o]*(mid-l+1); sumv[lson]%=p;
            sumv[rson]+=addv[o]*(r - mid); sumv[rson]%=p;
            addv[o]=0;
        }
    }
    inline void build(LL o,LL l,LL r) { //建树
        LL mid=(l+r)>>1; addv[o]=0; mulv[o]=1;
        if (l==r) sumv[o]=a[l]%p;
        else {
            build(lson,l,mid);
            build(rson,mid+1,r);
            pushup(o);
        }
    }
    inline void add(LL o,LL l,LL r,LL ql,LL qr,LL v) { //区间加
        if (ql<=l&&r<=qr) {
            addv[o]+=v; addv[o]%=p;
            sumv[o]+=v*(r-l+1); sumv[o]%=p;
            return;
        }
        pushdown(o,l,r);
        LL mid=(l+r)>>1;
        if (ql<=mid) add(lson,l,mid,ql,qr,v);
        if (qr>mid) add(rson,mid+1,r,ql,qr,v);
        pushup(o);
    }
    inline void multi(LL o,LL l,LL r,LL ql,LL qr,LL v) { //区间乘
        if (ql<=l&&r<=qr) {
            mulv[o]*=v; mulv[o]%=p;
            addv[o]*=v; addv[o]%=p;
            sumv[o]*=v; sumv[o]%=p;
            return;
        }
        pushdown(o,l,r);
        LL mid=(l+r)>>1;
        if (ql<=mid) multi(lson,l,mid,ql,qr,v);
        if (qr>mid) multi(rson,mid+1,r,ql,qr,v);
        pushup(o);
    }
    inline LL query(LL o,LL l,LL r,LL ql,LL qr) { //查询
        if (ql<=l&&r<=qr) return sumv[o];
        pushdown(o,l,r);
        LL mid=(l+r)>>1,rt=0;
        if (ql<=mid) rt+=query(lson,l,mid,ql,qr),rt%=p;
        if (qr>mid) rt+=query(rson,mid+1,r,ql,qr),rt%=p;
        pushup(o);
        return rt;
    }
#undef lson
#undef rson
}SGT;
int main() {
    n=read(); p=read();
    for (re LL i=1;i<=n;i++) a[i]=read();
    SGT.build(1,1,n); m=read();
    for (re LL i=1;i<=m;i++) {
        LL opt,x,y,k; opt=read();
        if (opt==1) {
            x=read(); y=read(); k=read();
            SGT.multi(1,1,n,x,y,k);
        }
        if (opt==2) {
            x=read(); y=read(); k=read();
            SGT.add(1,1,n,x,y,k);
        }
        if (opt==3) {
            x=read(); y=read();
            printf("%lld\n",SGT.query(1,1,n,x,y));
        }
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 02 : 21 PM

发表评论