洛谷P 1438退屈な数列

ブログはもっと良いbossbaby's blogを食べます

構想

さぶん

等差数列を見ると、差分で等差数列を加えるたびに区間に最後の区間を加えて和を求める(接頭辞和)ことがわかります.

セグメントツリー

区間加算と加算は線分ツリーでできます

ツリー配列

木の配列で作ることもできます(残念ながら書きたくないのでできません)

コード#コード#

#include 
#define MAXN 10000100
#define LL long long
#define lid (id<<1)
#define rid (id<<1|1)
using namespace std;
int n,m;
int s[MAXN],su[MAXN];
struct SEG{
    LL lazy,l,r,sum;
}tr[MAXN<<2];
void pushnow(LL id,LL v){
    tr[id].sum+=(tr[id].r-tr[id].l+1)*v;
    tr[id].lazy+=v;
}
void pushdown(LL id){
    if(tr[id].lazy){
        pushnow(lid,tr[id].lazy);
        pushnow(rid,tr[id].lazy);
        tr[id].lazy=0;
    }
}
void pushup(LL id){
    tr[id].sum=tr[lid].sum+tr[rid].sum;
}
void build(LL id,LL l,LL r){
    tr[id].l=l;tr[id].r=r;
    if(l==r){
        tr[id].sum=0;
        tr[id].lazy=0;
        return;
    }
    LL mid=(l+r)>>1;
    build(lid,l,mid);
    build(rid,mid+1,r);
    pushup(id);
}
void update(LL id,LL l,LL r,LL v){
    if(l<=tr[id].l&&r>=tr[id].r){
        pushnow(id,v);
        return;
    }
    pushdown(id);
    LL mid=(tr[id].l+tr[id].r)>>1;
    if(l<=mid)
        update(lid,l,r,v);
    if(r>mid)
        update(rid,l,r,v);
    pushup(id);
}
LL query(LL id,LL l,LL r){
    if(l<=tr[id].l&&r>=tr[id].r)
        return tr[id].sum;
    pushdown(id);
    LL mid=(tr[id].l+tr[id].r)>>1;
    LL ans=0;
    if(l<=mid)
        ans+=query(lid,l,r);
    if(r>mid)
        ans+=query(rid,l,r);
    return ans;
}// 
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>s[i];
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int opt;
        cin>>opt;
        if(opt==1){
            int L,R,K,D;
            cin>>L>>R>>K>>D;
            update(1,L,L,K);
            if(R>L)update(1,L+1,R,D);
            int N=(R-L+1);
            if(R>wq;
            cout<

転載先:https://www.cnblogs.com/bossbaby/p/10951904.html