求条30pts
查看原帖
求条30pts
1199534
ycy1124楼主2025/1/24 10:47

除了#1,3,4AC,其余全部RE求助

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,w[200005];
struct Node{
    int l,r,sum,mi,bj;
}a[200005*4];
inline void Push_down(int p){
    a[p*2].bj+=a[p].bj;
    a[p*2+1].bj+=a[p].bj;
    a[p].sum+=(a[p].r-a[p].l+1)*a[p].bj;
    a[p].mi+=a[p].bj;
    a[p].bj=0;
}
inline void Push_up(int p){
    if(a[p*2].bj){
        Push_down(p*2);
    }
    if(a[p*2+1].bj){
        Push_down(p*2+1);
    }
    a[p].sum=a[p*2].sum+a[p*2+1].sum;
    a[p].mi=min(a[p*2].mi,a[p*2+1].mi);
}
inline void New_Tree(int p,int l,int r){
    a[p].l=l;
    a[p].r=r;
    if(l==r){
        a[p].sum=a[p].mi=w[l];
        return;
    }
    int mid=(l+r>>1);
    New_Tree(p*2,l,mid);
    New_Tree(p*2+1,mid+1,r);
    Push_up(p);
}
inline int Find(int p,int l,int r){
    if(a[p].bj){
        Push_down(p);
    }
    if(a[p].l>=l&&a[p].r<=r){
        return a[p].mi;
    }
    int mid=(a[p].l+a[p].r>>1),x;
    if(mid<l){
        x=Find(p*2+1,l,r);
    }
    else if(mid>=r){
        x=Find(p*2,l,r);
    }
    else{
        x=min(Find(p*2,l,r),Find(p*2+1,l,r));
    }
    Push_up(p);
    return x;
}
inline int find(int p,int l,int r){
    if(a[p].bj){
        Push_down(p);
    }
    if(a[p].l>=l&&a[p].r<=r){
        return a[p].sum;
    }
    int mid=(a[p].l+a[p].r>>1),x;
    if(mid<l){
        x=find(p*2+1,l,r);
    }
    else if(mid>=r){
        x=find(p*2,l,r);
    }
    else{
        x=find(p*2,l,r)+find(p*2+1,l,r);
    }
    Push_up(p);
    return x;
}
inline void Push_date(int p,int l,int r,int val){
    Push_down(p);
    if(a[p].l>=l&&a[p].r<=r){
        a[p].bj+=val;
        return;
    }
    int mid=(a[p].l+a[p].r>>1);
    if(mid<l){
        Push_date(p*2+1,l,r,val);
    }
    else if(mid>=r){
        Push_date(p*2,l,r,val);
    }
    else{
        Push_date(p*2+1,l,r,val),Push_date(p*2,l,r,val);
    }
    Push_up(p);
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>w[i];
    }
    New_Tree(1,1,n);
    // cout<<"qwq";
    for(int i=1;i<=q;i++){
        char op;
        cin>>op;
        if(op=='M'){
            int l,r;
            cin>>l>>r;
            cout<<Find(1,l,r)<<endl;
        }
        else if(op=='S'){
            int l,r;
            cin>>l>>r;
            cout<<find(1,l,r)<<endl;
        }
        else{
            int l,r,val;
            cin>>l>>r>>val;
            Push_date(1,l,r,val);
        }
    }
    return 0;
}
2025/1/24 10:47
加载中...