社区讨论
本蒟蒻本地完全没输出,求条
P5490【模板】扫描线 & 矩形面积并参与者 4已保存回复 11
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 11 条
- 当前快照
- 1 份
- 快照标识符
- @mi8njfb1
- 此快照首次捕获于
- 2025/11/21 17:22 3 个月前
- 此快照最后确认于
- 2025/11/21 19:02 3 个月前
看不出来错哪了
就是没输出,直接终止
CPP#include<bits/stdc++.h>
#define ls i<<1
#define rs i<<1|1
#define mid l+r>>1
using namespace std;
const int maxn=3e5+10;
struct node{
int lx,ly,rx,ry;
}rec[maxn];
struct node1{
int x,y,y2,w;
}line[maxn];
bool cmp(node1 x,node1 y){
return x.x<y.x;
}
int ysort[maxn],len[maxn<<2],cover[maxn<<2],times[maxn<<2];
int prepare(int n){
sort(ysort+1,ysort+n+1);
int m=1;
for(int i=2;i<=n;i++){
if(ysort[m]!=ysort[i])ysort[++m]=ysort[i];
}
ysort[m+1]=ysort[m];
return m;
}
int rank(int n,int num){
int ans=0;
int l=1,r=n;
while(l<=r){
if(ysort[mid]>=num){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
return ans;
}
void build(int l,int r,int i){
if(l<r){
build(l,mid,ls);
build(mid+1,r,rs);
}
len[i]=ysort[r+1]-ysort[l];
times[i]=0;
cover[i]=0;
}
void up(int i){
if(times[i]>0){
cover[i]=len[i];
}else{
cover[i]=cover[ls]+cover[rs];
}
}
void add(int jobl,int jobr,int jobv,int l,int r,int i){
if(jobl<=l&&r<=jobr){
times[i]+=jobv;
}else{
if(jobl<=mid){
add(jobl,jobr,jobv,l,mid,ls);
}
if(jobr>mid){
add(jobl,jobr,jobv,mid+1,r,rs);
}
}
up(i);
}
long long compute(int n){
for(int i=1,j=n+1;i<=n;i++,j++){
ysort[i]=rec[i].ly;
ysort[j]=rec[i].ry;
line[i].x=rec[i].lx;
line[i].y=rec[i].ly;
line[i].y2=rec[i].ry;
line[i].w=1;
line[j].x=rec[i].rx;
line[j].y=rec[i].ly;
line[j].y2=rec[i].ry;
line[j].w=-1;
}
n<<=1;
int m=prepare(n);
build(1,m,1);
sort(line+1,line+n+1,cmp);
long long ans=0;
for(int i=1,pre=0;i<=n;i++){
ans+=(long long)cover[1]*(line[i].x-pre);
pre=line[i].x;
add(rank(m,line[i].y),rank(m,line[i].y2)-1,line[i].w,1,m,1);
}
return ans;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>rec[i].lx>>rec[i].ly>>rec[i].rx>>rec[i].ry;
}
cout<<compute(n);
return 0;
}
回复
共 11 条回复,欢迎继续交流。
正在加载回复...