MnZn线段树60pts求助

P1253 扶苏的问题

AC_CSP @ 2022-09-24 20:40:56

this

蒟蒻把1e9改成1e12,int 变long long,得了60pts


by xs_siqi @ 2022-09-24 21:01:49

@AC_CSP 找到问题了


by xs_siqi @ 2022-09-24 21:05:11

@AC_CSP

使用c++输出 1e18+1,输出的却是1e18。

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n=1e18+1;
    cout<<n<<endl;
    return 0;
}

目前不知道原理。但知道这一条性质之后把小于等于1e18改成小于1e18就过了


by AC_CSP @ 2022-09-25 21:46:10

@xs_siqi 栓Q,不过为什么我改了还是60pts 奇怪


by xs_siqi @ 2022-09-25 23:34:43

@AC_CSP 哪里改错了吧。我直接交你之前发帖子里源代码改成1e18就过了


by AC_CSP @ 2022-09-26 10:06:29

@xs_siqi 再麻烦一下dalao发下AC代码,我改不对了qwq


by xs_siqi @ 2022-09-26 21:07:17

@AC_CSP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7;
struct node{
    int lazy_add,lazy_change,max;
}t[N<<2];
int n,q,L,R,k[N],a,b;
inline int ls(int u){return u<<1;}
inline int rs(int u){return u<<1|1;}
inline bool inrange(int l,int r){return L<=l&&r<=R;}
inline void add_sum(int u){t[u].max=max(t[ls(u)].max,t[rs(u)].max);}
void build_tree(int u,int l,int r){
    t[u].lazy_change=1e18+1;
    if(l==r){
        t[u].max=k[l];
        return;
    }
    int m=l+r>>1;
    build_tree(ls(u),l,m);
    build_tree(rs(u),m+1,r);
    add_sum(u);
}
inline void f(int u,int l,int r,int _lazy,int _change){
    if(_change<1e18){
        t[u].max=_change;
        t[u].lazy_change=_change;
        t[u].lazy_add=0;
    }
    if(_lazy){//1
        t[u].max+=_lazy;
        t[u].lazy_add+=_lazy;
    }
}
inline void downdate(int u,int l,int r){
    int m=l+r>>1;
    f(ls(u),l,m,t[u].lazy_add,t[u].lazy_change);
    f(rs(u),m+1,r,t[u].lazy_add,t[u].lazy_change);
    t[u].lazy_add=0;
    t[u].lazy_change=1e18+1;
}
void add(int u,int l,int r){
    //printf("A:%d %d %d %d\n",u,l,r,t[u].max);
    if(inrange(l,r)){
        f(u,l,r,a,b);//
        return;
    }
    downdate(u,l,r);
    int m=l+r>>1;
    if(L<=m) add(ls(u),l,m);
    if(R>m) add(rs(u),m+1,r);
    add_sum(u);
}
int query(int u,int l,int r){
    //printf("Q:%d %d %d %d\n",u,l,r,t[u].max);
    if(inrange(l,r)) return t[u].max;
    downdate(u,l,r);
    int m=l+r>>1;
    int tmp=-1e18-1;
    if(L<=m) tmp=max(tmp,query(ls(u),l,m));
    if(R>m) tmp=max(tmp,query(rs(u),m+1,r));

    return tmp;
}
signed main(){
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++) scanf("%lld",&k[i]);
    build_tree(1,1,n);
    while(q--){
        int opt;
        scanf("%lld",&opt);
        if(opt==1){
            scanf("%lld%lld%lld",&L,&R,&b);
            a=0;
            add(1,1,n);
        }
        if(opt==2){
            scanf("%lld%lld%lld",&L,&R,&a);
            b=1e18+1;
            add(1,1,n);
        }
        if(opt==3){
            scanf("%lld%lld",&L,&R);
            printf("%lld\n",query(1,1,n));
        }
    }
    return 0;
}

by AC_CSP @ 2022-09-27 09:57:52

@xs_siqi 过了,十分感谢dalao!%%%


|