扫描线

· · 题解

看讨论区有人问，就水了一下这题，居然没人交过。

一看题面就是扫描线，但是这是三角形，很不好处理了。看下数据范围发现非常小，于是想到一种大胆的做法，我们考虑对于一个面来说，除了三角形最上面的那个点，其他的点都会往后产生 1 的贡献，而三角形最上面的那个点会产生 0.5 的贡献，n 和 m 都非常小，于是我们就可以暴力维护这些顶点，每次把这些点往下走一格，然后一个个单点修改，每次的代价就是线段树里覆盖的所有点，加上没被线段树里的点覆盖的顶点个数除以 2。x，y 很大，离散化后与一般板子的扫描线不同，我们直接枚举 x 坐标而不是把三角形排序，复杂度 O(n^2\operatorname{log}n)。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6+2;
const int N=2002;
struct Segment{//这部分可以直接用暴力省掉，并且复杂度更小
    int T[MAXN<<2],lz[MAXN<<2];
    #define ls p<<1
    #define rs p<<1|1
    void tag(int p,int l,int r,int x) {
        lz[p]+=x;
        if(lz[p]) T[p]=r-l+1;
        else T[p]=0;
    }
    void pushdown(int p,int l,int r,int mid) {
        if(!lz[p]) return ;
        tag(ls,l,mid,lz[p]);
        tag(rs,mid+1,r,lz[p]);
        lz[p]=0;
    }
    void update(int p,int l,int r,int L,int R,int x) {
        if(l>=L&&r<=R) return tag(p,l,r,x);
        int mid=l+r>>1;
        pushdown(p,l,r,mid);
        if(mid>=L) update(ls,l,mid,L,R,x);
        if(mid<R) update(rs,mid+1,r,L,R,x);
        T[p]=T[ls]+T[rs];
    }
    int ask(int p,int l,int r,int x) {
        if(l==r) return T[p];
        int mid=l+r>>1;
        pushdown(p,l,r,mid);
        if(mid>=x) return ask(ls,l,mid,x);
        else return ask(rs,mid+1,r,x);
    }
}tr;
struct Node{
    int x,y,m;
}s[N];
struct node{
    int y,m;
};
vector<node>v[MAXN];
pair<int,int>l1[N],l2[N];
int n;
typedef pair<int,int> P;
double ans;
#define fs first 
#define sc second 
P q[N],cp[N];
int s1,s2;
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d%d%d",&l1[i].fs,&l2[i].fs,&s[i].m);
        l1[i].sc=l2[i].sc=i;
    }
    sort(l1+1,l1+n+1);sort(l2+1,l2+n+1);
    for(int i=2;i<=n;i++) {//离散化部分
        if(l2[i].fs-l2[i-1].fs<=1000) s[l2[i].sc].y=s[l2[i-1].sc].y+l2[i].fs-l2[i-1].fs;
        else s[l2[i].sc].y=s[l2[i-1].sc].y+1000;
        if(l1[i].fs-l1[i-1].fs<=1000) s[l1[i].sc].x=s[l1[i-1].sc].x+l1[i].fs-l1[i-1].fs;
        else s[l1[i].sc].x=s[l1[i-1].sc].x+1000;
    }
    for(int i=1;i<=n;i++) 
        v[s[i].x].push_back((node){s[i].y,s[i].m});
    q[0].fs=-1;
    for(int i=0;i<MAXN-1;i++) {
        s2=0;
        for(int j=1;j<=s1;j++) {
            P p=q[j];--p.fs;
            if(--p.sc>0) tr.update(1,1,MAXN-2,p.fs,p.fs,-1);
            if(p.sc) cp[++s2]=p;
        }
        for(int j=1;j<=s2;j++)
            q[j]=cp[j]; s1=s2;
        for(int j=0;j<v[i].size();j++) {
            P p=P(v[i][j].m+v[i][j].y,v[i][j].m);
            if(v[i][j].m>1) tr.update(1,1,MAXN-2,v[i][j].y+1,p.fs-1,1);
            q[++s1]=p;
        }
        stable_sort(q+1,q+s1+1);//这里排序是防止位置相同的顶点算两次
        ans+=tr.T[1];
        for(int j=1;j<=s1;j++) {
            if(q[j].fs==q[j-1].fs) continue;//这里去重
            if(!tr.ask(1,1,MAXN-2,q[j].fs)) ans+=0.5;
        }
    }
    printf("%.1f",ans);
    return 0;
}

写到这里发现，其实因为 n\times m 非常小，所以其实都不需要线段树，直接暴力即可（甚至复杂度更小）。