求调,全WA

hao12345ia @ 2024-11-23 14:42:38

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[10000001];
int tree[40000001];
int lazy[40000001];
void build(int u,int x ,int y){
    if(x==y){
        tree[u]=a[x];
        return ;
    }
    int mid=(x+y)/2;
    build(u*2,x,mid);
    build(u*2+1,mid+1,y);
    tree[u]+=tree[u*2]+tree[u*2+1];
}
void duodiangai(int u,int x,int y,int l,int r,int c){
    if(l>=x&&r<=y){
        tree[u]+=(r-l+1)*c;
        lazy[u]+=c;
        return ;
    }
    int mid=(l+r)/2;
    if(lazy[u]>=0){
        tree[u*2]+=(mid-l+1)*lazy[u];
        lazy[u*2]+=lazy[u];
        tree[u*2+1]+=(r-mid)*lazy[u];
        lazy[u*2+1]+=lazy[u];
        lazy[u]=0;
    }
    if(l>=x){
        duodiangai(u*2,x,y,l,mid,c);
    }
    if(r<=y){
        duodiangai(u*2+1,x,y,mid+1,r,c);
    }
}//区间修改 
long long duodiancha(int u,int x,int y,int l,int r){
    if(l>=x&&r<=y){
        return tree[u];
    }
    int mid=(l+r)/2;
    if(lazy[u]>0){
        tree[u*2]+=(mid-l+1)*lazy[u];
        lazy[u*2]+=lazy[u];
        tree[u*2+1]+=(r-mid)*lazy[u];
        lazy[u*2+1]+=lazy[u];
        lazy[u]=0;
    }
    long long ans=0;
    if(l>=x){
        ans+=duodiancha(u*2,x,y,l,mid);
    }   
    if(r<=y){
        ans+=duodiancha(u*2+1,x,y,mid+1,r);
    }
    return ans;
}// 区间查询 
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    for(int i=1;i<=n;i++){
        cout<<duodiancha(1,1,i,1,n)<<endl;
    }
    for(int i=1;i<=m;i++){
        int b;
        int x,y,k;
        cin>>b;
        if(b==1){
            cin>>x>>y>>k;
            duodiangai(1,x,y,1,n,k);
        }
        else{
            cin>>x>>y;
            cout<<duodiancha(1,x,y,1,n)<<endl;
        }
    }
}

by AKCSPS @ 2024-11-23 14:53:31

@hao12345ia 感觉查改的判断不太对，还有build中最后一句是tree[u]=tree[u*2]+tree[u*2+1];

by hao12345ia @ 2024-11-23 15:20:27

查找的问题找到了。可我不到找区间改的问题。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[10000001];
int tree[40000001];
int lazy[40000001];
void build(int u,int x ,int y){
    if(x==y){
        tree[u]+=a[x];
        return ;
    }
    int mid=(x+y)/2;
    build(u*2,x,mid);
    build(u*2+1,mid+1,y);
    tree[u]=tree[u*2]+tree[u*2+1];
}
void duodiangai(int u,int x,int y,int l,int r,int c){
    if(l>=x&&r<=y){
        tree[u]+=(r-l+1)*c;
        lazy[u]+=c;
        return ;
    }
    int mid=(l+r)/2;
    if(lazy[u]){
        tree[u*2]+=(mid-l+1)*lazy[u];
        lazy[u*2]+=lazy[u];
        tree[u*2+1]+=(r-mid)*lazy[u];
        lazy[u*2+1]+=lazy[u];
        lazy[u]=0;
    }
    if(x<=mid){ //更改 
        duodiangai(u*2,x,y,l,mid,c);
    }
    if(y>mid){//更改 
        duodiangai(u*2+1,x,y,mid+1,r,c);
    }
}//区间修改 
long long duodiancha(int u,int x,int y,int l,int r){
    if(l>=x&&r<=y){
        return tree[u];
    }
    int mid=(l+r)/2;
    if(lazy[u]){
        tree[u*2]+=(mid-l+1)*lazy[u];
        lazy[u*2]+=lazy[u];
        tree[u*2+1]+=(r-mid)*lazy[u];
        lazy[u*2+1]+=lazy[u];
        lazy[u]=0;
    }
    long long ans=0;
    if(x<=mid){//更改
        ans+=duodiancha(u*2,x,y,l,mid);
    }   
    if(y>mid){//更改 
        ans+=duodiancha(u*2+1,x,y,mid+1,r);
    }
    return ans;
}// 区间查询 
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);

    for(int i=1;i<=m;i++){
        int b;
        int x,y,k;
        cin>>b;
        if(b==1){
            cin>>x>>y>>k;
            duodiangai(1,x,y,1,n,k);    
            for(int i=1;i<=n;i++){
                for(int j=i;j<=n;j++){
                    cout<<duodiancha(1,i,j,1,n)<<" ";   
                }
                cout<<endl;
            }
        }
        else{
            cin>>x>>y;
            cout<<duodiancha(1,x,y,1,n)<<endl;
        }
    }
}

by hao12345ia @ 2024-11-23 15:24:55

@AKCSPS

by hao12345ia @ 2024-11-23 16:29:40

此贴结