simonG @ 2022-06-11 12:32:54
#include<algorithm>
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const ll N=1e6,inf=1e12;
ll n,m,a[N],mx[4*N],tagsum[4*N],tagmax[4*N];
void build(ll p,ll l,ll r) {
if(l==r) {
mx[p]=a[l];
return ;
}
ll mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
tagmax[p]=-inf;
mx[p]=max(mx[p*2],mx[p*2+1]);
}
void add(ll p,ll l,ll r,ll v) {
if(tagmax[p]!=-inf) tagmax[p]+=v;
tagsum[p]+=v;
mx[p]+=v;
}
void maxi(ll p,ll l,ll r,ll v) {
mx[p]=tagmax[p]=v;
tagsum[p]=0;
}
void pushdown(ll p,ll l,ll r) {
ll mid=(l+r)/2;
if(tagmax[p]!=-inf) {
maxi(p*2,l,mid,tagmax[p]);
maxi(p*2+1,mid+1,r,tagmax[p]);
}
add(p*2,l,mid,tagsum[p]);
add(p*2+1,mid+1,r,tagsum[p]);
tagmax[p]=-inf;
tagsum[p]=0;
}
void modifysum(ll p,ll l,ll r,ll x,ll y,ll v) {
if(x<=l&&r<=y) {
add(p,l,r,v);
return ;
}
pushdown(p,l,r);
ll mid=(l+r)/2;
if(x<=mid) modifysum(p*2,l,mid,x,y,v);
if(y>mid) modifysum(p*2+1,mid+1,r,x,y,v);
mx[p]=max(mx[p*2],mx[p*2+1]);
}
void modifymax(ll p,ll l,ll r,ll x,ll y,ll v) {
if(x<=l&&r<=y) {
maxi(p,l,r,v);
return ;
}
pushdown(p,l,r);
ll mid=(l+r)/2;
if(x<=mid) modifymax(p*2,l,mid,x,y,v);
if(y>mid) modifymax(p*2+1,mid+1,r,x,y,v);
mx[p]=max(mx[p*2],mx[p*2+1]);
}
ll query(ll p,ll l,ll r,ll x,ll y) {
if(x<=l&&r<=y) return mx[p];
pushdown(p,l,r);
ll mid=(l+r)/2,res=-inf;
if(x<=mid) res=max(res,query(p*2,l,mid,x,y));
if(y>mid) res=max(res,query(p*2+1,mid+1,r,x,y));
return res;
}
signed main() {
scanf("%lld %lld",&n,&m);
for(ll i=1; i<=n; i++)
scanf("%lld",&a[i]);
build(1,1,n);
for(; m; m--) {
ll x,y,k,opt;
scanf("%lld %lld %lld",&opt,&x,&y);
if(opt==1) {
scanf("%lld",&k);
modifymax(1,1,n,x,y,k);
} else if(opt==2) {
scanf("%lld",&k);
modifysum(1,1,n,x,y,k);
} else {
printf("%lld\n",query(1,1,n,x,y));
}
}
return 0;
}by HINODE @ 2022-06-11 13:01:32
#include<bits/stdc++.h>
#define int long long
#define lf now<<1
#define rf now<<1|1
using namespace std;
const int size=1510100,T=-21457199871;
int a[size],n,m,o;
struct cjhakioi{
int l,r,pre,t1=0,t2=T;
}f[size<<1];
void build_tree(int now,int l,int r){
f[now].l=l;f[now].r=r;
if(l==r){
f[now].pre=a[l];
return;
}
int mid=(l+r)>>1;
build_tree(lf,l,mid);
build_tree(rf,mid+1,r);
f[now].pre=max(f[lf].pre,f[rf].pre);
}
void _(int now){
if(f[now].t2!=T){
f[lf].t1=f[rf].t1=0;
f[lf].t2=f[rf].t2=f[lf].pre=f[rf].pre=f[now].t2;
f[now].t2=T;
}
if(f[now].t1){
f[lf].t1+=f[now].t1;
f[rf].t1+=f[now].t1;
f[lf].pre+=f[now].t1;
f[rf].pre+=f[now].t1;
f[now].t1=0;
}
return;
}
void add_num(int now,int l,int r,int num){
if(l<=f[now].l&&r>=f[now].r){
f[now].t1+=num;
f[now].pre+=num;
return;
}
_(now);
int mid=f[now].l+f[now].r>>1;
if(l<=mid)add_num(lf,l,r,num);
if(r>mid)add_num(rf,l,r,num);
f[now].pre=max(f[lf].pre,f[rf].pre);
}
void set_num(int now,int l,int r,int num){
if(l<=f[now].l&&r>=f[now].r){
f[now].pre=num;
f[now].t1=0;
f[now].t2=num;
return;
}
_(now);
int mid=f[now].l+f[now].r>>1;
if(l<=mid)set_num(lf,l,r,num);
if(r>mid)set_num(rf,l,r,num);
f[now].pre=max(f[lf].pre,f[rf].pre);
}
int ask(int now,int l,int r){
if(l<=f[now].l&&r>=f[now].r)return f[now].pre;
_(now);
int mid=f[now].l+f[now].r>>1,ans=-191919191919;
if(l<=mid)ans=max(ans,ask(lf,l,r));
if(r>mid)ans=max(ans,ask(rf,l,r));
return ans;
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
build_tree(1,1,n);
for(int i=1;i<=m;i++){
int q,x,y,z;
scanf("%lld%lld%lld",&q,&x,&y);
if(q==1){
scanf("%lld",&z);
set_num(1,x,y,z);
}
else if(q==2){
scanf("%lld",&z);
add_num(1,x,y,z);
}
else printf("%lld\n",ask(1,x,y));
}
return 0;
}by HINODE @ 2022-06-11 13:09:17
删了第20行可以9AC1TLE
by HINODE @ 2022-06-11 13:21:12
再把N加上1可以AC