构建函数就有问题,求大佬查错

P1253 扶苏的问题

qqq100 @ 2023-10-14 15:38:14

#include <bits/stdc++.h>
using namespace std;
int a[1000010];
struct node{
    int l,r,add,dal,mx;     //dal记录延迟修改
                            //add记录延迟增加
                            //mx记录区间最大值 
    node* lch;node* rch;
    node(){
        l=r=add=dal=mx=-INT_MAX;
        lch=rch=NULL;
    }
};
void build(node* root,int l,int r){
    root->l=l;root->r=r;
    if(l+1<r){
        root->lch=new(node);
        root->rch=new(node);
        build(root->lch,l,(l+r)>>1);
        build(root->rch,(l+r)>>1+1,r);
        root->mx=max(root->lch->mx,root->rch->mx);
    }else{
        root->lch=root->rch=NULL;
        root->mx=a[l];
    }

}
void updal(node* root){
    root->mx=root->dal;
    if(root->lch!=NULL) root->lch->dal=root->dal;
    if(root->rch!=NULL) root->rch->dal=root->dal;
    root->dal=-INT_MAX; 
}
void upadd(node* root){
    root->mx+=root->add;
    if(root->lch!=NULL)root->lch->add=root->add;
    if(root->rch!=NULL) root->rch->add=root->add;
    root->add=-INT_MAX;
}
void ame(node* root,int l,int r,int x){
    if(root->dal!=-INT_MAX) updal(root);
    if(root->lch==NULL||root->rch==NULL) return ;
    if(l<=root->l&&r>=root->r){
        root->mx=x;root->lch->dal=root->rch->dal=x;
    }else{
        if(l<(root->l+root->r)/2)
            ame(root->lch,l,r,x);
        if(r>(root->l+root->r)/2)
            ame(root->rch,l,r,x); 
    }
}
void add(node* root,int l,int r,int x){
    if(root->add!=-INT_MAX) upadd(root);
    if(root->lch==NULL||root->rch==NULL) return ;
    if(l<=root->l&&r>=root->r){
        root->mx+=x;root->lch->add=root->rch->add=x;
    }else{
        if(l<(root->l+root->r)/2)
            add(root->lch,l,r,x);
        if(r>(root->l+root->r)/2)
            add(root->rch,l,r,x);
    }
}
int find_max(node* root,int l,int r){
    if(root->add!=-INT_MAX) upadd(root);
    if(root->dal!=-INT_MAX) updal(root);
    if(root->lch==NULL||root->rch==NULL) 
      return root->mx;
    int ans=-INT_MAX;
    if(l<=root->l&&r>=root->r)
        ans=max(ans,root->mx);
    if(l<(root->l+root->r)/2)
        ans=max(ans,find_max(root->lch,l,r));
    if(r>(root->l+root->r)/2)
        ans=max(ans,find_max(root->rch,l,r));
    return ans;
}
int n,q,op,l,r,x; 
int main(){
    scanf("%d %d",&n,&q);
    node* root=new(node);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    build(root,1,n);
    while(q--){
        scanf("%d %d %d",&op,&l,&r);
        switch(op){
            case 1:
                scanf("%d",&x);
                ame(root,l,r,x);
                break;
            case 2:
                scanf("%d",&x);
                add(root,l,r,x);
                break;
            case 3:
                printf("%d\n",find_max(root,l,r));
                break;
        }
    }
    return 0;
}

|