1 solutions

  • 0
    @ 2024-12-20 13:42:26

    题解

    呜呜呜，在不知调了多久后，终于过了......

    思路

    看到神奇的最大值最大值就知道，这题会比其他题简单很多,只 是 个 绿 题
    Q:为啥调了二十多次??? A:因为我太没实力了......

    一开始，我以为直接把pushup改了就行了，可是仔细一看，题目居然还需要区间修改（就是修改，不是加和）。

    然后，我以为只需要再写一个函数就好了。可是突然发现，原来的懒标记只能用在加法上，不能用在修改上。所以还需要一个懒标记来专门应对修改（就是修改，不是加和）。

    接着，我以为只需要再加一个懒标记就可以了。但是，仔细一看，这个数字可能是负数，所以在初始化时需要把初始值修改成一个很小的数。

    然后，我以为只需要修改初始值就可以了。但是，仔细一想，突然发现如果先处理加法的懒标记再处理修改（就是修改，不是加和）的懒标记，加的数就不会加上去，而是被新的数给覆盖掉。所以，写pushdown时需要先修改（就是修改，不是加和）再加和。

    再然后，我以为只需要再修改一下pushdown就好了。但是，我灵机一动，如果在修改（就是修改，不是加和）区间的时候，没有把旧的加法标记去掉，原来应该被覆盖的加法就会被加到新的数上。所以，在写修改（就是修改，不是加和）函数的时候，不仅需要修改自身的懒标记，还需要把加和的懒标记设为0。

    最后，我以为我可以过了，但是突然发现，在求区间最大值的时候，max值也要初始化为一个非常小的数，不然会出现非常悲伤的事。

    然后……没有然后了。

    呆码

    错误示范1

    死因 错误原因：把加和标记重置了。

    #include<bits/stdc++.h>
#define ety -114411441144123
typedef long long ll;
using namespace std;
struct node{
	int l;
	int r;
	ll num;
}tree[10000001];
ll arr[10000001],n;
ll tag1[10000001],tag2[10000001];
void createTree(ll sp,ll l,ll r){
	tree[sp].l=l;
	tree[sp].r=r;
	if(l==r){
		tree[sp].num=arr[l];
		return;
	}
	ll mid=(l+r)>>1;
	createTree(sp<<1,l,mid);
	createTree((sp<<1)+1,mid+1,r);
	tree[sp].num=max(tree[sp<<1].num,tree[(sp<<1)+1].num);
}
void cltag2(ll sp){
	tree[sp<<1].num+=tag2[sp];tree[(sp<<1)+1].num+=tag2[sp];
	tag2[sp<<1]=tag2[(sp<<1)+1]=tag2[sp];
	tag2[sp]=0;
}
void cltag1(ll sp){
	if(tag1[sp]!=ety){
		tree[sp<<1].num=tag1[sp];tree[(sp<<1)+1].num=tag1[sp];
		tag1[sp<<1]+=tag1[sp];
		tag1[(sp<<1)+1]+=tag1[sp];
		tag1[sp]=ety;
	}
}
void areaChange(ll sp,ll l,ll r,ll c){
	if(tree[sp].l>=l&&tree[sp].r<=r){
		tag1[sp]=c;
		tree[sp].num=c;
		return;
	}
	cltag1(sp);
	ll mid=(tree[sp].l+tree[sp].r)>>1;
	if(l<=mid)areaChange(sp<<1,l,r,c);
	if(r>mid)areaChange((sp<<1)+1,l,r,c);
	tree[sp].num=max(tree[sp<<1].num,tree[(sp<<1)+1].num);
}
void areaAdd(ll sp,ll l,ll r,ll c){
	if(tree[sp].l>=l&&tree[sp].r<=r){
		tag2[sp]+=c;
		tree[sp].num+=c;
		return;
	}
	cltag2(sp);
	ll mid=(tree[sp].l+tree[sp].r)>>1;
	if(l<=mid)areaAdd(sp<<1,l,r,c);
	if(r>mid)areaAdd((sp<<1)+1,l,r,c);
	tree[sp].num=max(tree[sp<<1].num,tree[(sp<<1)+1].num);
}
ll areaAsk(ll sp,ll l,ll r){
	if(tree[sp].l>=l&&tree[sp].r<=r)return tree[sp].num;
	cltag1(sp);
	cltag2(sp);
	ll maxn=0;
	ll mid=(tree[sp].l+tree[sp].r)>>1;
	if(l<=mid)maxn=max(maxn,areaAsk(sp<<1,l,r));
	if(r>mid)maxn=max(maxn,areaAsk((sp<<1)+1,l,r));
	return maxn;
}
int main(){
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(false);
	fill(tag1,tag1+10000000,ety);
	ll q;
	cin>>n>>q;
	for(ll i=1;i<=n;i++)cin>>arr[i];
	createTree(1,1,n);
	while(q--){
		int m;
		cin>>m;
		if(m==1){
			ll l,r,x;
			cin>>l>>r>>x;
			areaChange(1,l,r,x);
		}else if(m==2){
			ll l,r,x;
			cin>>l>>r>>x;
			areaAdd(1,l,r,x);
		}else{
			ll l,r;
			cin>>l>>r;
			cout<<areaAsk(1,l,r)<<endl;
		}
	}
}

    错误示范2

    死因 错误原因：初始值没有改，计算时的初始值也没有改。 更正了：加和标记修好了。

    #include<bits/stdc++.h>
