社区讨论
这个代码为什么不对?
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 条回复,欢迎继续交流。
正在加载回复...