PF_flute @ 2024-12-06 18:29:37
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e11;
int n,m;
int a[1001000];
struct node{
int l,r,dat,add,rev;
}tree[4001000];
int op,l,r,k;
void build(int p,int l,int r){
tree[p].l=l,tree[p].r=r,tree[p].rev=INF;
if(l==r){
tree[p].dat=a[l];
return ;
}
int mid=(tree[p].l+tree[p].r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
tree[p].dat=max(tree[p*2].dat,tree[p*2+1].dat);
return ;
}
void down(int p){
if(tree[p].rev!=INF){
int d=tree[p].rev;
tree[p*2].dat=d;
tree[p*2+1].dat=d;
tree[p*2].rev=d;
tree[p*2+1].rev=d;
tree[p*2].add=0;
tree[p*2+1].add=0;
tree[p].rev=INF;
}
if(tree[p].add!=0){
int d=tree[p].add;
tree[p*2].dat+=d;
tree[p*2+1].dat+=d;
tree[p*2].add+=d;
tree[p*2+1].add+=d;
tree[p].add=0;
}
return ;
}
void revupdate(int p,int l,int r,int k){
if(tree[p].l>=l&&tree[p].r<=r){
tree[p].dat=k;
tree[p].rev=k;
tree[p].add=0;
return ;
}
down(p);
int mid=(tree[p].l+tree[p].r)/2;
if(l<=mid)
revupdate(p*2,l,r,k);
if(r>mid)
revupdate(p*2+1,l,r,k);
tree[p].dat=max(tree[p*2].dat,tree[p*2+1].dat);
return ;
}
void addupdate(int p,int l,int r,int k){
if(tree[p].l>=l&&tree[p].r<=r){
tree[p].dat+=k;
tree[p].add+=k;
return ;
}
down(p);
int mid=(tree[p].l+tree[p].r)/2;
if(l<=mid)
addupdate(p*2,l,r,k);
if(r>mid)
addupdate(p*2+1,l,r,k);
tree[p].dat=max(tree[p*2].dat,tree[p*2+1].dat);
return ;
}
int ask(int p,int l,int r){
if(tree[p].l>=l&&tree[p].r<=r)
return tree[p].dat;
down(p);
int ans=0;
int mid=(tree[p].l+tree[p].r)/2;
if(l<=mid)
ans+=ask(p*2,l,r);
if(r>mid)
ans+=ask(p*2+1,l,r);
return ans;
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
build(1,1,n);
while(m--){
scanf("%lld",&op);
if(op==1){
scanf("%lld%lld%lld",&l,&r,&k);
revupdate(1,l,r,k);
}
if(op==2){
scanf("%lld%lld%lld",&l,&r,&k);
addupdate(1,l,r,k);
}
if(op==3){
scanf("%lld%lld",&l,&r);
printf("%lld\n",ask(1,l,r));
}
}
return 0;
}by LiujunjiaNC @ 2024-12-06 18:49:34
@PF_flute你ask函数是查询区间
by LiujunjiaNC @ 2024-12-06 18:50:59
@PF_flute因为是求最大值所以
by sdjjdjdjdjd @ 2024-12-06 18:51:51
求区间最值，你ask函数里用的是+=
by LiujunjiaNC @ 2024-12-06 18:52:31
好像还有一些问题，你可以看下我的代码
#include<iostream>
#define none -1145141919180
using namespace std;
typedef long long LL;
const int M = 1e6 +10;
int a[M];
struct node{
int l,r;
LL max;
LL add_laze,cover_laze;
node(){add_laze = 0,cover_laze = none;}
}tree[M<<2];
void buildTree(int k,int l,int r){
tree[k].l = l,tree[k].r = r;
if(l==r){
tree[k].max = a[l];
return;
}
int mid = (l+r)>>1;
int lchild = k<<1,rchild = k<<1|1;
buildTree(lchild,l,mid);
buildTree(rchild,mid+1,r);
tree[k].max = max(tree[lchild].max,tree[rchild].max);
}
void pushdown(int k){
int lchild = k<<1,rchild = k<<1|1;
if(tree[k].cover_laze!=none){
tree[lchild].max = tree[k].cover_laze;
tree[rchild].max = tree[k].cover_laze;
tree[lchild].add_laze = 0;
tree[rchild].add_laze = 0;
tree[lchild].cover_laze = tree[k].cover_laze;
tree[rchild].cover_laze = tree[k].cover_laze;
tree[k].cover_laze = none;
}
if(!tree[k].add_laze)return;
tree[lchild].max += tree[k].add_laze;
tree[rchild].max += tree[k].add_laze;
tree[lchild].add_laze += tree[k].add_laze;
tree[rchild].add_laze += tree[k].add_laze;
tree[k].add_laze = 0;
}
void add(int k,int l,int r,int x){
if(l<=tree[k].l&&r>=tree[k].r){
tree[k].max += x;
tree[k].add_laze += x;
return;
}
pushdown(k);
int mid = (tree[k].l+tree[k].r)>>1;
int lchild = k<<1,rchild = k<<1|1;
if(l<=mid) add(lchild,l,r,x);
if(r>mid) add(rchild,l,r,x);
tree[k].max = max(tree[lchild].max,tree[rchild].max);
}
void cover(int k,int l,int r,int x){
if(l<=tree[k].l&&r>=tree[k].r){
tree[k].max = x;
tree[k].add_laze = 0;
tree[k].cover_laze = x;
return;
}
pushdown(k);
int mid = (tree[k].l+tree[k].r)>>1;
int lchild = k<<1,rchild = k<<1|1;
if(l<=mid) cover(lchild,l,r,x);
if(r>mid) cover(rchild,l,r,x);
tree[k].max = max(tree[lchild].max,tree[rchild].max);
}
LL query(int k,int l,int r){
if(l<=tree[k].l&&r>=tree[k].r){
return tree[k].max;
}
pushdown(k);
LL res = none;
int mid = (tree[k].l+tree[k].r)>>1;
int lchild = k<<1,rchild = k<<1|1;
if(l<=mid) res = max(res,query(lchild,l,r));
if(r>mid) res = max(res,query(rchild,l,r));
return res;
}
void print_tree(int k){
cout<<k<<":["<<tree[k].l<<","<<tree[k].r<<"] -\t"<<tree[k].max<<endl;
int lchild = k<<1,rchild = k<<1|1;
if(tree[lchild].l>0)print_tree(lchild);
if(tree[rchild].r>0)print_tree(rchild);
return;
}
int main(){
int n,q;
scanf("%d %d",&n,&q);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
buildTree(1,1,n);
// print_tree(1);
int op,l,r,x;
for(int i=1;i<=q;i++){
scanf("%d %d %d",&op,&l,&r);
if(op==1){
scanf("%d",&x);
cover(1,l,r,x);
}else if(op==2){
scanf("%d",&x);
add(1,l,r,x);
}else{
// cout<<"-------print:";
printf("%lld\n",query(1,l,r));
}
}
return 0;
}
/*
6 6
1 1 4 5 1 4
2 3 4 2
3 1 4
3 2 3
3 1 6
*/
by S14819 @ 2024-12-07 08:50:42
菜
by PF_flute @ 2024-12-07 08:56:41
@LiujunjiaNC@sdjjdjdjdjd 蟹蟹