wch2021 @ 2024-10-21 16:52:09
rt,前6个点能过,后4个点WA
#include<bits/stdc++.h>
#define int __int128
const int inf=1e27+1;
using namespace std;
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<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10+'0');
}
struct node
{
int mx,lay,layj;
}tr[8000005];
void pu(int u)
{
tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);
}
void pd(int u)
{
if(tr[u].lay!=-inf)
{
tr[u<<1].lay=tr[u<<1|1].lay=tr[u<<1].mx=tr[u<<1|1].mx=tr[u].lay;
tr[u<<1].layj=tr[u<<1|1].layj=0;
tr[u].lay=-inf;
tr[u].layj=0;
}
tr[u<<1].mx+=tr[u].layj;
tr[u<<1].layj+=tr[u].layj;
tr[u<<1|1].mx+=tr[u].layj;
tr[u<<1|1].layj+=tr[u].layj;
tr[u].layj=0;
}
void build(int l,int r,int u)
{
if(l==r)
{
tr[u].mx=read();
tr[u].lay=-inf;
return;
}
tr[u].mx=-inf;
tr[u].lay=-inf;
int mid=l+r>>1;
build(l,mid,u<<1);
build(mid+1,r,u<<1|1);
pu(u);
}
void upd(int L,int R,int l,int r,int u,int x,int opt)
{
if(L<=l&&r<=R)
{
if(opt==1)
{
tr[u].mx=x;
tr[u].lay=x;
tr[u].layj=0;
}
if(opt==2)
{
tr[u].mx+=x;
if(tr[u].lay==-inf) tr[u].layj+=x;
else tr[u].lay+=x;
}
return;
}
pd(u);
int mid=l+r>>1;
if(L<=mid) upd(L,R,l,mid,u<<1,x,opt);
if(R>mid) upd(L,R,mid+1,r,u<<1|1,x,opt);
pu(u);
}
int query(int L,int R,int l,int r,int u)
{
if(L<=l&&r<=R) return tr[u].mx;
pd(u);
int mid=l+r>>1,ans=-inf;
if(L<=mid) ans=max(ans,query(L,R,l,mid,u<<1));
if(R>mid) ans=max(ans,query(L,R,mid+1,r,u<<1|1));
return ans;
}
signed main()
{
// freopen("P1253_7.in","r",stdin);
// freopen("P1253.out","w",stdout);
int n=read(),q=read();
build(1,n,1);
while(q--)
{
int opt=read(),l=read(),r=read();
if(opt!=3) upd(l,r,1,n,1,read(),opt);
else
{
write(query(l,r,1,n,1));
putchar('\n');
}
}
return 0;
}
by ghy_jerami__ @ 2024-10-21 17:22:30
@wch2021 两个修改:
__int128
改为 long long
,否则过不了,猜测是因为某个自带函数处理不了 __int128
push_down
部分,在下传 lay
时不能清空当前节点的 layj
。否则会覆盖掉父亲之后下传的 layj
修改后的 AC
代码:
#include<bits/stdc++.h>
#define int long long
const int inf=1e18+1;
using namespace std;
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<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10+'0');
}
struct node
{
int mx,lay,layj;
}tr[8000005];
void pu(int u)
{
tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);
}
void pd(int u)
{
if(tr[u].lay!=-inf)
{
tr[u<<1].lay=tr[u<<1|1].lay=tr[u<<1].mx=tr[u<<1|1].mx=tr[u].lay;
tr[u<<1].layj=tr[u<<1|1].layj=0;
tr[u].lay=-inf;
}
tr[u<<1].mx+=tr[u].layj;
tr[u<<1].layj+=tr[u].layj;
tr[u<<1|1].mx+=tr[u].layj;
tr[u<<1|1].layj+=tr[u].layj;
tr[u].layj=0;
}
void build(int l,int r,int u)
{
if(l==r)
{
tr[u].mx=read();
tr[u].lay=-inf;
return;
}
tr[u].mx=-inf;
tr[u].lay=-inf;
int mid=l+r>>1;
build(l,mid,u<<1);
build(mid+1,r,u<<1|1);
pu(u);
}
void upd(int L,int R,int l,int r,int u,int x,int opt)
{
if(L<=l&&r<=R)
{
if(opt==1)
{
tr[u].mx=x;
tr[u].lay=x;
tr[u].layj=0;
}
if(opt==2)
{
tr[u].mx+=x;
if(tr[u].lay==-inf) tr[u].layj+=x;
else tr[u].lay+=x;
}
return;
}
pd(u);
int mid=l+r>>1;
if(L<=mid) upd(L,R,l,mid,u<<1,x,opt);
if(R>mid) upd(L,R,mid+1,r,u<<1|1,x,opt);
pu(u);
}
int query(int L,int R,int l,int r,int u)
{
if(L<=l&&r<=R) return tr[u].mx;
pd(u);
int mid=l+r>>1,ans=-inf;
if(L<=mid) ans=max(ans,query(L,R,l,mid,u<<1));
if(R>mid) ans=max(ans,query(L,R,mid+1,r,u<<1|1));
return ans;
}
signed main()
{
// freopen("P1253_7.in","r",stdin);
// freopen("P1253.out","w",stdout);
int n=read(),q=read();
build(1,n,1);
while(q--)
{
int opt=read(),l=read(),r=read();
if(opt!=3) upd(l,r,1,n,1,read(),opt);
else
{
write(query(l,r,1,n,1));
putchar('\n');
}
}
return 0;
}
求关
by wch2021 @ 2024-10-21 17:26:05
@ghy_jerami__ 已过,感谢dalao 马上关
by ghy_jerami__ @ 2024-10-21 17:28:04
@wch2021 壶关了