60分求调
查看原帖
60分求调
796250
ShiYufan楼主2024/10/22 13:05

帮我这个蒻鞠调一下代码吧,大佬们


WA后四个点

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1000100
void read(int &x){
	x=0;
	long long 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();
	}
	x*=f;
}
int n,m,opt,x,y,k;
int a[N];
struct node{
	int l,r,mx,lz,add;
}tree[N*4];
void pushdown(int u){
	if(tree[u].lz==-1e18){
		tree[u*2].add+=tree[u].add;
		tree[u*2+1].add+=tree[u].add;
		tree[u*2].mx+=tree[u].add;
		tree[u*2+1].mx+=tree[u].add;
		tree[u].add=0;
	}
	else{
		tree[u*2].lz=tree[u].lz;
		tree[u*2+1].lz=tree[u].lz;
		tree[u*2].mx=tree[u].lz;
		tree[u*2+1].mx=tree[u].lz;
		tree[u].lz=-1e18;
	}
}
void build(int u,int l,int r){
	tree[u].l=l;
	tree[u].r=r;
	tree[u].lz=-1e18;
	if(l==r){
		tree[u].mx=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	if(l<=mid) build(u*2,l,mid);
	if(r>mid) build(u*2+1,mid+1,r);
	tree[u].mx=max(tree[u*2].mx,tree[u*2+1].mx);
}
void update(int u,int l,int r,int x){
	if(l<=tree[u].l&&tree[u].r<=r){
		tree[u].mx=x;
		tree[u].lz=x;
		tree[u].add=0; 
		return ;
	}
	pushdown(u);
	int mid=(tree[u].l+tree[u].r)>>1;
	if(l<=mid) update(u*2,l,r,x);
	if(r>mid) update(u*2+1,l,r,x);
	tree[u].mx=max(tree[u*2].mx,tree[u*2+1].mx);
}
void update1(int u,int l,int r,int x){
	if(l<=tree[u].l&&tree[u].r<=r){
		if(tree[u].lz!=-1e18) tree[u].lz+=x;
		else tree[u].add+=x;
		tree[u].mx+=x;
		return ;
	}
	pushdown(u);
	int mid=(tree[u].l+tree[u].r)>>1;
	if(l<=mid) update1(u*2,l,r,x);
	if(r>mid) update1(u*2+1,l,r,x);
	tree[u].mx=max(tree[u*2].mx,tree[u*2+1].mx);
}
int query(int u,int l,int r){
	if(l<=tree[u].l&&tree[u].r<=r){
		return tree[u].mx;
	}
	pushdown(u);
	int mid=(tree[u].l+tree[u].r)>>1;
	int ans=-1e18;
	if(l<=mid) ans=max(ans,query(u*2,l,r));
	if(r>mid) ans=max(ans,query(u*2+1,l,r));
	return ans;
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n);read(m);
	for(int i=1;i<=n;i++) read(a[i]);
	build(1,1,n);
	while(m--){
		read(opt);read(x);read(y);
		if(opt==1){
			read(k);
			update(1,x,y,k);
		}
		else if(opt==2){
			read(k);
			update1(1,x,y,k);
		}
		else{
			cout<<query(1,x,y)<<"\n";	
		}
	}
	return 0;
}
2024/10/22 13:05
加载中...