P1438 boring sequence line segment tree + difference

P1438 Boring series Line segment tree + Difference

---

Ideas : The question is nothing more than Line segment tree 1 A differential array is added on the basis of , So what we need to focus on is How to maintain a differential array . When known $opt=1$ when , We need to be in a range $[l,r]$ The first is $k$ The tolerance is $d$ A series of equal proportions . The segment tree can be modified by the following derivation ：

• $l=1$$r=5$$k=1$$d=2$
• In subscript $[1,5]$ Add..., respectively $1$$3$$5$$7$$9$
• Convert it into a differential array ：$1$$2$$2$$2$$2$$-9$
• According to the above formula, we only need to $3$ Time $modify$ operation , Namely $modify(1,l,l)$ 、$modify(1,l+1,r)$ 、$modify(1,r+1,r+1)$
• Details to note , If $l==r$ Then there is no need $modify(1,l+1,r)$ If $r+1>n$ Then there is no need $modify(1,r+1,r+1)$ .

---

Code ：

/* * @author: Snow * @Description: Algorithm Contest * @LastEditTime: 2022-07-26 09:43:44 */
#include<bits/stdc++.h>
using namespace std;
#define int long long 
// #pragma GCC optimize(3)
#define re register int
typedef pair<int,int>PII;
#define pb emplace_back
#define debug(a) cout<<a<<' ';
#define fer(i,a,b) for(re i=a;i<=b;i++)
#define der(i,a,b) for(re i=a;i>=b;i--)
int n,m;
const int N = 1e5+10;
int w[N];
struct Node{
    
    int l,r,sum,lazy;
}tr[N*4];
void pushup(int u){
    
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u){
    
    auto &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
    if(tr[u].lazy){
    
        left.lazy+=root.lazy,left.sum+=(left.r-left.l+1)*root.lazy;
        right.lazy+=root.lazy,right.sum+=(right.r-right.l+1)*root.lazy;
        root.lazy=0;
    }
}
void build(int u,int l,int r){
    
    if(l==r){
    
        tr[u]={
    l,r,w[l],0};
    }
    else{
    
        tr[u]={
    l,r};
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
void modify(int u,int l,int r,int d){
    
    if(tr[u].l>=l&&tr[u].r<=r){
    
        tr[u].sum+=(tr[u].r-tr[u].l+1)*d;
        tr[u].lazy+=d;// Delay devolution 
    }
    else{
    
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid)modify(u<<1,l,r,d);
        if(r>mid)modify(u<<1|1,l,r,d);
        pushup(u);
    }
}
int query(int u,int l,int r){
    
    if(tr[u].l>=l&&tr[u].r<=r){
    
        return tr[u].sum;
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    int sum=0;
    if(l<=mid)sum=query(u<<1,l,r);
    if(r>mid)sum+=query(u<<1|1,l,r);
    return sum;
}
signed main(){
    
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    fer(i,1,n)cin>>w[i];
    der(i,n,1)w[i]=w[i]-w[i-1];
    build(1,1,n);
    while(m--){
    
        int op;
        cin>>op;
        if(op==1){
    
            int l,r,k,d;
            cin>>l>>r>>k>>d;
            modify(1,l,l,k);
            if(l<r)modify(1,l+1,r,d);
            if(r<n)modify(1,r+1,r+1,-(k+(r-l)*d));
        }
        else{
    
            int p;
            cin>>p;
            cout<<query(1,1,p)<<endl;
        }
    }
    return 0;
}