LITFLYR @ 2024-07-29 09:53:50
最后一个点为什么会T啊要破防了QAQ
#include<bits/stdc++.h>
using namespace std;
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
int n,q,a[1000005];
int op,x,y,k;
int tre[4000005],lazy_add[4000005],lazy_cha[4000005];
void push_up(int f){
tre[f]=max(tre[ls(f)],tre[rs(f)]);
}
void build(int f,int l,int r){
if(l==r){
tre[f]=a[l];
return ;
}
int mid=(l+r)>>1;
build(ls(f),l,mid);
build(rs(f),mid+1,r);
push_up(f);
}
void push_down(int f,int l,int r){
if(lazy_cha[ls(f)]==0) lazy_add[ls(f)]+=lazy_add[f];
else lazy_cha[ls(f)]+=lazy_add[f];
if(lazy_cha[rs(f)]==0) lazy_add[rs(f)]+=lazy_add[f];
else lazy_cha[rs(f)]+=lazy_add[f];
if(lazy_cha[f]!=0){
lazy_cha[rs(f)]=lazy_cha[f];
lazy_cha[ls(f)]=lazy_cha[f];
lazy_add[rs(f)]=0;
lazy_add[ls(f)]=0;
}
int mid=(l+r)>>1;
if(lazy_cha[f]==0){
tre[ls(f)]+=lazy_add[f];
tre[rs(f)]+=lazy_add[f];
}
else{
tre[ls(f)]=lazy_cha[f];
tre[rs(f)]=lazy_cha[f];
}
lazy_add[f]=lazy_cha[f]=0;
}
void cha(int f,int l,int r,int x,int y,int k){
push_down(f,l,r);
if(x<=l&&r<=y){
tre[f]=k;
lazy_cha[f]=k;
return ;
}
int mid=(l+r)>>1;
if(x<=mid) cha(ls(f),l,mid,x,y,k);
if(y>mid) cha(rs(f),mid+1,r,x,y,k);
push_up(f);
}
void add(int f,int l,int r,int x,int y,int k){
push_down(f,l,r);
if(x<=l&&r<=y){
tre[f]+=k;
lazy_add[f]+=k;
return ;
}
int mid=(l+r)>>1;
if(x<=mid) add(ls(f),l,mid,x,y,k);
if(y>mid) add(rs(f),mid+1,r,x,y,k);
push_up(f);
}
int query(int f,int l,int r,int x,int y){
if(x<=l&&r<=y){
return tre[f];
}
push_down(f,l,r);
int mid=(l+r)>>1,ans=0;
if(x<=mid) ans=max(ans,query(ls(f),l,mid,x,y));
if(y>mid) ans=max(ans,query(rs(f),mid+1,r,x,y));
return ans;
}
int main(){
cin >> n >> q;
for(int i=1;i<=n;i++) cin >> a[i];
build(1,1,n);
while(q--){
cin >> op;
if(op==1){
cin >> x >> y >> k;
cha(1,1,n,x,y,k);
}
else if(op==2){
cin >> x >> y >> k;
add(1,1,n,x,y,k);
}
else{
cin >> x >> y;
cout << query(1,1,n,x,y) << endl;
}
}
}by Ace_FutureDream @ 2024-07-29 09:58:08
@LITFLYR 关闭一下同步流，加上：
ios::sync_with_stdio(false)
cin.tie(0);cout.tie(0);by LITFLYR @ 2024-07-29 10:00:39
@Ace_FutureDream 但是我还有50分的wa QAQ
by Ace_FutureDream @ 2024-07-29 10:13:39
@LITFLYR 目前60分了：
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
int n,q,a[1000005];
int op,x,y,k;
int tre[4000005],lazy_add[4000005],lazy_cha[4000005];
void push_up(int f){
tre[f]=max(tre[ls(f)],tre[rs(f)]);
}
void build(int f,int l,int r){
lazy_cha[f]=-1e18;
if(l==r){
tre[f]=a[l];
return ;
}
int mid=(l+r)>>1;
build(ls(f),l,mid);
build(rs(f),mid+1,r);
push_up(f);
}
void push_down(int f,int l,int r){
if(lazy_cha[f]!=-1e18){
lazy_cha[rs(f)]=lazy_cha[f];
lazy_cha[ls(f)]=lazy_cha[f];
tre[ls(f)]=lazy_cha[f];
tre[rs(f)]=lazy_cha[f];
lazy_add[f]=0;
lazy_cha[f]=-1e18;
}
if(lazy_add[f]!=0){
lazy_add[ls(f)]+=lazy_add[f];
lazy_add[rs(f)]+=lazy_add[f];
tre[ls(f)]+=lazy_add[f];
tre[rs(f)]+=lazy_add[f];
lazy_add[f]=0;
}
}
void cha(int f,int l,int r,int x,int y,int k){
if(l>y||r<x)return;
if(x<=l&&r<=y){
tre[f]=k;
lazy_cha[f]=k;
return ;
}
push_down(f,l,r);
int mid=(l+r)>>1;
cha(ls(f),l,mid,x,y,k);
cha(rs(f),mid+1,r,x,y,k);
push_up(f);
}
void add(int f,int l,int r,int x,int y,int k){
if(l>y||r<x)return;
if(x<=l&&r<=y){
tre[f]+=k;
lazy_add[f]+=k;
return ;
}
push_down(f,l,r);
int mid=(l+r)>>1;
add(ls(f),l,mid,x,y,k);
add(rs(f),mid+1,r,x,y,k);
push_up(f);
}
int query(int f,int l,int r,int x,int y){
if(l>y||r<x)return -1e18;
if(x<=l&&r<=y){
return tre[f];
}
push_down(f,l,r);
int mid=(l+r)>>1,ans=-1e18;
ans=max(ans,query(ls(f),l,mid,x,y));
ans=max(ans,query(rs(f),mid+1,r,x,y));
return ans;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> q;
for(int i=1;i<=n;i++) cin >> a[i];
build(1,1,n);
while(q--){
cin >> op;
if(op==1){
cin >> x >> y >> k;
cha(1,1,n,x,y,k);
}
else if(op==2){
cin >> x >> y >> k;
add(1,1,n,x,y,k);
}
else{
cin >> x >> y;
cout << query(1,1,n,x,y) << endl;
}
}
}by Ace_FutureDream @ 2024-07-29 10:16:44
@LITFLYR AC了
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
int n,q,a[1000005];
int op,x,y,k;
int tre[4000005],lazy_add[4000005],lazy_cha[4000005];
void push_up(int f){
tre[f]=max(tre[ls(f)],tre[rs(f)]);
}
void build(int f,int l,int r){
lazy_cha[f]=-1e18;
if(l==r){
tre[f]=a[l];
return ;
}
int mid=(l+r)>>1;
build(ls(f),l,mid);
build(rs(f),mid+1,r);
push_up(f);
}
void push_down(int f,int l,int r){
if(lazy_cha[f]!=-1e18){
lazy_cha[rs(f)]=lazy_cha[f];lazy_add[rs(f)]=0;
lazy_cha[ls(f)]=lazy_cha[f];lazy_add[ls(f)]=0;
tre[ls(f)]=lazy_cha[f];
tre[rs(f)]=lazy_cha[f];
lazy_cha[f]=-1e18;
}
if(lazy_add[f]!=0){
lazy_add[ls(f)]+=lazy_add[f];
lazy_add[rs(f)]+=lazy_add[f];
tre[ls(f)]+=lazy_add[f];
tre[rs(f)]+=lazy_add[f];
lazy_add[f]=0;
}
}
void cha(int f,int l,int r,int x,int y,int k){
if(l>y||r<x)return;
if(x<=l&&r<=y){
tre[f]=k;
lazy_cha[f]=k;
lazy_add[f]=0;
return ;
}
push_down(f,l,r);
int mid=(l+r)>>1;
cha(ls(f),l,mid,x,y,k);
cha(rs(f),mid+1,r,x,y,k);
push_up(f);
}
void add(int f,int l,int r,int x,int y,int k){
if(l>y||r<x)return;
if(x<=l&&r<=y){
tre[f]+=k;
lazy_add[f]+=k;
return ;
}
push_down(f,l,r);
int mid=(l+r)>>1;
add(ls(f),l,mid,x,y,k);
add(rs(f),mid+1,r,x,y,k);
push_up(f);
}
int query(int f,int l,int r,int x,int y){
if(l>y||r<x)return -1e18;
if(x<=l&&r<=y){
return tre[f];
}
push_down(f,l,r);
int mid=(l+r)>>1,ans=-1e18;
ans=max(ans,query(ls(f),l,mid,x,y));
ans=max(ans,query(rs(f),mid+1,r,x,y));
return ans;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> q;
for(int i=1;i<=n;i++) cin >> a[i];
build(1,1,n);
while(q--){
cin >> op;
if(op==1){
cin >> x >> y >> k;
cha(1,1,n,x,y,k);
}
else if(op==2){
cin >> x >> y >> k;
add(1,1,n,x,y,k);
}
else{
cin >> x >> y;
cout << query(1,1,n,x,y) << endl;
}
}
}by LITFLYR @ 2024-07-29 10:31:28
@Ace_FutureDream 哇，谢谢你！关注了！（bushi