自己造了几组小样例都能过,但是一交就是 WA
有无大佬可以帮忙看一下哪里写错了 (个人实在看不出有啥问题了qwq
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
struct rec{
int sx,sy,ex,ey;
}a[maxn];
struct line{
int l,r,y,k;
inline bool operator < (line tmp) const{
return y<tmp.y;
}
}l[maxn<<1];
struct segment{
int l,r,sum,len;
}c[maxn<<3];
int n,tmp[maxn<<1];
ll ans;
inline void build(int rt,int l,int r){
c[rt].l=l,c[rt].r=r;
if (l==r) return ;
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
}
inline void upd(int rt,int l,int r,int k){
if (c[rt].l>r || c[rt].r<l) return ;
if (c[rt].l>=l && c[rt].r<=r){
c[rt].sum+=k;
if (c[rt].sum) c[rt].len=tmp[c[rt].r]-tmp[c[rt].l-1];
else c[rt].len=c[rt<<1].len+c[rt<<1|1].len;
return ;
}
upd(rt<<1,l,r,k);
upd(rt<<1|1,l,r,k);
if (c[rt].sum) c[rt].len=tmp[c[rt].r]-tmp[c[rt].l-1];
else c[rt].len=c[rt<<1].len+c[rt<<1|1].len;
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d%d%d%d",&a[i].sx,&a[i].sy,&a[i].ex,&a[i].ey);
if (a[i].sx>a[i].ex) swap(a[i].sx,a[i].ex);
if (a[i].sy<a[i].ey) swap(a[i].sy,a[i].ey);
tmp[(i<<1)-1]=a[i].sx;
tmp[i<<1]=a[i].ex;
}
sort(tmp+1,tmp+(n<<1)+1);
int mtot=unique(tmp+1,tmp+(n<<1)+1)-tmp-1;
for (int i=1;i<=n;i++){
a[i].sx=lower_bound(tmp+1,tmp+mtot+1,a[i].sx)-tmp;
a[i].ex=lower_bound(tmp+1,tmp+mtot+1,a[i].ex)-tmp;
}
build(1,1,mtot);
for (int i=1;i<=n;i++){
l[(i<<1)-1]=(line){a[i].sx,a[i].ex,a[i].sy,-1};
l[i<<1]=(line){a[i].sx,a[i].ex,a[i].ey,1};
}
sort(l+1,l+(n<<1)+1);
for (int i=1;i<(n<<1);i++){
upd(1,l[i].l+1,l[i].r,l[i].k);
ans+=1ll*c[1].len*(l[i+1].y-l[i].y);
}
printf("%lld\n",ans);
return 0;
}
(悬关