allen2010 @ 2023-05-09 19:52:56
#include <bits/stdc++.h>
#define MAXN 1000001
#define ll long long
using namespace std;
unsigned ll n,m,a[MAXN],ans[MAXN<<4],tag[MAXN<<4],tag2[MAXN<<4];
inline ll ls(ll x)
{
return x<<1;
}
inline ll rs(ll x)
{
return x<<1|1;
}
void scan()
{
cin>>n>>m;
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
}
inline void push_up(ll p)
{
ans[p]=max(ans[ls(p)],ans[rs(p)]);
}
void build(ll p,ll l,ll r)
{
tag[p]=0;
tag2[p]=0;
if(l==r){ans[p]=a[l];return ;}
ll mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
push_up(p);
}
inline void f(ll p,ll l,ll r,ll k,ll method)
{
if(!method)
{
tag[p]+=k;
ans[p]+=k;
}else{
tag2[p]=1;
tag[p]=k;
ans[p]=k;
}
}
inline void push_down(ll p,ll l,ll r)
{
ll mid=(l+r)>>1;
f(ls(p),l,mid,tag[p],tag2[p]);
f(rs(p),mid+1,r,tag[p],tag2[p]);
tag[p]=0;
tag2[p]=0;
}
inline void update(ll nl,ll nr,ll l,ll r,ll p,ll k)
{
if(nl<=l&&r<=nr)
{
ans[p]+=k;
tag[p]+=k;
return;
}
push_down(p,l,r);
ll mid=(l+r)>>1;
if(nl<=mid)update(nl,nr,l,mid,ls(p),k);
if(nr>mid) update(nl,nr,mid+1,r,rs(p),k);
push_up(p);
}
inline void update2(ll nl,ll nr,ll l,ll r,ll p,ll k)
{
if(nl<=l&&r<=nr)
{
ans[p]=k;
tag[p]=k;
tag2[p]=1;
return;
}
push_down(p,l,r);
ll mid=(l+r)>>1;
if(nl<=mid)update(nl,nr,l,mid,ls(p),k);
if(nr>mid) update(nl,nr,mid+1,r,rs(p),k);
push_up(p);
}
ll query(ll q_x,ll q_y,ll l,ll r,ll p)
{
ll res=0;
if(q_x<=l&&r<=q_y)return ans[p];
ll mid=(l+r)>>1;
push_down(p,l,r);
if(q_x<=mid)res=max(res,query(q_x,q_y,l,mid,ls(p)));
if(q_y>mid) res=max(res,query(q_x,q_y,mid+1,r,rs(p)));
return res;
}
int main()
{
ll a1,b,c,d,e,f;
scan();
build(1,1,n);
while(m--)
{
scanf("%lld",&a1);
switch(a1)
{
case 1:{
scanf("%lld%lld%lld",&b,&c,&d);
update2(b,c,1,n,1,d);
break;
}
case 2:{
scanf("%lld%lld%lld",&b,&c,&d);
update(b,c,1,n,1,d);
break;
}
case 3:{
scanf("%lld%lld",&e,&f);
printf("%lld\n",query(e,f,1,n,1));
break;
}
}
}
return 0;
}by allen2010 @ 2023-05-10 06:33:10
犯了一些低级错误，更正如下，但是还是50分
by allen2010 @ 2023-05-10 06:33:37
#include <bits/stdc++.h>
#define MAXN 1000007
#define ll signed long long
using namespace std;
ll n,m,a[MAXN],ans[MAXN<<4],tag[MAXN<<4],tag2[MAXN<<4];
inline ll ls(ll x)
{
return x<<1;
}
inline ll rs(ll x)
{
return x<<1|1;
}
void scan()
{
cin>>n>>m;
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
}
inline void push_up(ll p)
{
ans[p]=max(ans[ls(p)],ans[rs(p)]);
}
void build(ll p,ll l,ll r)
{
tag[p]=0;
tag2[p]=0;
if(l==r){ans[p]=a[l];return ;}
ll mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
push_up(p);
}
inline void f(ll p,ll l,ll r,ll k,ll method)
{
if(!method)
{
//tag2[p]=1 累加改
//tag2[p]=0 累加
tag[p]+=k;
ans[p]+=k;
}else{
//tag2[p]=1 改
//tag2[p]=0 改
tag2[p]=1;
tag[p]=k;
ans[p]=k;
}
}
inline void push_down(ll p,ll l,ll r)
{
ll mid=(l+r)>>1;
f(ls(p),l,mid,tag[p],tag2[p]);
f(rs(p),mid+1,r,tag[p],tag2[p]);
tag[p]=0;
tag2[p]=0;
}
inline void update(ll nl,ll nr,ll l,ll r,ll p,ll k)
{
if(nl<=l&&r<=nr)
{
ans[p]+=k;
tag[p]+=k;
return;
}
push_down(p,l,r);
ll mid=(l+r)>>1;
if(nl<=mid)update(nl,nr,l,mid,ls(p),k);
if(nr>mid) update(nl,nr,mid+1,r,rs(p),k);
push_up(p);
}
inline void update2(ll nl,ll nr,ll l,ll r,ll p,ll k)
{
if(nl<=l&&r<=nr)
{
ans[p]=k;
tag[p]=k;
tag2[p]=1;
return;
}
push_down(p,l,r);
ll mid=(l+r)>>1;
if(nl<=mid)update2(nl,nr,l,mid,ls(p),k);
if(nr>mid) update2(nl,nr,mid+1,r,rs(p),k);
push_up(p);
}
ll query(ll q_x,ll q_y,ll l,ll r,ll p)
{
ll res=-1000000;
if(q_x<=l&&r<=q_y)return ans[p];
ll mid=(l+r)>>1;
push_down(p,l,r);
if(q_x<=mid)res=max(res,query(q_x,q_y,l,mid,ls(p)));
if(q_y>mid) res=max(res,query(q_x,q_y,mid+1,r,rs(p)));
return res;
}
int main()
{
ll a1,b,c,d,e,f;
scan();
build(1,1,n);
while(m--)
{
scanf("%lld",&a1);
switch(a1)
{
case 1:{
scanf("%lld%lld%lld",&b,&c,&d);
update2(b,c,1,n,1,d);
break;
}
case 2:{
scanf("%lld%lld%lld",&b,&c,&d);
update(b,c,1,n,1,d);
break;
}
case 3:{
scanf("%lld%lld",&e,&f);
printf("%lld\n",query(e,f,1,n,1));
break;
}
}
}
return 0;
}