社区讨论
离谱,同样功能的代码为何结果不同?
P5490【模板】扫描线 & 矩形面积并参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @m6305t43
- 此快照首次捕获于
- 2025/01/19 10:32 去年
- 此快照最后确认于
- 2025/11/04 11:19 4 个月前
rt。将最下方代码的
CPPmodify部分改为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 条回复,欢迎继续交流。
正在加载回复...