欢乐岛上最著名的游戏是一个寻宝游戏,小可可来到宝藏的埋藏地,这是一块开阔地,宝藏被分散的埋藏在这块地下,现在要做的是一件件的把宝藏挖出来。为了提示宝藏的埋藏点,游戏的主办方把这块开阔地当作第一象限,将所有可能埋藏宝藏的地方划成一个个矩形的土地,并把这些矩形土地的坐标都告诉了参赛者。挖宝的提示很简单,只要某一个矩阵土地至少被另外一个矩阵土地所包含,那么这个矩阵土地里肯定埋有宝藏。其实这些宝藏都是一些精美的纪念品,如果谁挖出来了纪念品就归谁了,小可可很想为这次旅程画上完美的句号,有你的帮助他信心十足,你只要告诉他:有多少个矩形土地里肯定埋有宝藏就行了。胜利就在眼前,加油吧!

链接🔗

「AHOI2008」矩形藏宝地

题解

CDQ分治
排序维护 x2 降序
归并维护 y2 降序
树状数组中用 x1的坐标,存y1的值
然后树状数组求前缀和最小值与当前y1比较

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxd = 2e5+10;
struct node
{
    int x1,y1,x2,y2,f;
}e[maxd];
int cmp(const node a,const node b)
{
    return a.x2 > b.x2;
}
int cmp1(const node a,const node b)
{
    return a.y2 > b.y2;
}
int fx[maxd<<1],fy[maxd<<1],totx,toty;
int t[maxd<<1],ans;
void clear(int x)
{
    for(;x<maxd*2;x+=(x&-x)) t[x] = 1e9;
}
void update(int x,int y)
{
    for(;x<maxd*2;x+=(x&-x)) t[x] = min(t[x],y);
}
int query(int x)
{
    int ans = 1e9;
    for(;x;x-=(x&-x)) ans = min(t[x],ans);
    return ans;
}
void cdq(int l,int r)
{
    if(l==r) return;
    int mid = (l+r)/2;
    cdq(l,mid),cdq(mid+1,r);
    sort(e+l,e+mid+1,cmp1); sort(e+mid+1,e+r+1,cmp1); //懒得手动归并,直接排序
    int j = l;
    for(int i=mid+1;i<=r;i++) // 此时j的x2 一定大于i的x2
    {
        if(e[i].f) continue;
        while(j <= mid&&e[j].y2 > e[i].y2) 
            update(e[j].x1,e[j].y1),j++; // 把y1插入数组x1的位置
        int tmp = query(e[i].x1); // 因为查询比 x1小的值,所以查询x1一定小于i的x1;
        if(tmp < e[i].y1) e[i].f = 1,ans++; 
    }
    while(--j>=l) clear(e[j].x1); // 重置
}
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("k.out","w",stdout);
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) 
    {
        scanf("%d %d %d %d",&e[i].x1,&e[i].y1,&e[i].x2,&e[i].y2);
        fx[++totx] = e[i].x1,fx[++totx] = e[i].x2;
        fy[++toty] = e[i].y1,fy[++toty] = e[i].y2;
    }
    sort(fx+1,fx+1+totx);sort(fy+1,fy+1+toty); //离散化 因为不存在相同的,不需要去重复
    for(int i=1;i<=n;i++)
    {
        e[i].x1 = lower_bound(fx+1,fx+1+totx,e[i].x1) - fx;
        e[i].x2 = lower_bound(fx+1,fx+1+totx,e[i].x2) - fx;
        e[i].y1 = lower_bound(fy+1,fy+1+toty,e[i].y1) - fy;
        e[i].y2 = lower_bound(fy+1,fy+1+toty,e[i].y2) - fy;
    }
    sort(e+1,e+1+n,cmp); // 第一维对右x进行排序
    for(int i=1;i<2*maxd;i++) t[i] = 1e9; // 初始化
    cdq(1,n);
    printf("%d",ans);
    return 0;
}