Mr_yeh @ 2024-10-29 19:40:31
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=(int)1e6+10;
struct node{
int l,r,val,lazy1,lazy2;
}t[N*4];
int a[N],x,flag;
void build(int u,int l,int r){
t[u].l=l;t[u].r=r;
if(l==r){
t[u].lazy1=a[l];
t[u].val=a[l];
return;
}
int mid=(t[u].l+t[u].r)/2;
build(u*2,l,mid);
build(u*2+1,mid+1,r);
t[u].val=max(t[u*2].val,t[u*2+1].val);
}
void pushdown1(int u){
if(!t[u].lazy1) return;
t[u*2].lazy1=t[u].lazy1;
t[u*2+1].lazy1=t[u].lazy1;
t[u*2].val=t[u*2].lazy1;
t[u*2+1].val=t[u*2+1].lazy1;
t[u].lazy1=0;
}
void pushdown2(int u){
if(!t[u].lazy2) return;
t[u*2].lazy2+=t[u].lazy2;
t[u*2+1].lazy2+=t[u].lazy2;
t[u*2].val=t[u*2].lazy1;
t[u*2+1].val=t[u*2+1].lazy1;
t[u*2].val+=(t[u*2].r-t[u*2].l+1)*t[u*2].lazy2;
t[u*2+1].val+=(t[u*2+1].r-t[u*2+1].l+1)*t[u*2+1].lazy2;
t[u].lazy2=0;
}
void modify1(int u,int l,int r){
if(t[u].l>=l&&t[u].r<=r){
t[u].lazy1=x;
t[u].val=x;
return;
}
pushdown2(u);
pushdown1(u);
int mid=(t[u].l+t[u].r)/2;
if(l<=mid) modify1(u*2,l,r);
if(r>mid) modify1(u*2+1,l,r);
t[u].val=max(t[u*2].val,t[u*2+1].val);
}
void modify2(int u,int l,int r){
if(t[u].l>=l&&t[u].r<=r){
t[u].lazy2+=x;
t[u].val=t[u].lazy1;
t[u].val+=(t[u].r-t[u].l+1)*t[u].lazy2;
return;
}
pushdown1(u);
pushdown2(u);
int mid=(t[u].l+t[u].r)/2;
if(l<=mid) modify2(u*2,l,r);
if(r>mid) modify2(u*2+1,l,r);
t[u].val=max(t[u*2].val,t[u*2+1].val);
}
int query(int u,int L,int R){
if(t[u].l>R||t[u].r<L) return 0;
if(t[u].l>=L&&t[u].r<=R) return t[u].val;
if(flag){
pushdown2(u);
pushdown1(u);
}else{
pushdown1(u);
pushdown2(u);
}
int mid=(t[u].l+t[u].r)/2,ans=INT_MIN;
if(L<=mid) ans=query(u*2,L,R);
if(R>mid) ans=max(ans,query(u*2+1,L,R));
return ans;
}
signed main(){
int n,q;
scanf("%lld%lld",&n,&q);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
build(1,1,n);
while(q--){
int op,l,r;
scanf("%lld",&op);
if(op==1){
scanf("%lld%lld%lld",&l,&r,&x);
modify1(1,l,r);
flag=0;
}else if(op==2){
scanf("%lld%lld%lld",&l,&r,&x);
modify2(1,l,r);
flag=1;
}else{
scanf("%lld%lld",&l,&r);
printf("%lld\n",query(1,l,r));
}
}
return 0;
}
by qdl66666666 @ 2024-10-29 21:08:15
终于改完了^0^
问题1：最大值的增加不能像区间求和一样加上(r-l+1)*x ,最大值应该直接加x
问题2：修改标记会覆盖之前的增加标记，增加标记应置为0
问题3：修改有可能把数修改成0，所以初值应赋成一个不会修改成的数字，如LONG_MIN
问题4：对于本题目来说，INT_MIN太小，需使用LONG_MIN，不然只有50
问题5：下传时先下传修改标记，他会覆盖掉还未生效的增加标记，modify和query时正常下传即可
#include<bits/stdc++.h>
using namespace std;
#define int long long//不建议用，空间翻倍，并且longlong取模慢
const int N=1e6+10;
struct node{
int l,r,val,lazy1,lazy2;//lazy1:修改标记，2:增加标记
//建议这样写：maxn(最大值) cover_tag(上) add_tag(上)
node(){//构造函数(给结构体赋初值)
val=lazy1=LONG_MIN;//cover标记有可能是0,所以要设为一个极值
lazy2=0;
}
}t[N*4];
int a[N],x,flag;
void build(int u,int l,int r){//建树没问题^0^
t[u].l=l;t[u].r=r;
if(l==r){
t[u].val=a[l];
return;
}
int mid=(t[u].l+t[u].r)/2;
build(u*2,l,mid);
build(u*2+1,mid+1,r);
t[u].val=max(t[u*2].val,t[u*2+1].val);
}
void pushdown1(int u){//cover下传,cover标记变为x,最大值变为x,add标记失效变为0
if(t[u].lazy1==LONG_MIN) return;
t[u*2].lazy1=t[u].lazy1;
t[u*2+1].lazy1=t[u].lazy1;
t[u*2].val=t[u].lazy1;
t[u*2+1].val=t[u].lazy1;
t[u*2].lazy2=0;//add变成0
t[u*2+1].lazy2=0;//add变成0
t[u].lazy1=LONG_MIN;//标记传完,恢复极值
}
void pushdown2(int u){//add下传,add标记加x,最大值也加x
if(!t[u].lazy2) return;
t[u*2].lazy2+=t[u].lazy2;
t[u*2+1].lazy2+=t[u].lazy2;
// t[u*2].val=t[u*2].lazy1;
// t[u*2+1].val=t[u*2+1].lazy1;
t[u*2].val+=t[u].lazy2;
t[u*2+1].val+=t[u].lazy2;//最大值加x
//不是区间求和，求最大值要加 x
// t[u*2].val+=(t[u*2].r-t[u*2].l+1)*t[u*2].lazy2;
// t[u*2+1].val+=(t[u*2+1].r-t[u*2+1].l+1)*t[u*2+1].lazy2;
t[u].lazy2=0;
}
void modify1(int u,int l,int r){//modify_cover操作
if(t[u].l>=l&&t[u].r<=r){
t[u].lazy1=x;
t[u].lazy2=0;//别忘了add标记清空
t[u].val=x;
return;
}
pushdown1(u);
pushdown2(u);
int mid=(t[u].l+t[u].r)/2;
if(l<=mid) modify1(u*2,l,r);
if(r>mid) modify1(u*2+1,l,r);
t[u].val=max(t[u*2].val,t[u*2+1].val);
}
void modify2(int u,int l,int r){//modify_add操作
if(t[u].l>=l&&t[u].r<=r){
t[u].lazy2+=x;
//t[u].val=t[u].lazy1;
//t[u].val+=(t[u].r-t[u].l+1)*t[u].lazy2;求最大值，不是求和
//add一个x，最大值也增加x
t[u].val+=x;
return;
}
pushdown1(u);
pushdown2(u);
int mid=(t[u].l+t[u].r)/2;
if(l<=mid) modify2(u*2,l,r);
if(r>mid) modify2(u*2+1,l,r);
t[u].val=max(t[u*2].val,t[u*2+1].val);
}
int query(int u,int L,int R){
if(t[u].l>R||t[u].r<L) return 0;
if(t[u].l>=L&&t[u].r<=R) return t[u].val;
// if(flag){
// pushdown2(u);
// pushdown1(u);
// }else{
// pushdown1(u);
// pushdown2(u);
// }
pushdown1(u);
pushdown2(u);//正常下传即可
int mid=(t[u].l+t[u].r)/2,ans=LONG_MIN;//INT_MIN不够小只能得到 50
if(L<=mid) ans=max(ans,query(u*2,L,R));
if(R>mid) ans=max(ans,query(u*2+1,L,R));
return ans;
}
signed main(){
int n,q;
scanf("%lld%lld",&n,&q);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
build(1,1,n);
while(q--){
int op,l,r;
scanf("%lld",&op);
if(op==1){
scanf("%lld%lld%lld",&l,&r,&x);
modify1(1,l,r);//fix
//flag=0;
}else if(op==2){
scanf("%lld%lld%lld",&l,&r,&x);
modify2(1,l,r);//add
//flag=1;
}else{
scanf("%lld%lld",&l,&r);
printf("%lld\n",query(1,l,r));
}
}
return 0;
}by qdl66666666 @ 2024-10-29 21:44:45
个人感觉这个要简洁一点，按你的写法，把一些重复写的东西写进了函数里
#include<bits/stdc++.h>
#define mid ((z[u].l + z[u].r)/2) // == z[u].l+z[u].r>>1
#define lson u*2,l,r//u*2 == u<<1
#define rson u*2+1,l,r//u*2+1 == u<<1|1
#define ll long long
using namespace std;
const int N=1e6+100;
int n,q,a[N],x;
struct node{
ll l,r,maxn,cover_tag,add_tag;
node(){
maxn=cover_tag=LONG_MIN;
add_tag=0;
}
}z[N*4];
//数据结构题最好用较为快速的读入方式
inline int read();//快读有模板，放主函数后面了
void updata(int u){
z[u].maxn = max(z[u*2].maxn,z[u*2+1].maxn);
}
void build(int u,ll l,ll r){
z[u].l = l , z[u].r = r;
if(l==r){
z[u].maxn = a[l];
return;
}
build(u*2,l,mid);
build(u*2+1,mid+1,r);
updata(u);
}
void cover(int u,ll v){
z[u].cover_tag = v;
z[u].add_tag = 0;
z[u].maxn = v;
}
void add(int u,ll v){
z[u].add_tag += v;
z[u].maxn += v;
}
void push_down(int u){
if(z[u].cover_tag != LONG_MIN){
cover(u*2,z[u].cover_tag); cover(u*2+1,z[u].cover_tag);
z[u].cover_tag = LONG_MIN;
}
if(z[u].add_tag!=0){
add(u*2,z[u].add_tag); add(u*2+1,z[u].add_tag);
z[u].add_tag = 0;
}
}
void modify_cover(int u,ll l,ll r){
if(l <= z[u].l && z[u].r <= r){
cover(u,x);
return;
}
push_down(u);
if(l <= mid) modify_cover(lson);
if(mid + 1 <= r) modify_cover(rson);//等价于 if(mid < r) modify_cover(u*2+1,l,r)
updata(u);
}
void modify_add(int u,ll l,ll r){
if(l <= z[u].l && z[u].r <= r){
add(u,x);
return;
}
push_down(u);
if(l <= mid) modify_add(lson);
if(mid + 1 <= r) modify_add(rson);
updata(u);
}
ll query(int u,ll l,ll r){
if(l <= z[u].l && z[u].r <= r){
return z[u].maxn;
}
push_down(u);
ll res = LONG_MIN;//res --> result 结果
if(l <= mid) res = max(res,query(lson));
if(mid + 1 <= r) res = max(res,query(rson));
return res;
}
int main(){
n=read(),q=read();
for(int i=1;i<=n;i++) a[i]=read();
build(1,1,n);
while(q--){
int opt=read(),l=read(),r=read();
if(opt==1){
x=read();
modify_cover(1,l,r);
}
else if(opt==2){
x=read();
modify_add(1,l,r);
}
else{
cout<<query(1,l,r)<<"\n";
}
}
return 0;
}
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}by Mr_yeh @ 2024-10-31 18:51:59
感谢大佬关注了关注了
by qdl66666666 @ 2024-10-31 21:07:40
@Mr_yeh ^0^ okok