社区讨论

离谱,同样功能的代码为何结果不同?

P5490【模板】扫描线 & 矩形面积并参与者 2已保存回复 2

讨论操作

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

当前回复
2 条
当前快照
1 份
快照标识符
@m6305t43
此快照首次捕获于
2025/01/19 10:32
去年
此快照最后确认于
2025/11/04 11:19
4 个月前
查看原帖
rt。将最下方代码的modify部分改为
CPP
void modify(int x,int l,int r,int tl,int tr,int k){
	if(l>tr||r<tl){
		return ;
	}
	if(l>=tl&&r<=tr){
		v[x].tag+=k;
		push_up(x,l,r);
		return ;
	}
	int mid=(l+r)/2;
	if(l<=tr&&mid>=tl){
		if(v[x].l==0){
		    v[x].l=newnode(l,mid);//改成这样就挂了
		}
		modify(v[x].l,l,mid,tl,tr,k);
	}
	if(mid+1<=tr&&r>=tl){
		if(v[x].r==0){
		    v[x].r=newnode(mid+1,r);//同样问题
		}
		modify(v[x].r,mid+1,r,tl,tr,k);
	}
	push_up(x,l,r);
}
就RE了。 请问是为什么。
CPP
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

#define int long long
#define div(...)

int n;
struct Edge{
	int l,r,h,w;
	bool operator <(const Edge rhs)const{
		return h<rhs.h;
	}
};
vector<Edge>e;

struct Node{
	int len,tag;
	int l,r;
};
vector<Node>v;

int newnode(int l,int r){
	v.push_back({0,0,0,0});
	return v.size()-1;
}

void push_up(int x,int l,int r){
	if(v[x].tag){
		v[x].len=(r-l+1);
	}
	else{
		v[x].len=0;
		if(v[x].l){
			v[x].len+=v[v[x].l].len;
		}
		if(v[x].r){
			v[x].len+=v[v[x].r].len;
		}
	}
}

void modify(int x,int l,int r,int tl,int tr,int k){
	if(l>tr||r<tl){
		return ;
	}
	if(l>=tl&&r<=tr){
		v[x].tag+=k;
		push_up(x,l,r);
		return ;
	}
	int mid=(l+r)/2;
	if(l<=tr&&mid>=tl){
		if(v[x].l==0){
		    int t=newnode(l,mid);//????????????
			v[x].l=t;
		}
		modify(v[x].l,l,mid,tl,tr,k);
	}
	if(mid+1<=tr&&r>=tl){
		if(v[x].r==0){
			int t=newnode(mid+1,r);//????????????
			v[x].r=t;
		}
		modify(v[x].r,mid+1,r,tl,tr,k);
	}
	push_up(x,l,r);
}

int query(){
	return v[0].len;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	div(input){
		cin>>n;
		for(int i=1,x1,y1,x2,y2;i<=n;++i){
			cin>>x1>>y1>>x2>>y2;
			Edge newe;
			newe={x1,x2,y1,1};
			e.push_back(newe);
			newe={x1,x2,y2,-1};
			e.push_back(newe);
		}
	}
	div(prework){
		sort(e.begin(),e.end());
		v.push_back({0,0,0,0});
	}
	div(solve){
		int ans=0;
		for(int i=0;i<e.size()-1;++i){
			modify(0,1,1e9,e[i].l+1,e[i].r,e[i].w);
			ans+=(e[i+1].h-e[i].h)*query();
		}
		cout<<ans;
	}
}

回复

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

正在加载回复...