hwwqy @ 2022-09-23 16:35:21
#include<bits/stdc++.h>
#define int long long
#define ls x<<1
#define rs x<<1|1
#define int_max 2147483647
using namespace std;
const int S=1000100;
int mx[S<<3],taga[S<<3],tagc[S<<3],a[S],n,m;
inline int read()
{
int a=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
a=a*10+ch-'0';
ch=getchar();
}
return a*f;
}
void update(int l,int r,int x)
{
if(l!=r)
{
mx[x]=max(mx[ls],mx[rs]);
// cout<<x<<" "<<mx[ls]<<" "<<mx[rs]<<endl;
}
}
void build(int l,int r,int x)
{
tagc[x]=int_max;
if(l==r)
{
mx[x]=a[l];
return ;
}
int mid=l+r>>1;
build(l,mid,ls);
build(mid+1,r,rs);
update(l,r,x);
// cout<<x<<" "<<mx[x]<<endl;
return ;
}
void pushdown(int l,int r,int x)
{
if(taga[x]==0&&tagc[x]==int_max)return;
int mid=l+r>>1;
if(tagc[x]!=int_max)
{
tagc[rs]=tagc[x];
tagc[ls]=tagc[x];
mx[ls]=tagc[x];
mx[rs]=tagc[x];
tagc[x]=int_max;
taga[x]=0;
return;
}
else if(l!=r)
{
mx[ls]+=taga[x];
mx[rs]+=taga[x];
taga[ls]+=taga[x];
taga[rs]+=taga[x];
}
// tagc[x]=int_max;
taga[x]=0;
}
int query(int x,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)return mx[x];
int mid=l+r>>1;
// cout<<mid<<endl;
pushdown(l,r,x);
if(qr<=mid)
{
return query(ls,l,mid,ql,qr);
}
else if(qr>mid)
{
return query(rs,mid+1,r,ql,qr);
}
else return max(query(ls,l,mid,ql,mid),query(rs,mid+1,r,mid+1,qr));
}
void add(int x,int l,int r,int ql,int qr,int k)
{
if(ql==l&&r==qr)
{
mx[x]+=k;
taga[x]+=k;
// cout<<mx[x]<<" "<<x<<endl;
return;
}
pushdown(l,r,x);
int mid=l+r>>1;
//cout<<mid<<endl;
if(qr<=mid)
{
add(ls,l,mid,ql,qr,k);
}
else if(ql>mid)
{
add(rs,mid+1,r,ql,qr,k);
}
else
{
add(ls,l,mid,ql,mid,k);
add(rs,mid+1,r,mid+1,qr,k);
}
update(l,r,x);
}
void change(int x,int l,int r,int ql,int qr,int k)
{
if(ql<=l&&r<=qr)
{
mx[x]=k;
tagc[x]=k;
taga[x]=0;
return;
}
pushdown(l,r,x);
int mid=l+r>>1;
if(qr<=mid)
{
change(ls,l,mid,ql,qr,k);
}
else if(ql>mid)
{
change(rs,mid+1,r,ql,qr,k);
}
else
{
change(ls,l,mid,ql,mid,k);
change(rs,mid+1,r,mid+1,qr,k);
}
update(l,r,x);
}
signed main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)a[i]=read();
build(1,n,1);
//for(int i=1;i<=13;i++)cout<<mx[i]<<" ";
// cout<<endl;
for(int i=1;i<=m;i++)
{
int op,l,r,x;
op=read(),l=read(),r=read();
if(op==1||op==2)x=read();
if(op==1)
{
change(1,1,n,l,r,x);
}
else if(op==2)
{
add(1,1,n,l,r,x);
}
else
{
cout<<query(1,1,n,l,r)<<endl;
}
// for(int i=1;i<=13;i++)cout<<mx[i]<<" ";
// cout<<endl;
}
return 0;
}
他们都说我的线段树码风太新奇了
by _Vix_ @ 2022-09-23 17:05:25
@hwwqy 没开long long
by hwwqy @ 2022-09-23 17:14:09
@Zheng07 开了，我在第二行写了define int long long
by _Vix_ @ 2022-09-23 17:26:19
@hwwqy query 里面 ql > mid (你的码风真是清奇
by _Vix_ @ 2022-09-23 17:27:05
@Zheng07 好像改了也没过（60pts
by hwwqy @ 2022-09-23 17:31:43
@Zheng07 好像是的，我太逆天了
by 天南星魔芋 @ 2022-09-23 17:59:13
@hwwqy 大概好了，最后一个点tle，自己优化吧
#include<bits/stdc++.h>
#define int long long
#define ls x<<1
#define rs x<<1|1
#define int_max 10000000000000000
using namespace std;
const int S=1000100;
int mx[S<<3],taga[S<<3],tagc[S<<3],a[S],n,m;
inline int read()
{
int a=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
a=a*10+ch-'0';
ch=getchar();
}
return a*f;
}
void update(int l,int r,int x)
{
if(l!=r)
{
mx[x]=max(mx[ls],mx[rs]);
// cout<<x<<" "<<mx[ls]<<" "<<mx[rs]<<endl;
}
}
void build(int l,int r,int x)
{
tagc[x]=int_max;
if(l==r)
{
mx[x]=a[l];
return ;
}
int mid=l+r>>1;
build(l,mid,ls);
build(mid+1,r,rs);
update(l,r,x);
// cout<<x<<" "<<mx[x]<<endl;
return ;
}
void pushdown(int l,int r,int x)
{
if(taga[x]==0&&tagc[x]==int_max)return;
int mid=l+r>>1;
if(tagc[x]!=int_max)
{
tagc[rs]=tagc[x];
tagc[ls]=tagc[x];
mx[ls]=tagc[x];
mx[rs]=tagc[x];
taga[ls]=0;taga[rs]=0;
tagc[x]=int_max;
taga[x]=0;
return;
}
else if(l!=r)
{
if(tagc[ls]!=int_max)pushdown(l,mid,x*2);
if(tagc[rs]!=int_max)pushdown(mid+1,r,x*2+1);
mx[ls]+=taga[x];
mx[rs]+=taga[x];
taga[ls]+=taga[x];
taga[rs]+=taga[x];
}
tagc[x]=int_max;
taga[x]=0;
}
int query(int x,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)return mx[x];
int mid=l+r>>1;
// cout<<mid<<endl;
pushdown(l,r,x);
if(qr<=mid)
{
return query(ls,l,mid,ql,qr);
}
else if(ql>mid)
{
return query(rs,mid+1,r,ql,qr);
}
else return max(query(ls,l,mid,ql,mid),query(rs,mid+1,r,mid+1,qr));
}
void add(int x,int l,int r,int ql,int qr,int k)
{
pushdown(l,r,x);
if(ql==l&&r==qr)
{
mx[x]+=k;
taga[x]+=k;
// cout<<mx[x]<<" "<<x<<endl;
return;
}
int mid=l+r>>1;
//cout<<mid<<endl;
if(qr<=mid)
{
add(ls,l,mid,ql,qr,k);
}
else if(ql>mid)
{
add(rs,mid+1,r,ql,qr,k);
}
else
{
add(ls,l,mid,ql,mid,k);
add(rs,mid+1,r,mid+1,qr,k);
}
update(l,r,x);
}
void change(int x,int l,int r,int ql,int qr,int k)
{
if(ql<=l&&r<=qr)
{
mx[x]=k;
tagc[x]=k;
taga[x]=0;
return;
}
pushdown(l,r,x);
int mid=l+r>>1;
if(qr<=mid)
{
change(ls,l,mid,ql,qr,k);
}
else if(ql>mid)
{
change(rs,mid+1,r,ql,qr,k);
}
else
{
change(ls,l,mid,ql,mid,k);
change(rs,mid+1,r,mid+1,qr,k);
}
update(l,r,x);
}
signed main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)a[i]=read();
build(1,n,1);
//for(int i=1;i<=13;i++)cout<<mx[i]<<" ";
// cout<<endl;
for(int i=1;i<=m;i++)
{
int op,l,r,x;
op=read(),l=read(),r=read();
if(op==1||op==2)x=read();
if(op==1)
{
change(1,1,n,l,r,x);
}
else if(op==2)
{
add(1,1,n,l,r,x);
}
else
{
cout<<query(1,1,n,l,r)<<endl;
}
// for(int i=1;i<=13;i++)cout<<mx[i]<<" ";
// cout<<endl;
}
return 0;
}