cat_lover1 @ 2023-11-16 00:25:26
思路几乎与第一篇题解相同，得40分，后6个点都TLE了
#define max(a,b) ((a)>(b)?(a):(b))
#define mid l+(r-l>>1)
#define lc h<<1
#define rc h<<1|1
#define IN x<=l&&r<=y
#define OUT (y<l||r<x)
#define LL long long
#define nul 1000000001
tr[4000001],t1[4000001],t2[4000001],n,q,op,x,y,z;
void make_tag1(h,x){
tr[h]=t1[h]=x,t2[h]=0;
}
void make_tag2(h,x){
t2[h]+=x,tr[h]+=x;
t1[h]!=nul&&(t1[h]+=x);
}
void pushup(h){tr[h]=max(tr[lc],tr[rc]);}
void pushdown(h){
if(t1[h]!=nul){
make_tag1(lc,t1[h]),make_tag1(rc,t1[h]);
t1[h]=nul;
}
else if(t2[h]){
make_tag2(lc,t2[h]),make_tag2(rc,t2[h]);
t2[h]=0;
}
}
void build(h,l,r){
if(l^r){
build(lc,l,mid),
build(rc,mid+1,r);
pushup(h);
}
else scanf("%d",tr+h);
}
qry(h,l,r){
//printf("%d: %d %d %d %d %d\n",op,h,l,r,x,y);
if(IN)return tr[h];
if(!OUT){
pushdown(h);
return max(qry(lc,l,mid),qry(rc,mid+1,r));
}
return -nul;
}
void upd(h,l,r){
//printf("%d: %d %d %d %d %d %d\n",op,h,l,r,x,y,z);
if(IN)op==1?make_tag1(h,z):(make_tag2(h,z));
else if(!OUT)pushdown(h),upd(lc,l,mid),upd(rc,mid+1,r),pushup(h);
}
void init(){
for(int i=0;i<4000001;++i)t1[i]=nul;
scanf("%d%d",&n,&q);
build(1,1,n);
}
void solve(){
scanf("%d%d%d",&op,&x,&y);
if(op^3)scanf("%d",&z),upd(1,1,n);
else printf("%d\n",qry(1,1,n));
}
main(){
for(init();q--;)solve();
}
by Buried_Dream @ 2023-11-16 09:32:14
@5t0_0r2 然后他op明明修改了啊，他的op是用来判断这次是×还是加的（希望你别啥也没看懂就来说了）
by Buried_Dream @ 2023-11-16 09:32:48
@5t0_0r2 6，那他为啥不直接比着题解改/qd
by 5t0_0r2 @ 2023-11-16 09:34:51
@cz_awa 你 nul 还是开小了（直接开到
by cat_lover1 @ 2023-11-16 09:35:25
@Buried_Dream 似乎可以边读边建树 我代码的max不能定义，得用函数的形式，不然会退化成O（n）
by cat_lover1 @ 2023-11-16 09:36:36
@5t0_tr2 按照大佬的建议，我修改了 nul 为2147483647 目前得50分，后5个点从tle变为wa
by Buried_Dream @ 2023-11-16 09:37:05
@cz_awa 我知道可以边读入边建树啊，我一直都是这个写法，你好像@错人了。
by 5t0_0r2 @ 2023-11-16 09:37:54
@cz_awa 上面说了，你 nul 还是开小了（开到
by Buried_Dream @ 2023-11-16 09:40:23
@cz_awa 要printf("%lld\n", qry) 吗
by 5t0_0r2 @ 2023-11-16 09:42:00
@cz_awa 帮你改好了：
//integer may be negative,so Read() should be noticed
long long max(long long a,long long b){return a>b?a:b;}
#define mid l+(r-l>>1)
#define lc h<<1
#define rc h<<1|1
#define IN x<=l&&r<=y//important
#define OUT (y<l||r<x)
#define nul 100000000000000000
#define make_tag1(h,x) tr[h]=t1[h]=x,t2[h]=0
#define make_tag2(h,x) tr[h]+=x,t1[h]!=nul?t1[h]+=x:(t2[h]+=x)
#define pushup(h) tr[h]=max(tr[lc],tr[rc])
#define pushdown(h) t1[h]^nul?make_tag1(lc,t1[h]),make_tag1(rc,t1[h]),t1[h]=nul:(t2[h]&&(make_tag2(lc,t2[h]),make_tag2(rc,t2[h]),t2[h]=0))
long long tr[4000001],t1[4000001],t2[4000001],n,q,op,x,y,z;
void build(long long h,long long l,long long r){
if(l^r)build(lc,l,mid),build(rc,mid+1,r),pushup(h);
else scanf("%lld",tr+h);
}
long long qry(long long h,long long l,long long r){
if(IN)return tr[h];
if(!OUT){
pushdown(h);
return max(qry(lc,l,mid),qry(rc,mid+1,r));
}
return -nul;
}
void upd(long long h,long long l,long long r){
if(IN)op&1?make_tag1(h,z):(make_tag2(h,z));
else if(!OUT)pushdown(h),upd(lc,l,mid),upd(rc,mid+1,r),pushup(h);
}
void init(){
for(long long i=0;i<4000001;++i)t1[i]=nul;
scanf("%lld%lld",&n,&q);
build(1,1,n);
}
void solve(){
scanf("%lld%lld%lld",&op,&x,&y);
if(op^3)scanf("%lld",&z),upd(1,1,n);
else printf("%lld\n",qry(1,1,n));
}
main(){
for(init();q--;)solve();
}by cat_lover1 @ 2023-11-16 09:44:50
AC了，祝各位好运^^ NOIP rp++！
tr,和两个tag数组都得long long，真的是十年OI一场空，不开long long见祖宗！
//integer may be negative,so Read() should be noticed
#define ll long long
ll max(ll a,ll b){return a>b?a:b;}
#define mid l+(r-l>>1)
#define lc h<<1
#define rc h<<1|1
#define IN x<=l&&r<=y//important
#define OUT (y<l||r<x)
#define nul 1000000000000000000
#define make_tag1(h,x) tr[h]=t1[h]=x,t2[h]=0
#define make_tag2(h,x) tr[h]+=x,t1[h]!=nul?t1[h]+=x:(t2[h]+=x)
#define pushup(h) tr[h]=max(tr[lc],tr[rc])
#define pushdown(h) t1[h]^nul?make_tag1(lc,t1[h]),make_tag1(rc,t1[h]),t1[h]=nul:(t2[h]&&(make_tag2(lc,t2[h]),make_tag2(rc,t2[h]),t2[h]=0))
ll tr[4000001],t1[4000001],t2[4000001];
n,q,op,x,y,z;
void build(h,l,r){
if(l^r)build(lc,l,mid),build(rc,mid+1,r),pushup(h);
else scanf("%lld",tr+h);
}
ll qry(h,l,r){
if(IN)return tr[h];
if(!OUT){
pushdown(h);
return max(qry(lc,l,mid),qry(rc,mid+1,r));
}
return -nul;
}
void upd(h,l,r){
if(IN)op&1?make_tag1(h,z):(make_tag2(h,z));
else if(!OUT)pushdown(h),upd(lc,l,mid),upd(rc,mid+1,r),pushup(h);
}
void init(){
for(int i=0;i<4000001;++i)t1[i]=nul;
scanf("%d%d",&n,&q);
build(1,1,n);
}
void solve(){
scanf("%d%d%d",&op,&x,&y);
if(op^3)scanf("%d",&z),upd(1,1,n);
else printf("%lld\n",qry(1,1,n));
}
main(){
for(init();q--;)solve();
}