BZOJ 1790: [Ahoi2008]Rectangle 矩形藏宝地

题目传送门

【题目大意】

　　游戏的主办方把这块开阔地当作第一象限，将所有可能埋藏宝藏的地方划成一个个矩形的土地，并把这些矩形土地的坐标都告诉了参赛者。挖宝的提示很简单，只要某一个矩阵土地至少被另外一个矩阵土地所包含，那么这个矩阵土地里肯定埋有宝藏。问：有多少个矩形土地里肯定埋有宝藏？

　　其实就是求对于矩形i，是否存在一个矩形j，使得aj＜ai，bj＜bi，cj＞ci，dj＞di。

　　并不要求在线，用离线算法就好了。（CDQ分治）

　　先对a排序，取mid，表示i小于等于mid的标记为添加，大于mid的标记为查询。

　　再对b排序，保证b是从小到大的，遇到添加的就将c作为下标，存d（线段树维护最大值），查询的就询问c+1~n的最大值是否大于d，是，标记当前矩形为藏宝地，不能直接ans++，会计算重复。

　　为什么这是对的？

　　因为查询的a一定比添加的a大，又对b进行排序，又保证了b有序。那么查询的矩阵A找到的添加的矩阵B，一定是B.a＜A.a，B.b＜A.b，剩下的就不解释了……

　　这题卡常，排序一定要写好。（TLE了好多次……）

#include<cstdio>

#include<algorithm>

#define imax(a,b) ((a>b)?(a):(b))

using namespace std;

const int N=200010;

int A[N],B[N],C[N],D[N],*Ry,id[N];

struct data{ int id; bool p; } np[N];

int n,px,T[N<<2],ans;

bool vis[N];

void updata(int ro,int L,int R,int x,int val)

{

	if(x<L || x>R) return;

	if(L==x && R==x)

	{

		T[ro]=val;

		return;

	}

	int Mid=(L+R)>>1;

	updata(ro<<1,L,Mid,x,val); updata(ro<<1|1,Mid+1,R,x,val);

	T[ro]=imax(T[ro<<1],T[ro<<1|1]);

}

int query(int ro,int L,int R,int li,int ri)

{

	if(L>ri || R<li) return 0;

	if(li<=L && R<=ri) return T[ro];

	int Mid=(L+R)>>1;

	int q1=query(ro<<1,L,Mid,li,ri),q2=query(ro<<1|1,Mid+1,R,li,ri);

	return imax(q1,q2);

}

bool cmp(int a,int b) { return (Ry[a]<Ry[b]); }

bool Cmp(data A,data B) { return (Ry[A.id]<Ry[B.id]); }

void CDQ(int L,int R)

{

	if(L==R) return;

	int Mid=(L+R)>>1;

	for(int i=L;i<=Mid;i++) np[i].p=1;

	Ry=B; sort(np+L,np+R+1,Cmp);

	for(int i=L;i<=R;i++)

	{

		if(np[i].p) updata(1,1,n,C[np[i].id],D[np[i].id]); else

		if(query(1,1,n,C[np[i].id]+1,n)>D[np[i].id]) vis[np[i].id]=1;

	}

	for(int i=L;i<=R;i++) if(np[i].p) updata(1,1,n,C[np[i].id],0),np[i].p=0;

	Ry=A; sort(np+L,np+R+1,Cmp);

	CDQ(L,Mid); CDQ(Mid+1,R);

}

int read()

{

	int yu=0;

	char ch=getchar();

	while(ch>'9' || ch<'0') ch=getchar();

	while(ch>='0' && ch<='9')

	{

		yu=(yu<<3)+(yu<<1)+ch-'0';

		ch=getchar();

	}

	return yu;

}

void work()

{

	for(int i=1;i<=n;i++) id[i]=i;

	sort(id+1,id+1+n,cmp);

	for(int i=1;i<=n;i++) Ry[id[i]]=i;

}

int main()

{

	scanf("%d",&n); ans=0;

	for(int i=1;i<=n;i++)

	{

		A[i]=read(); B[i]=read();

		C[i]=read(); D[i]=read();

	}

	Ry=D; work();	Ry=C; work();

	Ry=B; work();	Ry=A; work();

	for(int i=1;i<=n;i++) np[i].id=id[i];

	CDQ(1,n); for(int i=1;i<=n;i++) if(vis[i]) ans++;

	printf("%d\n",ans);

	return 0;

}