[AHOI2008]RECTANGLE 矩形藏宝地

C++14(g++5.4) 解法, 执行用时: 466ms, 内存消耗: 14284K, 提交时间: 2020-10-07 08:10:50

#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); //对y进行排序
    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;
}

C++(clang++ 11.0.1) 解法, 执行用时: 388ms, 内存消耗: 11460K, 提交时间: 2022-09-28 20:11:56

#include<bits/stdc++.h>
#define ll long long
#define ri ll
#define maxn 200005
#define inf 0x7fffffff
using namespace std;
struct node{
	ll x1,y1,x2,y2,id;
}a[maxn];
ll n,rk[maxn],c[maxn],ans;
bool vis[maxn];
inline bool cmp1(node x,node y){
	return x.x1<y.x1;
}
inline bool cmp2(node x,node y){
	return x.y1<y.y1;
}
inline bool cmp3(node x,node y){
	return x.x2>y.x2;
}
inline bool cmp4(node x,node y){
	return x.y2>y.y2;
}
inline ll lowbit(ri x){
	return x&(~x+1);
}
inline void update(ri x,ri v){
	for(;x<=n;x+=lowbit(x))c[x]=min(c[x],v);
}
inline void era(ri x){
	for(;x<=n;x+=lowbit(x))c[x]=inf;
}
inline ll sum(ri x){
	ri res=inf;
	for(;x;x-=lowbit(x))res=min(res,c[x]);
	return res;
}
inline void CDQ(ri l,ri r){
	if(l==r)return;
	ri mid=l+r>>1;CDQ(l,mid);CDQ(mid+1,r);
	ri i=l,j=mid+1;
	while(j<=r){
		while(i<=mid&&a[i].y2>a[j].y2){
			update(a[i].x1,a[i].y1);++i;
		}
		if(sum(a[j].x1)<a[j].y1)vis[a[j].id]=true;
		++j;
	}
	i=l,j=mid+1;
	while(j<=r){
		while(i<=mid&&a[i].y2>a[j].y2){
			era(a[i].x1);++i;
		}
		++j;
	}
	sort(a+l,a+r+1,cmp4);
}
int main()
{
	scanf("%lld",&n);
	for(ri i(1);i<=n;++i)
	scanf("%lld%lld%lld%lld",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
	for(ri i(1);i<=n;++i)a[i].id=i;
	sort(a+1,a+n+1,cmp1);ri sz(0);rk[1]=++sz;
	for(ri i(2);i<=n;++i)
	{
		if(a[i].x1!=a[i-1].x1)++sz;
		rk[i]=sz;
	}
	for(ri i(1);i<=n;++i)a[i].x1=rk[i];
	sort(a+1,a+n+1,cmp3);
	memset(c,0x7f,sizeof(c));CDQ(1,n);
	for(ri i(1);i<=n;++i)if(vis[i])++ans;
	printf("%lld\n",ans);
	return 0;
}

详情