P2184 贪婪大陆

我们考虑记录每个位置作为左右端点的次数的信息。

1. 直接在两个位置处+1.
2. 查询区间相当于=左端点在当前区间左侧的区间个数-右端点在

#include<cstdio>
#include<iostream>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while
#define ls p<<1
#define rs p<<1|1

const int N=100010,M=4*N;
int n,m,l[M],r[M],a[N];
typedef long long ll;
ll v[M],f[M];
void up(int p){
    v[p]=v[ls]+v[rs];
}
void down(int p){
    ll &vv=f[p];
    if(vv){
        v[ls]+=(r[ls]-l[ls]+1)*vv;
        f[ls]+=vv;
        v[rs]+=(r[rs]-l[rs]+1)*vv;
        f[rs]+=vv;
        vv=0;
    }
}
void build(int p,int ll,int rr){
    l[p]=ll,r[p]=rr;
    if(ll==rr){
        v[p]=a[ll]-a[ll-1];
        return;
    }
    int mid=ll+rr>>1;
    build(ls,ll,mid),build(rs,mid+1,rr);
    up(p);
}
void update(int p,int ll,int rr,int va){
    if(ll<=l[p]&&r[p]<=rr){
        v[p]+=(r[p]-l[p]+1ll)*va;
        f[p]+=va;
        return;
    }
    int mid=l[p]+r[p]>>1;
    down(p);
    if(ll<=mid)update(ls,ll,rr,va);
    if(rr>mid)update(rs,ll,rr,va);
    up(p);
}
ll query(int p,int L,int R){
    if(L<=l[p]&&r[p]<=R)return v[p];
    int mid=l[p]+r[p]>>1;
    down(p);
    ll res=0;
    if(L<=mid)res=query(ls,L,R);
    if(R>mid)res+=query(rs,L,R);
    return res;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    E(i, n)cin>>a[i];
    build(1,1,n);
    E(i, m){
        int op,l,r,k,d;
        cin>>op;
        if(op==1){
            cin>>l>>r>>k>>d;
            update(1,l,l,k);
            if(l<n)update(1,l+1,r,d);
            if(r<n)update(1,r+1,r+1,(l-r)*d-k);
        }
        else{
            cin>>d;
            cout<<query(1,1,d)<<'\n';
        }
    }
    return 0;
}