自动搬运

查看原文

来自洛谷，原作者为

	天命之路 嗟尔日出，嗟尔日暮

搬运于2025-08-24 22:15:08，当前版本为作者最后更新于2021-10-16 14:44:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

写在前面

一道一眼的 cdq 分治题

当然了啊，假如你想写树套树或者 KD-Tree，那当我没说

正题

首先把总对数对化为“加入一个图形时新贡献的对数”，最后把答案求前缀和即可

然后看到这种题目，考虑一下，发现加入一个矩形十分难以处理，决定化动为静

化动态为静态，当然 cdq，品牌首选，匠心传承

考虑 cdq(l,r) 的过程

首先往左右两边递归，不需多言

然后区间分为 $[l,mid]$ 和 $[mid+1,r]$ ，开始计算

我们要计算两个东西：

1. 左半边点对右半边矩形的贡献
2. 左半边矩形对右半边点的贡献

先掏个树状数组出来

考虑把一个矩形$(x1,y1,x2,y2)$ 拆成 $(x1-1,y1,y2)$ 和 $(x2,y1,y2)$ ，他们分别表示 $x\le x1-1,y \in[y1,y2]$ 的点的数量 和 $x\le x2,y \in[y1,y2]$ 的点的数量 ，最后将两相减即可

然后把他们和点扔在一起，按 $x$ 坐标从小到大排序

**尤其注意！！！坐标相同时，修改排在询问前面，这是 cdq 分治的铁则 **

然后遍历，遇点加点，遇询问查询区间和即可

再看第二部分

因为矩形变成了修改，所以我们要借鉴一下扫描线的套路

把矩形 $(x1,y1,x2,y2)$ 拆成两条带"权"的线段 $(x1,y1,y2,1)$ 和 $(x2+1,y1,y2,-1)$ 表示当直线 扫到 $x = x1$

时，$y \in [y1,y2]$ 的点都会多被贡献一个，当扫到 $x = x2+1$ 时，$y\in[y1,y2]$ 的点都会被少贡献一个

依照之前的方法排序

遇修改则区间加，遇询问则单点查，树状数组区间加可以用差分，不会的请左转 “树状数组2” 了解详情

然后就做完了，记得离散化 $y$ 坐标

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
typedef long long ll;
struct event{
	int tp;
	int x,y;
	int a1,b1,a2,b2;
	event(){}
	event(const int _x,const int _y):
	x(_x),y(_y){ tp = 1;}
	event(const int _a1,const int _b1,const int _a2,const int _b2):
	a1(_a1),b1(_b1),a2(_a2),b2(_b2){tp = 2;}
};
event Q[N];
ll ans[N];
int n;
int valy[N*3],leny=0;
#define idx(x) (lower_bound(valy+1,valy+leny+1,(x))-valy)
struct line{
	int x,l,r,tp,id;
	line(){}
	line(const int _x,const int _l,const int _r,const int _tp,const int _id):
	x(_x),l(_l),r(_r),tp(_tp),id(_id){}
};
int tr[N*3];
#define lowbit(x) (x&(-x))
inline void upd(int x,int v) { ++x;for(int i=x;i<=leny+1;i+=lowbit(i)) tr[i] += v;}
inline int Sum(int x) {++x;int res = 0;for(int i=x;i;i^=lowbit(i)) res += tr[i];return res;}
inline int Qry(int l,int r) { return Sum(r)-Sum(l-1);}
inline void inc(int l,int r,int v) { upd(l,v);upd(r+1,-v);}
inline bool cmp1(const line &a,const line &b)
{
	if(a.x != b.x) return a.x < b.x;
	if(a.tp != 0 && b.tp == 0) return true;   //修改排在询问前面，这里通过判断tp是否为0来区分修改和询问
	if(a.tp == 0 && b.tp != 0) return false;
	return a.tp <b.tp; 
}
inline bool cmp2(const line &a,const line &b)
{
	if(a.x != b.x) return a.x < b.x;
	if(a.tp != 0 && b.tp == 0) return false;  //到了第二部分,tp的赋值规则有所改变，cmp要跟着改变
	if(a.tp == 0 && b.tp != 0) return true;
	return a.tp <b.tp;  //你这里写true 或false 是不行的，因为sort 的 CMP 函数必须满足严格偏序关系，即具有非自反，反对称，传递性的关系，否则就会出现奇怪的 RE 和 TLE 等问题
}
line a[N*3];
inline void cdq(int l,int r)
{
	if(l == r) return;
	int mid = l + r >> 1;
	cdq(l,mid);cdq(mid+1,r);
	//左半边矩形对右半边点的贡献
	
	int tot = 0;
	for(int i=l;i<=mid;i++)
		if(Q[i].tp == 2) 
		a[++tot] = line(Q[i].a1,Q[i].b1,Q[i].b2,1,0),
		a[++tot] = line(Q[i].a2+1,Q[i].b1,Q[i].b2,-1,0);
	for(int i=mid+1;i<=r;i++)
		if(Q[i].tp == 1)
			a[++tot] = line(Q[i].x,Q[i].y,Q[i].y,0,i);
	sort(a+1,a+tot+1,cmp1);
	for(int i=1;i<=tot;i++)
	{
		if(a[i].tp != 0)
		inc(a[i].l,a[i].r,a[i].tp);
		else ans[a[i].id] += Sum(a[i].l);
	}
	for(int i=1;i<=tot;i++) if(a[i].tp != 0) inc(a[i].l,a[i].r,-a[i].tp);
	tot = 0;
	//左半边点对右半边矩形的贡献
	for(int i=l;i<=mid;i++)
		if(Q[i].tp == 1)
			a[++tot] = line(Q[i].x,Q[i].y,Q[i].y,0,0);
	for(int i=mid+1;i<=r;i++)
		if(Q[i].tp == 2)
			a[++tot] = line(Q[i].a1-1,Q[i].b1,Q[i].b2,-1,i),
			a[++tot] = line(Q[i].a2,Q[i].b1,Q[i].b2,1,i);
	sort(a+1,a+tot+1,cmp2);
	for(int i=1;i<=tot;i++)
	{
		if(a[i].tp == 0) upd(a[i].l,1);
		else
			ans[a[i].id] += a[i].tp * Qry(a[i].l,a[i].r);
	}
	for(int i=1;i<=tot;i++) if(a[i].tp == 0) upd(a[i].l,-1);  //清空，不要Memset,cdq(l,r) 的算贡献的复杂度必须控制在 r-l 量级，才能保证总复杂度正确
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int tp;
		scanf("%d",&tp);
		if(tp == 1)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			Q[i] = event(x,y);
			valy[++leny] = y;
		}
		else
		{
			int a1,b1,a2,b2;
			scanf("%d%d%d%d",&a1,&b1,&a2,&b2);
			Q[i] = event(a1,b1,a2,b2);
			valy[++leny] = b1;valy[++leny] = b2;
		}
	}
	sort(valy+1,valy+leny+1);
	leny = unique(valy+1,valy+leny+1) - valy - 1;
	for(int i=1;i<=n;i++)
		if(Q[i].tp == 1) Q[i].y = idx(Q[i].y);
		else Q[i].b1 = idx(Q[i].b1),Q[i].b2 = idx(Q[i].b2);
	cdq(1,n);
	for(int i=1;i<=n;i++) ans[i] += ans[i-1];
	for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
	return 0;
}

完结撒花 ！！！