扫描线

What a Colorful Wall

https://codeforces.com/gym/103443/problem/F

题意:n个有颜色的矩形按顺序放在平面上,被覆盖的部分颜色不可见,求最后可见的颜色数

矩形覆盖的问题很自然想到扫描线,先把矩形离散,按x坐标排序,并拆分为加入线段和删除线段两部分.线段树维护y轴,每个时刻先增删线段,每个节点挂一个可删堆维护当前区间内时间最大矩形的颜色,最后dfs全树,查询当前时刻能看到颜色种类.每次查询复杂度$O(nlogn)$,总共有n次询问,总复杂度$O(n^2logn)$,可以勉强卡过.

//黑科技可删堆
struct HEAP{
    priority_queue <pii> p,q;
    void add(pii x){p.push(x);}
    void del(pii x){q.push(x);}
    void mt(){while(p.size()&&q.size()&&q.top()==p.top())p.pop(),q.pop();}
    pii top(){mt();return p.top();}
    bool empty(){mt();return p.empty();}
};
//此处和通常的线段树稍有不同,由于维护的实际上是矩形的边,表示颜色块需要边界-1
void add(int p,int l,int r){
    if(ql<=l&&r<=qr) {ar[p].add(qii);return ;}
    if(ql<mid) add(ls,l,mid);
    if(mid<qr) add(rs,mid,r);
}
void del(int p,int l,int r){
    if(ql<=l&&r<=qr) {ar[p].del(qii);return ;}
    if(ql<mid) del(ls,l,mid);
    if(mid<qr) del(rs,mid,r);
}
void dfs(int p,int l,int r,pii pi){
    if(!ar[p].empty()) pi=max(pi,ar[p].top());
    if(r-l==1){ans[pi.second]=1;return ;}
    dfs(ls,l,mid,pi),dfs(rs,mid,r,pi);
}
void solve(){
    po=pii(0,0);
    For(i,1,ttx){
        for(auto x:vad[i]) qii=pii(x.id,ocl[x.id]),ql=x.l,qr=x.r,add(1,1,tty);
        for(auto x:vde[i]) qii=pii(x.id,ocl[x.id]),ql=x.l,qr=x.r,del(1,1,tty);
        dfs(1,1,tty,po);
    }
    int cnt=0;For(i,1,n)cnt+=ans[i];
    cout<<cnt;
}

一个更好的做法就是在每个时刻维护每种颜色可见的总长度,直接在增删线段时更新,不需要再dfs,复杂度$O(nlogn)$.

需要注意的是,如果直接用二维线段树或外层暴力内层线段树,虽然理论复杂度是$O(n^2logn)$的,但是常数巨大,无法通过(存疑).