蒟蒻20分求调

P1253 扶苏的问题

hnxxwpf @ 2024-05-09 19:50:25

#include<iostream>
#define lc p << 1
#define rc p << 1 | 1 
#define int long long
using namespace std;
const int maxn = 1e6 + 1;
const int inf = 1e18;
struct Tree{
    int l,r,sum,add,cover;
}tr[maxn << 2];
int n,p,a[maxn];
void build(int p,int l,int r){
    tr[p] = (Tree) {l,r,a[l],0,inf};
    if(l == r) return;
    int m = l + (r - l >> 1);
    build(lc,l,m);
    build(rc,m+1,r);
    tr[p].sum = max(tr[lc].sum,tr[rc].sum);
}
void cupdate(int p,int l,int r,int x){
    if(l <= tr[p].l && tr[p].r <= r){
        tr[p].sum = x;
        tr[p].cover = x;
        tr[p].add = 0;
        return;
    }
    if(tr[p].cover != inf){
        tr[lc].sum = tr[rc].sum = tr[p].cover;
        tr[lc].cover = tr[rc].cover = tr[p].cover;
        tr[lc].add = tr[rc].add = 0;
        tr[p].cover = inf;
    }
    if(tr[p].add){
        tr[lc].sum += tr[p].add;
        tr[rc].sum += tr[p].add;
        tr[lc].add += tr[p].add;
        tr[rc].add += tr[p].add;
        tr[p].add = 0;
    }
    int m = tr[p].l + (tr[p].r - tr[p].l >> 1);
    if(l <= m) cupdate(lc,l,r,x);
    if(r > m) cupdate(rc,l,r,x);
    tr[p].sum = max(tr[lc].sum,tr[rc].sum);
}
void aupdate(int p,int l,int r,int x){
    if(l <= tr[p].l && tr[p].r <= r){
        tr[p].sum += x;
        tr[p].add += x;
        return;
    }
    if(tr[p].cover != inf){
        tr[lc].sum = tr[rc].sum = tr[p].cover;
        tr[lc].cover = tr[rc].cover = tr[p].cover;
        tr[lc].add = tr[rc].add = 0;
        tr[p].cover = inf;
    }
    if(tr[p].add){
        tr[lc].sum += tr[p].add;
        tr[rc].sum += tr[p].add;
        tr[lc].add += tr[p].add;
        tr[rc].add += tr[p].add;
        tr[p].add = 0;
    }
    int m = tr[p].l + (tr[p].r - tr[p].l >> 1);
    if(l <= m) aupdate(lc,l,r,x);
    if(r > m) aupdate(rc,l,r,x);
    tr[p].sum = max(tr[lc].sum,tr[rc].sum);
}
int query(int p,int x,int y){
    if(x <= tr[p].l && tr[p].r <= y) return tr[p].sum;
    if(tr[p].cover != inf){
        tr[lc].sum = tr[rc].sum = tr[p].cover;
        tr[lc].cover = tr[rc].cover = tr[p].cover;
        tr[lc].add = tr[rc].add = 0;
        tr[p].cover = inf;
    }
    if(tr[p].add){
        tr[lc].sum += tr[p].add;
        tr[rc].sum += tr[p].add;
        tr[lc].add += tr[p].add;
        tr[rc].add += tr[p].add;
        tr[p].add = 0;
    }
    int m = tr[p].l + (tr[p].r - tr[p].l >> 1),maxx = -inf;
    if(x <= m) maxx = query(lc,x,m);
    if(y > m) maxx = max(maxx,query(rc,m+1,y));
    return maxx;
}
signed main(){
    scanf("%lld%lld",&n,&p);
    for(int i = 1;i <= n;++i) scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i = 0,opt,l,r,x;i < p;++i){
        scanf("%lld%lld%lld",&opt,&l,&r);
        if(opt == 1){
            scanf("%lld",&x);
            cupdate(1,l,r,x);
        }else if(opt == 2){
            scanf("%lld",&x);
            aupdate(1,l,r,x);
        }else printf("%lld\n",query(1,l,r));
    }
    return 0;
}

by hnxxwpf @ 2024-05-16 20:27:19

update的x可为浮点型,此贴结


by wangtairan114 @ 2024-07-30 20:12:18

@hnxxwpf az,大佬orz


|