M_sea

洛谷2023 [AHOI2009]维护序列
题目描述老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。 有长为N的数列,不妨设为a1,a2,…,a...
扫描右侧二维码阅读全文
13
2017/11

洛谷2023 [AHOI2009]维护序列

题目描述

老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。 有长为N的数列,不妨设为a1,a2,…,aN 。有如下三种操作形式: (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和,由于答案可能很大,你只需输出这个数模P的值。

传送门

算法

这题和洛谷3373 线段树2有什么区别呢?
把m换一下位置就A了。。。

代码

#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;
}
最后修改:2018 年 11 月 09 日 04 : 29 PM

发表评论