社区讨论

萌新跪求50分程序改错

P1253扶苏的问题参与者 2已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@lobf01pd
此快照首次捕获于
2023/10/29 19:55
2 年前
此快照最后确认于
2023/11/04 01:30
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
long long n,m,a[1000001],ans[1000001],tot;
struct tree{
	long long l,r;
	long long dat=-0x3f3f3f3f3f;
	long long add;
	long long xg;
}t[1000001*4];
void build(long long p,long long l,long long r)
{
	t[p].l=l,t[p].r=r;
	if(l==r) {t[p].dat=a[l];return;}
	long long mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	t[p].dat=max(t[p*2].dat,t[p*2+1].dat);
}
void spread(long long p)
{
    if(t[p].add)
	{
		t[p*2].add+=t[p].add;
		t[p*2+1].add+=t[p].add;
		t[p*2].dat+=t[p].add;
		t[p*2+1].dat+=t[p].add;
		t[p].add=0;
	}
}
void spread1(long long p)
{
	if(t[p].xg)
	{
		t[p*2].add=0;
		t[p*2+1].add=0;
		t[p*2].xg=t[p].xg;
		t[p*2+1].xg=t[p].xg;
		t[p*2].dat=t[p].xg;
		t[p*2+1].dat=t[p].xg;
		t[p].xg=0;
	}
}
void chang(long long p,long long l,long long r,long long x)       //修改 
{
	
	if(l<=t[p].l&&r>=t[p].r)
	{
		t[p].dat=x;
		t[p].xg=x;
		t[p].add=0; 
		return;
	}
	spread1(p);
	long long mid=(t[p].l+t[p].r)/2;
	if(l<=mid) chang(p*2,l,r,x);
	if(r>mid) chang(p*2+1,l,r,x);
	t[p].dat=max(t[p*2].dat,t[p*2+1].dat);
}
void chan(long long p,long long l,long long r,long long x)          //加 
{
	if(l<=t[p].l&&r>=t[p].r)
	{
	    t[p].dat+=x;
		t[p].add+=x;
		return;
	}
	spread(p);
	long long mid=(t[p].l+t[p].r)/2;
	if(l<=mid) chan(p*2,l,r,x);
	if(r>mid) chan(p*2+1,l,r,x);
	t[p].dat=max(t[p*2].dat,t[p*2+1].dat);
}
long long ask(int p,int l,int r)
{
	if(l<=t[p].l&&r>=t[p].r) return t[p].dat;
	spread1(p);
	spread(p);
	long long mid=(t[p].r+t[p].l)/2;
	long long val=-0x3f3f3f;
	if(l<=mid) val=max(val,ask(p*2,l,r));
	if(r>mid) val=max(val,ask(p*2+1,l,r));
	return val;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
	    long long w,l,r,x;
		cin>>w>>l>>r;
		if(w==1)
		{
			cin>>x;
			chang(1,l,r,x);
		}
		if(w==2)
		{
			cin>>x;
			chan(1,l,r,x);
		}
		if(w==3) ans[++tot]=ask(1,l,r);
	}
	for(int i=1;i<=tot;i++)
	cout<<ans[i]<<endl;
}

回复

5 条回复,欢迎继续交流。

正在加载回复...