WA声一片，用树状数组写的，求调（玄关））

WangYao0126 @ 2024-01-29 11:59:08

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long fw[100005],fw1[100005],a[100005];
void add(int p,int v){
    for(long long q=p*v;p<=n;p+=(p&-p)){
        fw[p]+=v;
        fw1[p]=q;
    }
    return ;
}
int query(int p){
    long long res=0;
    for(int i=p;i!=0;i-=(i&-i))
        res+=fw[i]*(p+1)-fw1[i];
    return res;
}
int query1(int l,int r){
    return query(r)-query(l-1);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=n;i>=1;i--)
        add(i,a[i]-=a[i-1]);
    for(int i=1;i<=m;i++){
        int type;
        cin>>type;
        if(type==1){
            int l,r,k;
            cin>>l>>r>>k;
            add(l,k);
            add(r+1,-k);
        } 
        else{
            int l,r;
            cin>>l>>r;
            cout<<query1(l,r)<<'\n';
        }
    }
    return 0;
}

by ___njr___ @ 2024-01-29 19:45:05

@沃若

by ___njr___ @ 2024-01-29 19:48:41

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long fw[100005],fw1[100005],a[100005];
void add(int p,int v){
    for(long long q= 1LL* p*v;p<=n;p+=(p&-p)){
        fw[p]+=v;
        fw1[p] +=q;
    }
    return ;
}
long long query(int p){
    long long res=0;
    for(int i=p;i!=0;i-=(i&-i))
        res+=1LL*fw[i]*(p+1)-fw1[i];
    return res;
}
long long query1(int l,int r){
    return query(r)-query(l-1);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=n;i>=1;i--)
        add(i,a[i]-=a[i-1]);
    for(int i=1;i<=m;i++){
        int type;
        cin>>type;
        if(type==1){
            int l,r,k;
            cin>>l>>r>>k;
            add(l,k);
            if(r<n)add(r+1,-k);
        } 
        else{
            int l,r;
            cin>>l>>r;
            cout<<query1(l,r)<<'\n';
        }
    }
    return 0;
}

by ___njr___ @ 2024-01-29 19:50:27

1. 要开long long，乘法前乘上1LL
2. 第8行fw1[p]=q;应改为fw1[p]+=q;

by 沃若 @ 2024-01-29 22:32:08

@njr 正确的