求助关于inf的问题

P4513 小白逛公园

Godzilla @ 2021-05-10 17:33:50

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <ctime>

#define LL long long

using namespace std;

const int kN=5e5+5;
const LL kInf=1e14;

struct Smt{
    int l=0,r=0;
    LL Lsum=-kInf,Rsum=-kInf,Msum=-kInf,Sum=-kInf;
    #define Ls(p) (p<<1)
    #define Rs(p) ((p<<1)+1)
    #define L(p) tree[p].l
    #define R(p) tree[p].r
    #define Lsum(p) tree[p].Lsum
    #define Rsum(p) tree[p].Rsum
    #define Msum(p) tree[p].Msum
    #define Sum(p) tree[p].Sum
}tree[4*kN];

int n,m;
int a[kN];

void P_u(int p);

void Build(int l,int r,int p){
    L(p)=l;R(p)=r;
    if(l==r){
        Sum(p)=Lsum(p)=Rsum(p)=Msum(p)=a[l];
        return;
    }
    int mid=(l+r)>>1;
    Build(l,mid,Ls(p));
    Build(mid+1,r,Rs(p));
    P_u(p);
}

void P_u(int p){
    Sum(p)=Sum(Ls(p))+Sum(Rs(p));
    Lsum(p)=max(Lsum(Ls(p)),Sum(Ls(p))+Lsum(Rs(p)));
    Rsum(p)=max(Rsum(Rs(p)),Sum(Rs(p))+Rsum(Ls(p)));
    Msum(p)=max(Msum(Ls(p)),max(
    Msum(Rs(p)),Rsum(Ls(p))+Lsum(Rs(p))));
}

void Modify(int x,int s,int p){
    int l=L(p),r=R(p);
    if(l==x&&r==x){
        Sum(p)=Lsum(p)=Rsum(p)=Msum(p)=s;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid){
        Modify(x,s,Ls(p));
    }
    else{
        Modify(x,s,Rs(p));
    }
    P_u(p);
}

Smt Query(int nl,int nr,int p){
    int l=L(p),r=R(p);
    if(l>=nl&&r<=nr){
        return tree[p];
    }
    Smt res,t1,t2;
    int mid=(l+r)>>1;
    if(nl<=mid){
        t1=Query(nl,nr,Ls(p));
    }
    if(nr>mid){
        t2=Query(nl,nr,Rs(p));
    }
    res.Sum=t1.Sum+t2.Sum;
    res.Lsum=max(t1.Lsum,t1.Sum+t2.Lsum);
    res.Rsum=max(t2.Rsum,t2.Sum+t1.Rsum);
    res.Msum=max(t1.Msum,max(t2.Msum,t1.Rsum+t2.Lsum));
    return res;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    Build(1,n,1);
    for(int i=1;i<=m;++i){
        int k,a,b,s,p;
        scanf("%d",&k);
        if(k==1){
            scanf("%d%d",&a,&b);
            if(a>b){swap(a,b);}
            printf("%lld\n",Query(a,b,1).Msum);
        }
        else{
            scanf("%d%d",&p,&s);
            Modify(p,s,1);
        }
    }
    return 0;
}

请问为什么kInf设置成1e18就会WA8个点,而设置成1e14就AC,请问1e18是在哪里爆long long 了呢?


by XiaoQuQu @ 2021-05-10 17:46:15

实际上,1e18 = 100,0000,0000,0000,0000 并不会爆long long.测试代码:

#include<iostream>
long long n = 1e18;
int main(void) {
    printf("%lld", n);
    return 0;
}

by XiaoQuQu @ 2021-05-10 17:47:13

对了,测试环境:Visual Studio 2019 Debug x86


by Godzilla @ 2021-05-10 17:48:21

@XiaoQuQu 我是说可能在运算的途中爆了long long


by XiaoQuQu @ 2021-05-10 17:52:24

这个我还需要一点时间帮您检查。能下载数据下来吗?如果能的话,您可以尝试输出每一步的结果,来看看是哪里出错了。二分查找的时间复杂度是O(logn)


by Godzilla @ 2021-05-10 17:56:53

https://www.luogu.com.cn/paste/iltfef7m


|