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