P1253求调
  • 板块学术版
  • 楼主wang1234567
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/2/4 22:48
  • 上次更新2023/10/28 09:41:12
查看原帖
P1253求调
305900
wang1234567楼主2022/2/4 22:48

题目

只有60分,剩下的点不知道错哪了,求大佬看看

#include<bits/stdc++.h>
using namespace std;
struct node
{
	long long l,r,mx,tag_1,tag_2;
	bool f;
}t[40000000];
long long l,r,n,m,op,x,a[10000000];
void pushup(long long id)
{
	t[id].mx=max(t[id*2].mx,t[id*2+1].mx);
}
void pushdown(long long id)
{
	if(t[id].f)
	{
		t[id*2].tag_1=t[id].tag_1;
		t[id*2+1].tag_1=t[id].tag_1;
		t[id*2].mx=t[id].tag_1;
		t[id*2+1].mx=t[id].tag_1;
		t[id].tag_1=0;
		t[id].f=0;
	}
	if(t[id].tag_2)
	{
		t[id*2].tag_2+=t[id].tag_2;
		t[id*2+1].tag_2+=t[id].tag_2;
		t[id*2].mx+=t[id].tag_2;
		t[id*2+1].mx+=t[id].tag_2;
		t[id].tag_2=0;
	}
}
void build(long long l,long long r,long long id)
{
	t[id].l=l;t[id].r=r;
	if(l==r)
	{
		t[id].mx=a[l];
		return;
	}
	long long mid=(l+r)/2;
	build(l,mid,id*2);
	build(mid+1,r,id*2+1);
	pushup(id);
}
long long query(long long id)
{
	if(t[id].l>r||t[id].r<l) return -999999999999;
	if(t[id].l>=l&&t[id].r<=r)
		return t[id].mx;
	pushdown(id);
	return max(query(id*2),query(id*2+1));
}
void update_1(long long id)
{
	if(t[id].l>r||t[id].r<l) return;
	if(t[id].l>=l&&t[id].r<=r)
	{
		t[id].mx=x;
		t[id].tag_1=x;
		t[id].tag_2=0;
		t[id].f=1;
		return;
	}
	pushdown(id);
	update_1(id*2);update_1(id*2+1);
	pushup(id);
}
void update_2(long long id)
{
	if(t[id].l>r||t[id].r<l) return;
	if(t[id].l>=l&&t[id].r<=r)
	{
		t[id].mx+=x;
		t[id].tag_2+=x;
		return;
	}
	pushdown(id);
	update_2(id*2);update_2(id*2+1);
	pushup(id);
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	build(1,n,1);
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&op,&l,&r);
		if(op==1)
		{
			scanf("%lld",&x);
			update_1(1);
		}
		if(op==2)
		{
			scanf("%lld",&x);
			update_2(1);
		}
		if(op==3)
			printf("%lld\n",query(1));
	}
	return 0;
}
2022/2/4 22:48
加载中...