#define ety -114411441144123
typedef long long ll;
using namespace std;
struct node{
	int l;
	int r;
	ll num;
}tree[10000001];
ll arr[10000001],n;
ll tag1[10000001],tag2[10000001];
void createTree(ll sp,ll l,ll r){
	tree[sp].l=l;
	tree[sp].r=r;
	if(l==r){
		tree[sp].num=arr[l];
		return;
	}
	ll mid=(l+r)>>1;
	createTree(sp<<1,l,mid);
	createTree((sp<<1)+1,mid+1,r);
	tree[sp].num=max(tree[sp<<1].num,tree[(sp<<1)+1].num);
}
void cltag2(ll sp){
	tree[sp<<1].num+=tag2[sp];tree[(sp<<1)+1].num+=tag2[sp];
	tag2[sp<<1]+=tag2[sp];
	tag2[(sp<<1)+1]+=tag2[sp];
	tag2[sp]=0;
}
void cltag1(ll sp){
	if(tag1[sp]!=ety){
		tree[sp<<1].num=tag1[sp];tree[(sp<<1)+1].num=tag1[sp];
		tag1[sp<<1]=tag1[(sp<<1)+1]=tag1[sp];
		tag1[sp]=ety;
	}
}
void areaChange(ll sp,ll l,ll r,ll c){
	if(tree[sp].l>=l&&tree[sp].r<=r){
		tag1[sp]=c;
		tree[sp].num=c;
		return;
	}
	cltag1(sp);
	ll mid=(tree[sp].l+tree[sp].r)>>1;
	if(l<=mid)areaChange(sp<<1,l,r,c);
	if(r>mid)areaChange((sp<<1)+1,l,r,c);
	tree[sp].num=max(tree[sp<<1].num,tree[(sp<<1)+1].num);
}
void areaAdd(ll sp,ll l,ll r,ll c){
	if(tree[sp].l>=l&&tree[sp].r<=r){
		tag2[sp]+=c;
		tree[sp].num+=c;
		return;
	}
	cltag2(sp);
	ll mid=(tree[sp].l+tree[sp].r)>>1;
	if(l<=mid)areaAdd(sp<<1,l,r,c);
	if(r>mid)areaAdd((sp<<1)+1,l,r,c);
	tree[sp].num=max(tree[sp<<1].num,tree[(sp<<1)+1].num);
}
ll areaAsk(ll sp,ll l,ll r){
	if(tree[sp].l>=l&&tree[sp].r<=r)return tree[sp].num;
	cltag1(sp);
	cltag2(sp);
	ll maxn=0;
	ll mid=(tree[sp].l+tree[sp].r)>>1;
	if(l<=mid)maxn=max(maxn,areaAsk(sp<<1,l,r));
	if(r>mid)maxn=max(maxn,areaAsk((sp<<1)+1,l,r));
	return maxn;
}
int main(){
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(false);
	fill(tag1,tag1+10000000,ety);
	ll q;
	cin>>n>>q;
	for(ll i=1;i<=n;i++)cin>>arr[i];
	createTree(1,1,n);
	while(q--){
		int m;
		cin>>m;
		if(m==1){
			ll l,r,x;
			cin>>l>>r>>x;
			areaChange(1,l,r,x);
		}else if(m==2){
			ll l,r,x;
			cin>>l>>r>>x;
			areaAdd(1,l,r,x);
		}else{
			ll l,r;
			cin>>l>>r;
			cout<<areaAsk(1,l,r)<<endl;
		}
	}
}

    错误示范3正确呆码

    修改了前面的所有错误。

    #include<bits/stdc++.h>
