P5490 扫描线
线段树维护的是区间内点或点集的信息 或者 维护经过特殊处理的左右端点的信息
而此题求的是区间长度
解法：将区间长度分给左端点
未通过洛谷全部测试点
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e5+7;
int n;
struct L{
ll x,x2,y;
int w;
}a[N<<1];
ll z[N<<1];
bool cmp(L a,L b){
return a.y!=b.y?a.y>b.y:a.w>b.w;
}
ll tr[N<<2],tr2[N<<2];
void add(int p,int l,int r,int x,int y,int w){
if(x<=l&&r<=y){
tr[p]+=w;
if(tr[p]>0) tr2[p]=z[r+1]-z[l];
else {
tr2[p]=tr2[p*2]+tr2[p*2+1];
}
return ;
}
int mid=(l+r) >> 1;
if(x<=mid) add(p*2,l,mid,x,y,w);
if(mid+1<=y) add(p*2+1,mid+1,r,x,y,w);
if(tr[p]>0) tr2[p]=z[r+1]-z[l];
else {
tr2[p]=tr2[p*2]+tr2[p*2+1];
}
}
int main(){
cin >> n;
for(int i=1;i<=n;++i){
cin >> a[i].x >> a[i].y >> a[i].x2 >> a[i+n].y;
a[i+n].x=a[i].x;a[i+n].x2=a[i].x2;
a[i].w=-1;a[i+n].w=1;
z[i]=a[i].x;z[i+n]=a[i].x2;
}
n<<=1;
sort(z+1,z+n+1);
sort(a+1,a+n+1,cmp);
int cnt=unique(z+1,z+n+1)-z-1;
for(int i=1;i<=n;++i){
a[i].x=lower_bound(z+1,z+n+1,a[i].x)-z;
a[i].x2=lower_bound(z+1,z+n+1,a[i].x2)-z;
}
ll ans=0,res;
add(1,1,n,a[1].x,a[1].x2-1,a[1].w); //
for(int i=2;i<=n;++i){
ans+=tr2[1]*(a[i-1].y-a[i].y);
add(1,1,n,a[i].x,a[i].x2-1,a[i].w);
}
cout << ans;
return 0;
}
查看13道真题和解析
