分块，qz

FChang @ 2024-07-04 17:23:25

#include<bits/stdc++.h>
#define int long long
using namespace std;

/*
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1xu
2 1 4

*/

const int N = 5e5 + 15,M = 5e5 + 5;

int n,m,sq,len;

int a[N];

int sum[M],tag[N],p[N],ll[N],rr[N],siz[N];

void add(int l,int r,int d) {
    int l1 = ((l-1)/len+1),r1 = ((r-1)/len+1);
    l1 += (ll[l1]!=l);
    r1 -= (rr[r1]!=r);
    for(int i=l1; i<=r1; ++i) sum[i] += d * siz[i],tag[i] += d;
    for(int j=l; j<ll[l1]; ++j) a[j] += d,sum[p[j]]+=d;
    for(int j=rr[r1]+1; j<=r; ++j) a[j] += d,sum[p[j]]+=d;
    return ;
}

int query(int l,int r) {
    int l1 = ((l-1)/len+1),r1 = ((r-1)/len+1),res = 0;
    l1 += (ll[l1]!=l);
    r1 -= (rr[r1]!=r);
    for(int i=l1; i<=r1; ++i) res += sum[i];
    for(int j=l; j<ll[l1]; ++j) res += a[j] + tag[p[j]];
    for(int j=rr[r1]+1; j<=r; ++j) res += a[j] + tag[p[j]];
    return res;
}

signed main() {
    freopen("P3372_4.in","r",stdin);
    freopen("P3372.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    cin>>n>>m;
    for(int i=1; i<=n; ++i) cin>>a[i];
    len = sq = sqrt(n);
    for(int i=1; i<=sq; ++i) {
        ll[i] = rr[i-1] + 1,rr[i] = ll[i] + sq - 1;
        siz[i] = rr[i] - ll[i] + 1;
        for(int j=ll[i]; j<=rr[i]; ++j) sum[i] += a[j],p[j] = i;
    }
    if(rr[sq]!=n) {
        ++sq;
        ll[sq] = rr[sq-1] + 1,rr[sq] = n;
        siz[sq] = rr[sq] - ll[sq] + 1;
        for(int j=ll[sq]; j<=n; ++j) sum[sq] += a[j],p[j] = sq;
    }
    int opt,x,y,k;
    while(m--) {
        cin>>opt>>x>>y;
        if(opt==1) {
            cin>>k;
            add(x,y,k);
        } else {
            cout<<query(x,y)<<"\n";
        }
    }
    return 0;
}

/*
((l-1)/sq+1):

1 2 3 4 5

1 1 2 2 3

*/

by FChang @ 2024-07-04 17:24:00

60 pts WA

by just_do_it_now @ 2024-07-11 15:09:15

本蒟蒻分块也不太好，弹道可以贴一个线段树的代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,m;
int a[N],tree[4*N],lazy[4*N];
void push_up(int fa){
    tree[fa]=tree[fa<<1]+tree[fa<<1|1];
}
void push_down(int left,int right,int fa){
    int mid=(left+right)>>1;
    tree[fa<<1]+=lazy[fa]*(mid-left+1);
    lazy[fa<<1]+=lazy[fa];
    tree[fa<<1|1]+=lazy[fa]*(right-mid);
    lazy[fa<<1|1]+=lazy[fa];
    lazy[fa]=0;
}
void build_tree(int left,int right,int fa){
    if (left==right){
        tree[fa]=a[left];
        return;
    }
    int mid=(left+right)>>1;
    build_tree(left,mid,fa<<1);
    build_tree(mid+1,right,fa<<1|1);
    push_up(fa);
}
void update(int ql,int qr,int left,int right,int k,int fa){
    if (ql<=left&&qr>=right){
        tree[fa]+=k*(right-left+1);
        lazy[fa]+=k;
        return;
    }
    push_down(left,right,fa);
    int mid=(left+right)>>1;
    if (ql<=mid)update(ql,qr,left,mid,k,fa<<1);
    if (qr>mid)update(ql,qr,mid+1,right,k,fa<<1|1);
    push_up(fa);
}
int query(int ql,int qr,int left,int right,int fa){
    int ans=0;
    if (ql<=left&&qr>=right)return tree[fa];
    int mid=(left+right)>>1;
    push_down(left,right,fa);
    if (ql<=mid)ans+=query(ql,qr,left,mid,fa<<1);
    if (qr>mid)ans+=query(ql,qr,mid+1,right,fa<<1|1);
    return ans;
}
signed main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++)cin>>a[i];
    build_tree(1,n,1);
    int op,left,right,k;
    for (int i=1;i<=m;i++){
        cin>>op>>left>>right;
        if (op==1){
            cin>>k;
            update(left,right,1,n,k,1);
        }
        if (op==2)cout<<query(left,right,1,n,1)<<endl;
    }
    return 0;
}