#define ety -114411441144123
typedef long long ll;
using namespace std;
struct node{
	int l;
	int r;
	ll num;
}tree[10000001];
ll arr[10000001],n;
ll tag1[10000001],tag2[10000001];
void createTree(ll sp,ll l,ll r){
	tree[sp].l=l;
	tree[sp].r=r;
	tree[sp].num=-100000000000000;
	if(l==r){
		tree[sp].num=arr[l];
		return;
	}
	ll mid=(l+r)>>1;
	createTree(sp<<1,l,mid);
	createTree((sp<<1)+1,mid+1,r);
	tree[sp].num=max(tree[sp<<1].num,tree[(sp<<1)+1].num);
}
void cltag(ll sp){
	if(tag1[sp]!=ety){
		tag1[sp<<1]=tag1[(sp<<1)+1]=tag1[sp];
		tag2[sp<<1]=tag2[(sp<<1)+1]=tag2[sp];//如果不是先改变数再加上数，加就没有意义了
		tree[sp<<1].num=tree[(sp<<1)+1].num=tag1[sp]+tag2[sp];
		tag1[sp]=ety;
	}else{
		tag2[sp<<1]+=tag2[sp];tag2[(sp<<1)+1]+=tag2[sp];
		tree[sp<<1].num+=tag2[sp];tree[(sp<<1)+1].num+=tag2[sp];
	}
	tag2[sp]=0;
}
void areaChange(ll sp,ll l,ll r,ll c){
	if(tree[sp].l>=l&&tree[sp].r<=r){
		tag1[sp]=c;
		tree[sp].num=c;
		tag2[sp]=0;//改变后加的数全部没用了
		return;
	}
	cltag(sp);
	ll mid=(tree[sp].l+tree[sp].r)>>1;
	if(l<=mid)areaChange(sp<<1,l,r,c);
	if(r>mid)areaChange((sp<<1)+1,l,r,c);
	tree[sp].num=max(tree[sp<<1].num,tree[(sp<<1)+1].num);
}
void areaAdd(ll sp,ll l,ll r,ll c){
	if(tree[sp].l>=l&&tree[sp].r<=r){
		tag2[sp]+=c;
		tree[sp].num+=c;
		return;
	}
	cltag(sp);
	ll mid=(tree[sp].l+tree[sp].r)>>1;
	if(l<=mid)areaAdd(sp<<1,l,r,c);
	if(r>mid)areaAdd((sp<<1)+1,l,r,c);
	tree[sp].num=max(tree[sp<<1].num,tree[(sp<<1)+1].num);
}
ll areaAsk(ll sp,ll l,ll r){
	if(tree[sp].l>=l&&tree[sp].r<=r)return tree[sp].num;
	cltag(sp);
	ll maxn=-100000000000000;
	ll mid=(tree[sp].l+tree[sp].r)>>1;
	if(l<=mid)maxn=max(maxn,areaAsk(sp<<1,l,r));
	if(r>=mid+1)maxn=max(maxn,areaAsk((sp<<1)+1,l,r));
	return maxn;
}
int main(){
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(false);
	fill(tag1,tag1+10000000,ety);
	ll q;
	cin>>n>>q;
	for(ll i=1;i<=n;i++)cin>>arr[i];
	createTree(1,1,n);
	while(q--){
		int m;
		cin>>m;
		if(m==1){
			ll l,r,x;
			cin>>l>>r>>x;
			areaChange(1,l,r,x);
		}else if(m==2){
			ll l,r,x;
			cin>>l>>r>>x;
			areaAdd(1,l,r,x);
		}else{
			ll l,r;
			cin>>l>>r;
			cout<<areaAsk(1,l,r)<<endl;
		}
	}
}
    • @ 2024-12-20 13:43:27

      这么郵筫的题解就没有人点赞吗......

    • @ 2024-12-20 19:10:15

      鸡生体节

      #include<iostream>
