// Problem: P1253 扶苏的问题
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1253
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1000010;
const ll INF=1e20;
int n,q;
int w[N];
struct Node{
int l,r;
ll Max,f1,f2;
}tr[N*4];
void pushup(int u)
{
tr[u].Max=max(tr[u<<1].Max,tr[u<<1|1].Max);
}
void pushdown(int u)
{
if(tr[u].f1!=INF)
{
tr[u].f2=tr[u<<1].f2=tr[u<<1|1].f2=0;
tr[u<<1].f1=tr[u].f1;
tr[u<<1].Max=tr[u].f1;
tr[u<<1|1].f1=tr[u].f1;
tr[u<<1|1].Max=tr[u].f1;
tr[u].f1=INF;
}
else
{
tr[u<<1].f2+=tr[u].f2;
tr[u<<1].Max+=tr[u].f2;
tr[u<<1|1].f2+=tr[u].f2;
tr[u<<1|1].Max+=tr[u].f2;
tr[u].f2=0;
}
}
void build(int u,int l,int r)
{
if(l==r) tr[u]={l,r,w[r],INF,0};
else
{
tr[u]={l,r,0,INF,0};
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(int u,int l,int r,ll f,ll a)
{
Node &ro=tr[u];
if(ro.l>=l&&ro.r<=r)
{
if(f!=INF)
{
ro.Max=f;
tr[u].f1=f;
}
else
{
ro.Max+=a;
ro.f2+=a;
}
}
else
{
pushdown(u);
int mid=ro.l+ro.r>>1;
if(l<=mid) modify(u<<1,l,r,f,a);
if(r>mid) modify(u<<1|1,l,r,f,a);
pushup(u);
}
}
ll query(int u,int l,int r)
{
Node &ro=tr[u];
if(ro.l>=l&&ro.r<=r) return tr[u].Max;
ll res = -INF;
pushdown(u);
int mid=ro.l+ro.r>>1;
if(l<=mid) res = max(res, query(u<<1,l,r));
if(r>mid) res = max(res, query(u<<1|1,l,r));
return res;
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
build(1,1,n);
for(int i = 1; i <= n; i ++) query(1, i, i);
int op,l,r,x;
while(q--)
{
scanf("%d%d%d",&op,&l,&r);
if(op==1)
{
scanf("%d",&x);
modify(1,l,r,x,0);
}
else if(op==2)
{
scanf("%d",&x);
modify(1,l,r,INF,x);
}
else printf("%lld\n",query(1,l,r));
}
return 0;
}
实在不知道错在哪,求大佬指点!!!
兄弟你知道哪里错了吗 我也这样
是操作优先性的问题
// Ptr[u]blem: P1253 扶苏的问题 // Contest: Luogu // URL: https://www.luogu.com.cn/ptr[u]blem/P1253 // Memory Limit: 512 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=1000010; const ll INF=1e18; int n,q; int w[N]; struct Node{ int l,r; ll Max,f1,f2; }tr[N*4]; void pushup(int u) { tr[u].Max=max(tr[u<<1].Max,tr[u<<1|1].Max); } void cover(int u) { Node &a=tr[u],&b=tr[u<<1],&c=tr[u<<1|1]; b.f2=c.f2=0; b.f1=c.f1=a.f1; b.Max=c.Max=a.f1; a.f1=INF; } void pushdown(int u) { Node &ro=tr[u],&le=tr[u<<1],&ri=tr[u<<1|1]; if(ro.f1!=INF) cover(u); if(ro.f2) { le.f2+=ro.f2; ri.f2+=ro.f2; le.Max+=ro.f2; ri.Max+=ro.f2; ro.f2=0; } } void build(int u,int l,int r) { if(l==r) tr[u]={l,r,w[r],INF,0}; else { tr[u]={l,r,0,INF,0}; int mid=l+r>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); pushup(u); } } void modify(int u,int l,int r,ll f,ll a) { if(tr[u].l>=l&&tr[u].r<=r) { if(f!=INF) { tr[u].f2=0; tr[u].f1=f; tr[u].Max=f; } if(a) { tr[u].f2+=a; tr[u].Max+=a; } } else { pushdown(u); int mid=tr[u].l+tr[u].r>>1; if(l<=mid) modify(u<<1,l,r,f,a); if(r>mid) modify(u<<1|1,l,r,f,a); pushup(u); } } ll query(int u,int l,int r) { if(tr[u].l>=l&&tr[u].r<=r) return tr[u].Max; ll res = -INF; pushdown(u); int mid=tr[u].l+tr[u].r>>1; if(l<=mid) res = max(res, query(u<<1,l,r)); if(r>mid) res = max(res, query(u<<1|1,l,r)); return res; } int main() { scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) scanf("%d",&w[i]); build(1,1,n); int op,l,r,x; while(q--) { scanf("%d%d%d",&op,&l,&r); if(op==1) { scanf("%d",&x); modify(1,l,r,x,0); } else if(op==2) { scanf("%d",&x); modify(1,l,r,INF,x); } else printf("%lld\n",query(1,l,r)); } return 0; }
这是AC代码
懂了谢谢