CF983D Arkady and Rectangles

· · 题解

首先对这个平面从左往右扫描线。

使用线段树，每个节点维护 p 一个 set，表示所有完全覆盖这个节点的值。可以发现，颜色 x 能够在某个时刻被看到，当且仅当在线段树上存在一条从根到叶子的路径，满足这条路径上的最大值是 x。

于是我们可以对于每一个节点 p 维护 mn_p 从这个节点到某个叶子的路径上的最大值的最小值。在 p 处插入 x 的时候，我们利用当前节点父链上的最大值以及 mn_p 就可以 O(1) 地知道这种颜色当前是否能看到。

我们还要解决另一个问题：可能有一些颜色一开始被别的覆盖了，但覆盖它的颜色比它早删除，它在后面被看到了。

此时一个朴素做法就是遍历整棵线段树，每次走到一个节点 p，就把 p 中所有当前能看到的颜色暴力找出来，并标记为被看到过。但这样时间复杂度是 O(n^2\log n) 的，显然不能接受。

对于每一个节点再维护 vl_p 表示当前节点的 set 中没有被看到过的颜色的最大值，ps_p 表示满足 q 在 p 的子树内且 vl_q>mn_q 的 vl_q 的最大值。

维护了这两个值之后，我们就可以 O(1) 地判断 p 的子树内是否存在当前第一次被看到。而我们每次花费 O(\log n) 的代价找到一种当前第一次被看到的颜色。因此总时间复杂度为 O(n\log^2 n)。

实际上可以用 priority_queue 代替 set 来降低常数。

upd：感谢 @WaReTle 指出之前的代码复杂度写假了，现已进行更正。

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define mid ((l+r)/2)
#define pb push_back
const int N=2e5+5;
int n,ans,dsX[N],dsY[N];bool vs[N],vs1[N];struct Rect {int x1,y1,x2,y2;}a[N];
struct Node {int l,r,w;};vector<Node> vc1[N],vc2[N];
struct Seg {int mn,mx,vl,ps;priority_queue<int> z,z1;}sg[N*4];
void build(int p,int l,int r)
{
    sg[p].z.push(0);sg[p].z1.push(0);
    if(l==r) return;build(p*2,l,mid);build(p*2+1,mid+1,r);
}
void pu(int p,int l,int r)
{
    sg[p].mn=max((l<r?min(sg[p*2].mn,sg[p*2+1].mn):0),sg[p].mx);
    sg[p].ps=max((l<r?max(sg[p*2].ps,sg[p*2+1].ps):0),sg[p].vl);
    if(sg[p].ps<sg[p].mn) sg[p].ps=0;
}
void mdf1(int p,int w,int mx)
{
    if(w>=max(mx,sg[p].mn)) vs1[w]=1;else sg[p].vl=max(sg[p].vl,w);
    sg[p].mx=max(sg[p].mx,w);sg[p].z.push(w);sg[p].z1.push(w);
}
void mdf2(int p,int w,int mx)
{
    while(vs[sg[p].z.top()]) sg[p].z.pop();
    while(vs[sg[p].z1.top()] || vs1[sg[p].z1.top()]) sg[p].z1.pop();
    sg[p].mx=sg[p].z.top();sg[p].vl=sg[p].z1.top();
}
void mdf(int p,int mx)
{
    while(sg[p].vl && sg[p].vl>=max(mx,sg[p].mn))
    {
        vs1[sg[p].vl]=1;
        while(vs[sg[p].z1.top()] || vs1[sg[p].z1.top()]) sg[p].z1.pop();
        sg[p].vl=sg[p].z1.top();
    }
}
void upd1(int p,int l,int r,int qL,int qR,int w,int mx)
{
    mx=max(mx,sg[p].mx);
    if(l>=qL && r<=qR) {mdf1(p,w,mx);pu(p,l,r);return;}
    if(qL<=mid) upd1(p*2,l,mid,qL,qR,w,mx);
    if(qR>mid) upd1(p*2+1,mid+1,r,qL,qR,w,mx);pu(p,l,r); 
}
void upd2(int p,int l,int r,int qL,int qR,int w,int mx)
{
    mx=max(mx,sg[p].mx);
    if(l>=qL && r<=qR) {mdf2(p,w,mx);pu(p,l,r);return;}
    if(qL<=mid) upd2(p*2,l,mid,qL,qR,w,mx);
    if(qR>mid) upd2(p*2+1,mid+1,r,qL,qR,w,mx);pu(p,l,r);
}
void upd(int p,int l,int r,int mx)
{
    mx=max(mx,sg[p].mx);if(!sg[p].ps || sg[p].ps<mx) return;
    mdf(p,mx);if(l==r) {pu(p,l,r);return;}
    upd(p*2,l,mid,mx);upd(p*2+1,mid+1,r,mx);pu(p,l,r);
}
int main()
{
    scanf("%d",&n);
    for(int i=1,x1,y1,x2,y2;i<=n;++i)
    {
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);a[i]=(Rect) {x1+1,y1+1,x2,y2};
        dsX[++dsX[0]]=x1;dsX[++dsX[0]]=x2;dsY[++dsY[0]]=y1;dsY[++dsY[0]]=y2;
    }
    sort(dsX+1,dsX+dsX[0]+1);dsX[0]=unique(dsX+1,dsX+dsX[0]+1)-dsX-1;
    sort(dsY+1,dsY+dsY[0]+1);dsY[0]=unique(dsY+1,dsY+dsY[0]+1)-dsY-1;
    for(int i=n;i;--i)
    {
        a[i].x1=lower_bound(dsX+1,dsX+dsX[0]+1,a[i].x1)-dsX;
        a[i].x2=lower_bound(dsX+1,dsX+dsX[0]+1,a[i].x2)-dsX;
        a[i].y1=lower_bound(dsY+1,dsY+dsY[0]+1,a[i].y1)-dsY;
        a[i].y2=lower_bound(dsY+1,dsY+dsY[0]+1,a[i].y2)-dsY;
        vc1[a[i].x1].pb((Node) {a[i].y1,a[i].y2,i});
        vc2[a[i].x2].pb((Node) {a[i].y1,a[i].y2,i});
    }
    build(1,1,dsY[0]);
    for(int i=1;i<=dsX[0];++i)
    {
        for(auto j:vc1[i]) upd1(1,1,dsY[0],j.l,j.r,j.w,0);upd(1,1,dsY[0],0);
        for(auto j:vc2[i]) vs[j.w]=1,upd2(1,1,dsY[0],j.l,j.r,j.w,0);
    }for(int i=1;i<=n;++i) if(vs1[i]) ++ans;printf("%d\n",ans+1);return 0;
}