DLDZD @ 2024-10-15 16:32:36
#include<bits/stdc++.h>
#define int long long
#define max(a,b) (a>b? a:b);
using namespace std;
const int N=1e6;
struct tree{
int l,r,maxn=-(1e18+1);
int num;
int add;
int lazy;
int lazysum;
}t[N*4];
int a[N],n,m,mod;
void build(int p,int l,int r){
t[p].l=l; t[p].r=r;
if(l==r){
t[p].maxn=a[l];
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
t[p].maxn=max(t[p<<1].maxn,t[p<<1|1].maxn);
return ;
}
void spread(int p){
if(t[p].lazy){
t[p<<1].maxn=t[p<<1|1].maxn=t[p].maxn;
t[p].lazy=0;
}
t[p<<1].maxn+=t[p].add;
t[p<<1|1].maxn+=t[p].add;
t[p<<1].add+=t[p].add;
t[p<<1|1].add+=t[p].add;
t[p].add=0;
return ;
}
void update(int p,int l,int r,int k){
if(l<=t[p].l&&r>=t[p].r){
t[p].maxn+=k;
t[p].add+=k;
return ;
}
spread(p);
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) update(p<<1,l,r,k);
if(mid<r) update(p<<1|1,l,r,k);
t[p].maxn=max(t[p<<1].maxn,t[p<<1|1].maxn);
}
void change(int p,int l,int r,int k){
if(l<=t[p].l&&r>=t[p].r){
t[p].maxn=k;
t[p].add=0;
t[p].lazy=1;
return ;
}
spread(p);
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) change(p<<1,l,r,k);
if(mid<r) change(p<<1|1,l,r,k);
t[p].maxn=max(t[p<<1].maxn,t[p<<1|1].maxn);
}
int ask(int p,int l,int r){
if(l<=t[p].l&&r>=t[p].r){
return t[p].maxn;
}
spread(p);
int mid=(t[p].l+t[p].r)>>1;
int ans=-(1e18+1);
if(l<=mid) ans=max(ans,ask(p<<1,l,r));
if(mid<r) ans=max(ans,ask(p<<1|1,l,r));
return ans;
}
int read(){
int x=0,f=1; char c;
c=getchar_unlocked();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar_unlocked();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar_unlocked();
}
return x*f;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
n=read();m=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
build(1,1,n);
for(int i=1;i<=m;i++){
int opt=read(),x=read(),y=read(),k;
if(opt==1){
k=read();
change(1,x,y,k);
}
else if(opt==2){
k=read();
update(1,x,y,k);
}
else{
printf("%lld\n",ask(1,x,y));
}
}
return 0;
}
by 114514xxx @ 2024-10-15 16:38:46
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6;
struct tree{
int l,r,maxn=-(1e18+1);
int num;
int add;
int lazy;
int lazysum;
}t[N*4];
int a[N],n,m,mod;
void build(int p,int l,int r){
t[p].l=l; t[p].r=r;
if(l==r){
t[p].maxn=a[l];
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
t[p].maxn=max(t[p<<1].maxn,t[p<<1|1].maxn);
return ;
}
void spread(int p){
if(t[p].lazy){
t[p<<1].lazy=t[p<<1|1].lazy=t[p].lazy;
t[p<<1].maxn=t[p<<1|1].maxn=t[p].maxn;
t[p].lazy=0;
t[p].add=0;
return;
}
t[p<<1].maxn+=t[p].add;
t[p<<1|1].maxn+=t[p].add;
t[p<<1].add+=t[p].add;
t[p<<1|1].add+=t[p].add;
t[p].add=0;
return ;
}
void update(int p,int l,int r,int k){
if(l<=t[p].l&&r>=t[p].r){
t[p].maxn+=k;
t[p].add+=k;
return ;
}
spread(p);
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) update(p<<1,l,r,k);
if(mid<r) update(p<<1|1,l,r,k);
t[p].maxn=max(t[p<<1].maxn,t[p<<1|1].maxn);
}
void change(int p,int l,int r,int k){
if(l<=t[p].l&&r>=t[p].r){
t[p].maxn=k;
t[p].add=0;
t[p].lazy=1;
return ;
}
spread(p);
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) change(p<<1,l,r,k);
if(mid<r) change(p<<1|1,l,r,k);
t[p].maxn=max(t[p<<1].maxn,t[p<<1|1].maxn);
}
int ask(int p,int l,int r){
if(l<=t[p].l&&r>=t[p].r){
return t[p].maxn;
}
spread(p);
int mid=(t[p].l+t[p].r)>>1;
int ans=-(1e18+1);
if(l<=mid) ans=max(ans,ask(p<<1,l,r));
if(mid<r) ans=max(ans,ask(p<<1|1,l,r));
return ans;
}
int read(){
int x=0,f=1; char c;
c=getchar_unlocked();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar_unlocked();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar_unlocked();
}
return x*f;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
n=read();m=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
build(1,1,n);
for(int i=1;i<=m;i++){
int opt=read(),x=read(),y=read(),k;
if(opt==1){
k=read();
change(1,x,y,k);
}
else if(opt==2){
k=read();
update(1,x,y,k);
}
else{
printf("%lld\n",ask(1,x,y));
}
}
return 0;
}
by 114514xxx @ 2024-10-15 16:42:26
手写 max太慢了。