Firrel_qaq @ 2024-11-27 18:17:02
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#define int long long
using namespace std;
struct node{
int val,l,r,add,ex;
}tr[8000005];
int n,q;
int op,l,r,x;
int a[8000005];
void pushdown(int p){
if(tr[p].ex > -1e18){
tr[p * 2].val = tr[p * 2 + 1].val = tr[p].ex;
tr[p * 2].ex = tr[p * 2 + 1].ex = tr[p].ex;
tr[p * 2].add = tr[p * 2 + 1].add = 0;
tr[p].ex = -1e18;
}
tr[p * 2].val += tr[p].add;
tr[p * 2 + 1].val += tr[p].add;
tr[p * 2].add += tr[p].add;
tr[p * 2 + 1].add += tr[p].add;
return ;
}
void build(int p,int l,int r){
tr[p].l = l,tr[p].r = r,tr[p].ex = -1e18;
if(tr[p].l == tr[p].r){
tr[p].val = a[l];
return ;
}
int mid = (tr[p].l + tr[p].r) / 2;
build(p * 2,tr[p].l,mid);
build(p * 2 + 1,mid + 1,tr[p].r);
tr[p].val = max(tr[p * 2].val,tr[p * 2 + 1].val);
return ;
}
void exchange(int p,int l,int r,int k){
if(tr[p].l >= l && tr[p].r <= r){
tr[p].val = k;
tr[p].ex = k;
tr[p].add = 0;
return ;
}
pushdown(p);
int mid = (tr[p].l + tr[p].r) / 2;
if(mid >= l) exchange(p * 2,l,r,k);
if(mid < r) exchange(p * 2 + 1,l,r,k);
tr[p].val = max(tr[p * 2].val,tr[p * 2 + 1].val);
return ;
}
void add(int p,int l,int r,int k){
if(tr[p].l >= l && tr[p].r <= r){
tr[p].val += k;
tr[p].add += k;
return ;
}
pushdown(p);
int mid = (tr[p].l + tr[p].r) / 2;
if(mid >= l) add(p * 2,l,r,k);
if(mid < r) add(p * 2 + 1,l,r,k);
tr[p].val = max(tr[p * 2].val,tr[p * 2 + 1].val);
return ;
}
int found(int p,int l,int r){
if(tr[p].l >= l && tr[p].r <= r) return tr[p].val;
pushdown(p);
int ans = 0,mid = (tr[p].l + tr[p].r) / 2;
if(mid >= l) ans = found(p * 2,l,r);
if(mid < r) ans = max(found(p * 2 + 1,l,r),ans);
return ans;
}
signed main(){
scanf("%lld%lld",&n,&q);
for(int i = 1;i <= n;i++) scanf("%lld",&a[i]);
build(1,1,n);
for(int i = 1;i <= q;i++){
scanf("%lld%lld%lld",&op,&l,&r);
if(op == 1){
scanf("%lld",&x);
exchange(1,l,r,x);
}
else if(op == 2){
scanf("%lld",&x);
add(1,l,r,x);
}
else printf("%lld\n",found(1,l,r));
}
return 0;
}
by zzz13579zzz @ 2024-11-27 18:18:27
点权值可以是负的
by Firrel_qaq @ 2024-11-27 21:15:00
@zzz13579zzz 不知道为什么这个代码变成20分了，点权值是负的对这份代码有什么影响吗
by dengyifan @ 2024-11-27 21:28:43
我也50分......
#include<bits/stdc++.h>
using namespace std;
const long long N=1e7+10,inf=INT_MAX;
long long a[N*4],tree[N*4],tag[N*4],tag2[N*4],n,m;
long long ls(long long p){return (p<<1);}
long long rs(long long p){return (p<<1|1);}
void update(long long p)
{
tree[p]=max(tree[ls(p)],tree[rs(p)]);
}
void build(long long p,long long pl,long long pr)
{
tag2[p]=inf;
if(pl==pr)
{
tree[p]=a[pl];
return;
}
long long mid=(pl+pr)>>1;
build(ls(p),pl,mid);
build(rs(p),mid+1,pr);
update(p);
}
void tag_down(long long p)
{
tag[ls(p)]+=tag[p];
tree[ls(p)]+=tag[p];
tag[rs(p)]+=tag[p];
tree[rs(p)]+=tag[p];
tag[p]=0;
}
void tag_down2(long long p)
{
if(tag2[p]!=inf)
{
tag2[ls(p)]=tag2[p];
tag[ls(p)]=0;
tree[ls(p)]=tag2[p];
tag2[rs(p)]=tag2[p];
tag[rs(p)]=0;
tree[rs(p)]=tag2[p];
tag[p]=0;
tag2[p]=inf;
}
}
void change(long long l,long long r,long long p,long long pl,long long pr,long long d)
{
if(l<=pl&&pr<=r)
{
tag[p]+=d;
tree[p]+=d;
return;
}
tag_down2(p);
tag_down(p);
long long mid=(pl+pr)>>1;
if(l<=mid)
{
change(l,r,ls(p),pl,mid,d);
}
if(r>mid)
{
change(l,r,rs(p),mid+1,pr,d);
}
update(p);
}
void change2(long long l,long long r,long long p,long long pl,long long pr,long long d)
{
if(l<=pl&&pr<=r)
{
tag2[p]=d;
tree[p]=d;
tag[p]=0;
return;
}
tag_down2(p);
tag_down(p);
long long mid=(pl+pr)>>1;
if(l<=mid)
{
change2(l,r,ls(p),pl,mid,d);
}
if(r>mid)
{
change2(l,r,rs(p),mid+1,pr,d);
}
update(p);
}
long long sum(long long l,long long r,long long p,long long pl,long long pr)
{
if(l<=pl&&pr<=r)
{
return tree[p];
}
tag_down2(p);
tag_down(p);
long long res=-INT_MAX,mid=(pl+pr)>>1;
if(l<=mid)
{
res=max(res,sum(l,r,ls(p),pl,mid));
}
if(r>mid)
{
res=max(res,sum(l,r,rs(p),mid+1,pr));
}
return res;
}
int main()
{
cin>>n>>m;
for(long long i=1;i<=n;i++)
{
cin>>a[i];
}
build(1,1,n);
while(m--)
{
long long q,l,r,d;
cin>>q>>l>>r;
if(q==1)
{
cin>>d;
change2(l,r,1,1,n,d);
}
if(q==2)
{
cin>>d;
change(l,r,1,1,n,d);
}
if(q==3)
{
cout<<sum(l,r,1,1,n)<<"\n";
}
}
return 0;
}by zzz13579zzz @ 2024-11-27 22:05:35
@Firrel_qaq那你最大值赋初值0？
by zzz13579zzz @ 2024-11-27 22:22:48
@dengyifan也是一样的问题，-int_MAX 太大，建议使用LONG_LONG_MIN 或者-1e18
by Neokaye @ 2024-11-28 12:55:48
点权值为负会导致答案有可能小于0,ans=0就会出错
by dengyifan @ 2024-11-29 20:52:34
@zzz13579zzz 我改了，但60分......
提交记录
#include<bits/stdc++.h>
using namespace std;
const long long N=1e7+10,inf=1e18;
long long a[N*4],tree[N*4],tag[N*4],tag2[N*4],n,m;
long long ls(long long p){return (p<<1);}
long long rs(long long p){return (p<<1|1);}
void update(long long p)
{
tree[p]=max(tree[ls(p)],tree[rs(p)]);
}
void build(long long p,long long pl,long long pr)
{
tag2[p]=inf;
if(pl==pr)
{
tree[p]=a[pl];
return;
}
long long mid=(pl+pr)>>1;
build(ls(p),pl,mid);
build(rs(p),mid+1,pr);
update(p);
}
void tag_down(long long p)
{
tag[ls(p)]+=tag[p];
tree[ls(p)]+=tag[p];
tag[rs(p)]+=tag[p];
tree[rs(p)]+=tag[p];
tag[p]=0;
}
void tag_down2(long long p)
{
if(tag2[p]!=inf)
{
tag2[ls(p)]=tag2[p];
tag[ls(p)]=0;
tree[ls(p)]=tag2[p];
tag2[rs(p)]=tag2[p];
tag[rs(p)]=0;
tree[rs(p)]=tag2[p];
tag[p]=0;
tag2[p]=inf;
}
}
void change(long long l,long long r,long long p,long long pl,long long pr,long long d)
{
if(l<=pl&&pr<=r)
{
tag[p]+=d;
tree[p]+=d;
return;
}
tag_down2(p);
tag_down(p);
long long mid=(pl+pr)>>1;
if(l<=mid)
{
change(l,r,ls(p),pl,mid,d);
}
if(r>mid)
{
change(l,r,rs(p),mid+1,pr,d);
}
update(p);
}
void change2(long long l,long long r,long long p,long long pl,long long pr,long long d)
{
if(l<=pl&&pr<=r)
{
tag2[p]=d;
tree[p]=d;
tag[p]=0;
return;
}
tag_down2(p);
tag_down(p);
long long mid=(pl+pr)>>1;
if(l<=mid)
{
change2(l,r,ls(p),pl,mid,d);
}
if(r>mid)
{
change2(l,r,rs(p),mid+1,pr,d);
}
update(p);
}
long long sum(long long l,long long r,long long p,long long pl,long long pr)
{
if(l<=pl&&pr<=r)
{
return tree[p];
}
tag_down2(p);
tag_down(p);
long long res=-1e18,mid=(pl+pr)>>1;
if(l<=mid)
{
res=max(res,sum(l,r,ls(p),pl,mid));
}
if(r>mid)
{
res=max(res,sum(l,r,rs(p),mid+1,pr));
}
return res;
}
int main()
{
cin>>n>>m;
for(long long i=1;i<=n;i++)
{
cin>>a[i];
}
build(1,1,n);
while(m--)
{
long long q,l,r,d;
cin>>q>>l>>r;
if(q==1)
{
cin>>d;
change2(l,r,1,1,n,d);
}
if(q==2)
{
cin>>d;
change(l,r,1,1,n,d);
}
if(q==3)
{
cout<<sum(l,r,1,1,n)<<"\n";
}
}
return 0;
}