严格单 $\log$ 做法,附实现细节和代码。
考虑从左往右扫描线,发现每次操作是线段上端点 $-1$,插入线段,删除退化成点的线段。
如果某时刻一条线段被另一条完全覆盖,那么这条线段显然不会产生贡献,可以删去。最后得到的线段一定是左端点单调递增时,右端点也单调递增,可以用 set 维护。
当两线段相交时,下方线段上端点的改变并不会影响总覆盖长度。于是想到用小根堆维护相交区域,当有相交区域缩小至 $0$ 时删去。每次更新长度时减少的就是 set 的 $size$ 减去堆的 $size$。
删除是平凡的。插入时,若线段被已有线段包含,则不需插入。否则,将它包含的线段及其之间的交从 set 和堆中删去,并将中间未被覆盖的区域贡献到当前长度。最后再将其与上/下线段之间的交更新。
时间复杂度分析:set 和堆插入删除都是 $O(\log{N})$ 的,初始和结束时两者皆空。插入一条线段时最多在 set 和堆中加入三个元素(线段本身及其与上下线段的交)。因此只有 $O(N)$ 个元素被插入删除,总复杂度 $O(N\log{N})$。
实现细节:
-
因为堆不支持直接删除,可以使用懒标记,对于每一条线段记录与上方线段的交的编号,在取堆顶元素时判一下即可。因为懒标记,所以不能用
q.size()
直接得到堆中元素个数,要另外记录。 -
对于线段上端点整体 $-1$ 的情况,虽然纵坐标改变,但横坐标+纵坐标的值不变,可以用此值比较右端点大小。堆中也可用此方法判断线段的交是否已退化成点。
-
虽然结果在 int 范围内,但计算梯形面积时可能会爆,要开 long long。
-
corner case 很多,要小心 RE 和 边界条件。
最后附上丑陋的代码:
#include<bits/stdc++.h>
using namespace std;
const int N=50005;
#define int long long
int n,num,l[N],cnt; bool v[N*3],vl[N];
int id[N*2];
struct tri{
int x,y,l;
bool operator<(const tri &a)const{return x<a.x;}
}t[N];
struct len{
int x,id;
bool operator<(const len &a)const{return x>a.x||x==a.x&&id<a.id;}
};
struct seg{
int y,z,id;
bool operator<(const seg &a)const{return y<a.y||y==a.y&&z<a.z;}
};
set<seg> s;
priority_queue<len> q;
vector<len> op[N*2];
set<seg>::iterator it,itl;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0); cin>>n;
for(int i=1;i<=n;i++){
cin>>t[i].x>>t[i].y>>t[i].l;
id[i*2-1]=t[i].x,id[i*2]=t[i].x+t[i].l;
}int x,xl,zl,qc=0;
sort(t+1,t+n+1); sort(id+1,id+n*2+1); cnt=unique(id+1,id+n*2+1)-(id+1);
for(int i=1;i<=n;i++){
x=lower_bound(id+1,id+cnt+1,t[i].x)-id; op[x].push_back({1,i});
x=lower_bound(id+1,id+cnt+1,t[i].x+t[i].l)-id; op[x].push_back({-1,i});
}v[0]=1;
int nx=-2e9,ny=0,px,py=0,ans=0;
for(int i=1;i<=cnt;i++){
while(q.size()&&v[q.top().id]) q.pop();
while(q.size()&&q.top().x<=id[i]){
px=nx; nx=q.top().x;
py=ny; ny-=(nx-px)*(s.size()-qc);
if(px!=-2e9) ans+=(py+ny)*(nx-px);
while(q.size()&&(q.top().x==nx||v[q.top().id])){
if(!v[q.top().id]) qc--; v[q.top().id]=1; q.pop();
}
}
px=nx; nx=id[i];
py=ny; ny-=(nx-px)*(s.size()-qc);
if(px!=-2e9) ans+=(py+ny)*(nx-px);
for(int j=0;j<op[i].size();j++){
x=op[i][j].id;
if(op[i][j].x==-1&&!vl[x]){
it=s.find({t[x].y,t[x].x+t[x].y+t[x].l}); s.erase(it);
}
else if(!vl[x]){
it=s.lower_bound({t[x].y,-2000000000,-2000000000});
if(it!=s.begin()){
if(it!=s.end()){itl=it;itl--;
if((*itl).y<=t[x].y&&(*itl).z>=t[x].x+t[x].y+t[x].l){vl[x]=1;continue;}
if((*it).y<=t[x].y&&(*it).z>=t[x].x+t[x].y+t[x].l){vl[x]=1;continue;}
if(!v[l[(*itl).id]])qc--;v[l[(*itl).id]]=1;
if((*it).z<=t[x].x+t[x].y+t[x].l)ny+=max(min(id[i]+t[(*it).id].y-(*itl).z,t[(*it).id].y-t[x].y),0ll);
else{
ny+=t[x].l; ny-=min(max(t[x].x+t[x].y+t[x].l-id[i]-t[(*it).id].y,0ll)+max((*itl).z-t[x].x-t[x].y,0ll),t[x].l);
}
while(it!=s.end()&&(*it).z<=t[x].x+t[x].y+t[x].l){
xl=(*it).id,vl[xl]=1;zl=(*it).z; it++; if(!v[l[xl]])qc--; v[l[xl]]=1;
if(it!=s.end()&&(*it).z<=t[x].x+t[x].y+t[x].l) ny+=max(t[(*it).id].y+id[i]-zl,0ll);
else if(it!=s.end()) ny+=max(min(id[i]+t[(*it).id].y-zl,t[x].x+t[x].y+t[x].l-zl),0ll);
else ny+=t[x].x+t[x].y+t[x].l-zl; it--; it=s.erase(it);
}
if((*itl).z>t[x].x+t[x].y){
num++,l[(*itl).id]=num,q.push({id[i]+(*itl).z-t[x].x-t[x].y,num}),qc++;
}
if(it!=s.end()&&t[x].x+t[x].y+t[x].l>id[i]+t[(*it).id].y){
num++,l[x]=num,q.push({id[i]+t[x].x+t[x].y+t[x].l-id[i]-t[(*it).id].y,num}),qc++;
}
}
else{itl=it; itl--;
if((*itl).z>=t[x].x+t[x].y+t[x].l){vl[x]=1;continue;}ny+=t[x].l;
if((*itl).z>t[x].x+t[x].y){
num++,l[(*itl).id]=num,q.push({id[i]+(*itl).z-t[x].x-t[x].y,num}),qc++; ny-=(*itl).z-t[x].x-t[x].y;
}
}
}
else{
if(it!=s.end()&&(*it).y<=t[x].y&&(*it).z>=t[x].x+t[x].y+t[x].l){vl[x]=1;continue;}
if(it==s.end()) ny+=t[x].l;
else if((*it).z>t[x].x+t[x].y+t[x].l){
ny+=t[x].l; ny-=max(t[x].x+t[x].y+t[x].l-id[i]-t[(*it).id].y,0ll);
}
else ny+=t[(*it).id].y-t[x].y;
while(it!=s.end()&&(*it).z<=t[x].x+t[x].y+t[x].l){
xl=(*it).id,vl[xl]=1;zl=(*it).z; it++; if(!v[l[xl]])qc--; v[l[xl]]=1;
if(it!=s.end()&&(*it).z<=t[x].x+t[x].y+t[x].l) ny+=max(t[(*it).id].y+id[i]-zl,0ll);
else if(it!=s.end()) ny+=max(min(id[i]+t[(*it).id].y-zl,t[x].x+t[x].y+t[x].l-zl),0ll);
else ny+=t[x].x+t[x].y+t[x].l-zl; it--; it=s.erase(it);
}
if(it!=s.end()&&t[x].x+t[x].y+t[x].l>id[i]+t[(*it).id].y){
num++,l[x]=num,q.push({id[i]+t[x].x+t[x].y+t[x].l-id[i]-t[(*it).id].y,num}),qc++;
}
}
s.insert({t[x].y,t[x].x+t[x].y+t[x].l,x});
}
}
}
cout<<fixed<<setprecision(1)<<(double)(ans)/(double)2;
return 0;
}
实测在 P3219 上跑 $60ms$,目前最优解,比第二快五倍。在 P1222 上 rk4。(可能是数据太水了,因为我调试时还一堆锅的代码都过了)
标签:itl,ny,int,题解,线段,HNOI2012,num,三角形,id From: https://www.cnblogs.com/skh504535/p/18009517