#define N 1000005
#define INF 100000000000000ULL
#define int long long
using namespace std;
int n,q;
int a[4*N];//原始数组 
int tree[4*N];//最大值 
int flag[4*N];//更改标记 
int chan[4*N];//更改值 
int lazy[4*N];//加法标记 
void downlazy(int l,int r,int x)
{
	if(flag[x])
	{
		tree[x<<1]=chan[x]+lazy[x];
		tree[x<<1|1]=chan[x]+lazy[x];
		flag[x<<1]=flag[x];
		flag[x<<1|1]=flag[x];
		chan[x<<1]=chan[x];
		chan[x<<1|1]=chan[x];
		lazy[x<<1]=lazy[x];
		lazy[x<<1|1]=lazy[x];
		flag[x]=0;
	}
	else
	{
		tree[x<<1]+=lazy[x];
		tree[x<<1|1]+=lazy[x];
		lazy[x<<1]+=lazy[x];
		lazy[x<<1|1]+=lazy[x];
	}
	lazy[x]=0;
}
void btree(int l,int r,int x)
{
    if(l==r)
    {
    	tree[x]=a[l];
    	return;
	}
    int m=(l+r)>>1;
    btree(l,m,x<<1);
    btree(m+1,r,x<<1|1);
    tree[x]=max(tree[x<<1],tree[x<<1|1]);
}
void uctree(int l,int r,int s,int t,int c,int x)
{
	if(l<=s && t<=r)
	{
		tree[x]=c;
		flag[x]=1;
		chan[x]=c;
		lazy[x]=0;
		return;
	}
	int m=(s+t)>>1;
	downlazy(s,t,x);
	if(l<=m)
		uctree(l,r,s,m,c,x<<1);
	if(r>m)
		uctree(l,r,m+1,t,c,x<<1|1);
	tree[x]=max(tree[x<<1],tree[x<<1|1]);
}
void uatree(int l,int r,int s,int t,int c,int x)
{
	if(l<=s && t<=r)
	{
		tree[x]+=c;
		lazy[x]+=c;
		return;
	}
	int m=(s+t)>>1;
	downlazy(s,t,x);
	if(l<=m)
		uatree(l,r,s,m,c,x<<1);
	if(r>m)
		uatree(l,r,m+1,t,c,x<<1|1);
	tree[x]=max(tree[x<<1],tree[x<<1|1]);
}
int gtree(int l,int r,int s,int t,int x)
{
	if(l<=s && t<=r)
		return tree[x];
	int m=(s+t)>>1,ans=-INF;
	downlazy(s,t,x);
	if(l<=m)
		ans=max(ans,gtree(l,r,s,m,x<<1));
	if(r>m)
		ans=max(ans,gtree(l,r,m+1,t,x<<1|1));
	return ans;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	for(int i=0;i<N;i++)
		chan[i]=-INF;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    btree(1,n,1);
    while(q--)
    {
		int o,l,r,x;
		cin>>o>>l>>r;
		if(o!=3)
		{
			cin>>x;
			if(o==1)
				uctree(l,r,1,n,x,1);
			if(o==2)
				uatree(l,r,1,n,x,1);
		}	
		else
			cout<<gtree(l,r,1,n,1)<<"\n";
    }
    return 0;
}
    • @ 2024-12-27 21:10:34

      注释：tag1 是乘法懒标记，tag2 是加法懒标记。

    • @ 2024-12-30 13:17:02

      @ 系绳体节还不错

  • 1

扶苏的问题

Information

ID
294
Time
2000ms
Memory
512MiB
Difficulty
9
Tags
# Submissions
103
Accepted
6
Uploaded By
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 粤ICP备2022044963号-1
  3. Worker 0, 28ms
  4. Powered by Hydro v4.13.3 Community