社区讨论

这个代码为什么不对?

AT_abc437_f[ABC437F] Manhattan Christmas Tree 2参与者 1已保存回复 1

讨论操作

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

当前回复
1 条
当前快照
1 份
快照标识符
@mjmhu0jo
此快照首次捕获于
2025/12/26 14:31
2 个月前
此快照最后确认于
2025/12/27 22:05
2 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define repn(x) rep(x,1,n)
const int N=2e5+7;
int n,q,X[N],Y[N],mx1[N<<2],mx2[N<<2],mn1[N<<2],mn2[N<<2];
void build(int p,int l,int r){
	if(l==r){
		mx1[p]=X[l]+Y[l];
		mx2[p]=X[l]-Y[l];
		mn1[p]=X[l]+Y[l];
		mn2[p]=X[l]-Y[l];
		return;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	mx1[p]=max(mx1[p<<1],mx1[p<<1|1]);
	mx2[p]=max(mx2[p<<1],mx2[p<<1|1]);
	mn1[p]=min(mn1[p<<1],mn1[p<<1|1]);
	mn2[p]=min(mn2[p<<1],mn2[p<<1|1]);
}
void addmx1(int p,int l,int r,int x,int v){
	if(l==x){
		mx1[p]=v;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) addmx1(p<<1,l,mid,x,v);
	if(x>mid) addmx1(p<<1|1,mid+1,r,x,v);
	mx1[p]=max(mx1[p<<1],mx1[p<<1|1]);
}
void addmx2(int p,int l,int r,int x,int v){
	if(l==x){
		mx2[p]=v;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) addmx2(p<<1,l,mid,x,v);
	if(x>mid) addmx2(p<<1|1,mid+1,r,x,v);
	mx2[p]=max(mx2[p<<1],mx2[p<<1|1]);
}
void addmn1(int p,int l,int r,int x,int v){
	if(l==x){
		mn1[p]=v;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) addmn1(p<<1,l,mid,x,v);
	if(x>mid) addmn1(p<<1|1,mid+1,r,x,v);
	mn1[p]=min(mn1[p<<1],mn1[p<<1|1]);
}
void addmn2(int p,int l,int r,int x,int v){
	if(l==x){
		mn2[p]=v;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) addmn2(p<<1,l,mid,x,v);
	if(x>mid) addmn2(p<<1|1,mid+1,r,x,v);
	mn2[p]=min(mn2[p<<1],mn2[p<<1|1]);
}
int querymx1(int p,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		return mx1[p];
	}
	int mid=l+r>>1,ans=-1e18;
	if(x<=mid) ans=max(ans,querymx1(p<<1,l,mid,x,y));
	if(y>mid) ans=max(ans,querymx1(p<<1|1,mid+1,r,x,y));
	return ans;
}
int querymx2(int p,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		return mx2[p];
	}
	int mid=l+r>>1,ans=-1e18;
	if(x<=mid) ans=max(ans,querymx2(p<<1,l,mid,x,y));
	if(y>mid) ans=max(ans,querymx2(p<<1|1,mid+1,r,x,y));
	return ans;
}
int querymn1(int p,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		return mn1[p];
	}
	int mid=l+r>>1,ans=1e18;
	if(x<=mid) ans=min(ans,querymn1(p<<1,l,mid,x,y));
	if(y>mid) ans=min(ans,querymn1(p<<1|1,mid+1,r,x,y));
	return ans;
}
int querymn2(int p,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		return mn2[p];
	}
	int mid=l+r>>1,ans=1e18;
	if(x<=mid) ans=min(ans,querymn2(p<<1,l,mid,x,y));
	if(y>mid) ans=min(ans,querymn2(p<<1|1,mid+1,r,x,y));
	return ans;
}
signed main()
{
	cin>>n>>q;
	rep(i,1,n){
		cin>>X[i]>>Y[i];
	}
	build(1,1,n);
//	cout<<querymn2(1,1,n,1,2)<<"\n";
	while(q--){
		int op,L,R,i,x,y;
		cin>>op;
		if(op==1){
			cin>>i>>x>>y;
			addmx1(1,1,n,i,x+y);
			addmx2(1,1,n,i,x-y);
			addmn1(1,1,n,i,x+y);
			addmn2(1,1,n,i,x-y);
		}
		if(op==2){
			cin>>L>>R>>x>>y;
			int U=x+y,V=x-y;
			int rmx1=querymx1(1,1,n,L,R);
			int rmn1=querymn1(1,1,n,L,R);
			int rmx2=querymx2(1,1,n,L,R);
			int rmn2=querymn2(1,1,n,L,R);
			cout<<max(max(abs(rmx1-U),abs(rmn1-U)),max(abs(rmx2-V),abs(rmn2-V)))<<"\n";
		}
	}
	return 0;
}

回复

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

正在加载回复...