P3219 [HNOI2012] 三角形覆盖问题&P1222 三角形 题解
严格单 \log 做法，附实现细节和代码。
考虑从左往右扫描线，发现每次操作是线段上端点
如果某时刻一条线段被另一条完全覆盖，那么这条线段显然不会产生贡献，可以删去。最后得到的线段一定是左端点单调递增时，右端点也单调递增，可以用 set 维护。
当两线段相交时，下方线段上端点的改变并不会影响总覆盖长度。于是想到用小根堆维护相交区域，当有相交区域缩小至
删除是平凡的。插入时，若线段被已有线段包含，则不需插入。否则，将它包含的线段及其之间的交从 set 和堆中删去，并将中间未被覆盖的区域贡献到当前长度。最后再将其与上/下线段之间的交更新。
时间复杂度分析：set 和堆插入删除都是
实现细节：
-
因为堆不支持直接删除，可以使用懒标记，对于每一条线段记录与上方线段的交的编号，在取堆顶元素时判一下即可。因为懒标记，所以不能用
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 上跑