【[SHOI2007]园丁的烦恼】

\(CDQ\) 分治的神奇操作

这个问题跟偏序问题好像差的不小啊

但是就是可以转化过去

对于一个查询我们可以把它拆成四个，也就是用二维前缀和的方式来查询

我们发现其实前缀和的定义就是多少个点的横纵坐标都小于这个点

典型的偏序问题

于是直接上\(cdq\)了

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#define re register

#define maxn 500005

#define LL long long

#define min(a,b) ((a)<(b)?(a):(b))

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

#define lowbit(x) ((x)&(-x))

inline int read()

{

	char c=getchar();

	int x=0;

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

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

		x=(x<<3)+(x<<1)+c-48,c=getchar();

	return x;

}

struct Node

{

	int x,y,ans,o,rk;

}b[maxn*5],a[maxn*5];

int c[2][maxn*10];

int n,m,tot,num;

int sz[2],Ans[maxn];

int bit[maxn*10];

inline int ask(int x){int now=0;for(re int i=x;i;i-=lowbit(i)) now+=bit[i];return now;}

inline void add(int x,int val){for(re int i=x;i<=sz[1];i+=lowbit(i)) bit[i]+=val;}

inline int find(int x,int o)

{

	int l=1,r=sz[o];

	while(l<=r)

	{

		int mid=l+r>>1;

		if(c[o][mid]==x) return mid;

		if(c[o][mid]>x) r=mid-1;

			else l=mid+1;

	}

	return 0;

}

inline int cmp(Node A,Node B)

{

	if(A.x==B.x) return A.y<B.y;

	return A.x<B.x;

}

void CDQ(int s,int t)

{

	if(s==t) return;

	int mid=s+t>>1;

	CDQ(s,mid),CDQ(mid+1,t);

	int i=s,j=mid+1,p=i;

	while(i<=mid&&j<=t)

	{

		if(b[i].x<=b[j].x)

		{

			if(!b[i].o) add(b[i].y,1);

			a[p++]=b[i++];

		}

		else

		{

			if(b[j].o) b[j].ans+=ask(b[j].y);

			a[p++]=b[j++];

		}

	}

	while(j<=t)

	{

		if(b[j].o) b[j].ans+=ask(b[j].y);

		a[p++]=b[j++];

	}

	for(re int k=s;k<i;k++) if(!b[k].o) add(b[k].y,-1);

	while(i<=mid) a[p++]=b[i++];

	for(re int k=s;k<=t;k++) b[k]=a[k];

}

int main()

{

	n=read(),m=read();

	tot=0;

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

		b[i].x=read(),b[i].y=read(),c[0][++tot]=b[i].x,c[1][tot]=b[i].y;

	num=n;

	int xx,yy,X,Y;

	for(re int i=1;i<=m;i++)

	{

		xx=read(),yy=read(),X=read(),Y=read();

		b[++num].x=X,b[num].y=Y,b[num].o=1,b[num].rk=i;

		c[0][++tot]=b[num].x,c[1][tot]=b[num].y;

		b[++num].x=xx-1,b[num].y=yy-1,b[num].o=1,b[num].rk=i;

		c[0][++tot]=b[num].x,c[1][tot]=b[num].y;

		b[++num].x=X,b[num].y=yy-1,b[num].o=2,b[num].rk=i;

		c[0][++tot]=b[num].x,c[1][tot]=b[num].y;

		b[++num].x=xx-1,b[num].y=Y,b[num].o=2,b[num].rk=i;

		c[0][++tot]=b[num].x,c[1][tot]=b[num].y;

	}

	std::sort(c[0]+1,c[0]+tot+1);

	std::sort(c[1]+1,c[1]+tot+1);

	sz[0]=std::unique(c[0]+1,c[0]+tot+1)-c[0]-1;

	sz[1]=std::unique(c[1]+1,c[1]+tot+1)-c[1]-1;

	for(re int i=1;i<=num;i++)

		b[i].x=find(b[i].x,0),b[i].y=find(b[i].y,1);

	CDQ(1,num);

	for(re int i=1;i<=num;i++)

	{

		if(!b[i].o) continue;

		if(b[i].o==1) Ans[b[i].rk]+=b[i].ans;

			else Ans[b[i].rk]-=b[i].ans;

	}

	for(re int i=1;i<=m;i++)

		printf("%d\n",Ans[i]);

	return 0;

}

【[SHOI2007]园丁的烦恼】的相关教程结束。