20分求助,在线等

P1253 扶苏的问题

Chancylaser @ 2022-08-04 19:25:57

Ac at 1,3 其他WA

#include<bits/stdc++.h>
#define gou 2e9 
#define INF -1e18
using namespace std;

const int N=1e6+5;
int n,q;
long long a[N];

struct Tree{
    int l,r;
    long long sum,mx,all,lazy;
}t[4*N];

void build(int p,int x,int y){
    t[p].l=x,t[p].r=y;
    t[p].lazy=0; t[p].all=gou;
    if(x==y){
        t[p].sum=a[x];t[p].mx=a[x];
        return;
    }
    int mid=(x+y)>>1;
    build(p<<1,x,mid);build(p<<1|1,mid+1,y);
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
    t[p].mx=max(t[p<<1].mx,t[p<<1|1].mx);
}

void pushdown(int p){
    if(t[p].all!=gou){
        t[p<<1].all=t[p].all,t[p<<1|1].all=t[p].all;
        t[p<<1].mx=t[p].all,t[p<<1|1].mx=t[p].all;
        t[p<<1].sum=(t[p<<1].r-t[p<<1].l+1)*t[p].all;
        t[p<<1|1].sum=(t[p<<1|1].r-t[p<<1|1].l+1)*t[p].all;
        t[p<<1].lazy=0,t[p<<1|1].lazy=0;
    }
    t[p<<1].lazy+=t[p].lazy,t[p<<1|1].lazy+=t[p].lazy;
    t[p<<1].mx+=t[p].lazy,t[p<<1|1].mx+=t[p].lazy;
    t[p<<1].sum+=(t[p<<1].r-t[p<<1].l+1)*t[p].lazy;
    t[p<<1|1].sum+=(t[p<<1|1].r-t[p<<1|1].l+1)*t[p].lazy;
    t[p].lazy=0; t[p].all=gou;
}

void xiu(int p,int x,int y,int k){
    if(t[p].l>y||t[p].r<x) return;
    if(t[p].l>=x&&t[p].r<=y){
        t[p].all=k; t[p].mx=k; t[p].lazy=0;
        t[p].sum=(t[p].r-t[p].l+1)*k;
        return;
    }
    pushdown(p);
    xiu(p<<1,x,y,k), xiu(p<<1|1,x,y,k);
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
    t[p].mx=max(t[p<<1].mx,t[p<<1|1].mx);
}

void addsum(int p,int x,int y,int k){
    if(t[p].l>y||t[p].r<x) return;
    if(t[p].l>=x&&t[p].r<=y){
        t[p].mx+=k; t[p].lazy+=k;  
        t[p].sum+=(t[p].r-t[p].l+1)*k;
        return;
    }
    pushdown(p);
    addsum(p<<1,x,y,k), addsum(p<<1|1,x,y,k);
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
    t[p].mx=max(t[p<<1].mx,t[p<<1|1].mx);
}

long long maxn(int p,int x,int y){
    if(t[p].l>y||t[p].r<x) return INF;
    if(t[p].l>=x&&t[p].r<=y) return t[p].mx;
    pushdown(p);
    return max(maxn(p<<1,x,y),maxn(p<<1|1,x,y));
}
int main(){

    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);

    int op,l,r,x;
    for(int i=1;i<=q;i++){
        scanf("%d%d%d",&op,&l,&r);
        if(op==1){
            scanf("%d",&x);
            xiu(1,l,r,x);
        }
        else if(op==2){
            scanf("%d",&x);
            addsum(1,l,r,x);
        }
        else printf("%lld\n",maxn(1,l,r));
    }
    return 0;
}

by Chancylaser @ 2022-08-04 19:26:20

@2018ljw 按您说的改了,还是20(((


by Chancylaser @ 2022-08-04 19:27:47

@2018ljw 在pushodown加了个tp.all=0就A了

谢谢啦


|