【2023NOI模拟赛18】送分题 做题记录

给定 $n$ 个矩形 $(lx_i,rx_i,ly_i,ry_i)$，求选出三个互不相交的矩形的方案数。

$1\le n\le 10^5$，$1\le lx_i<rx_i\le 2n$，$1\le ly_i<ry_i\le 2n$，所有 $lx_i$、$rx_i$ 构成 $2n$ 的排列，所有 $ly_i$、$ry_i$ 构成 $2n$ 的排列。

考虑容斥，答案即为乱选的方案数，先减去钦定两个矩形有交的方案数，再加上钦定某个矩形和两个矩形有交的方案数，最后减掉三个矩形两两都有交的方案数。第一个显然就是 $\binom{n}{3}$，第二个和第三个可以通过算出和第 $i$ 个矩形相交的矩形个数 $sum_i$ 来解决，先来考虑第四个。

考虑计算选择三个两两有交的矩形的方案数，有如下式子：

$\sum\limits_{\text{选 }3\text{ 个不同的矩形 }A,B,C}[|A\cap B\cap C|\not= 0]$

观察到 $A\cap B\cap C$ 一定是一个矩形，本质上是数 $A\cap B\cap C$ 有多少个简单连通块（内部没有洞）。那么考虑网格图上一种特殊的可以把数简单连通块个数转换为数面积的容斥：简单连通块个数等于 $1\times 1$ 的小联通块的个数，减去 $1\times 2$ 的小连通块的个数，减去 $2\times 1$ 的小连通块的个数，最后再加上 $2\times 2$ 的小连通块的个数。

这个容斥本质上其实相当于把连通块往下、往右缩，类似于点边容斥，最后每个凹进去的下右拐角会有 $-1$ 的贡献，突出来的左上拐角会有 $1$ 的贡献：

那么式子就变成了：

调换求和顺序：

显然可以四遍扫描线求解，维护组合数可以利用范德蒙德卷积和标记永久化。

然后考虑求解 $sum_i$，仍套用以上容斥，扫描线用区间加区间查树状数组维护历史和即可，不用线段树是因为卡常。

代码如下：

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

const int S=100005;

struct node
{
	int lx,rx,ly,ry;
};

struct prr
{
	int lx,rx;
	long long k,b;
};

int n,on_my_love_ruiruiruiruirui__don_t__STAY______on_my_love_ruiruiruiruirui_non_t__STAY_____;
node a[S];
vector<prr> vec[S*2],que[S*2];
int sum[S];
long long ans;

namespace tr1
{
	struct node
	{
		long long k,b;
		inline node(){k=b=0;}
		inline node(long long x,long long y){k=x,b=y;}
		inline node operator+(node bb){return (node){k+bb.k,b+bb.b};}
		inline node operator*(int y){return (node){k*y,b*y};}
		inline node operator-(){return (node){-k,-b};}
		inline node operator-(node bb){return (node){k-bb.k,b-bb.b};}
	}tr1[S*2],tr2[S*2];
	inline void clear(){memset(tr1,0,sizeof(tr1));memset(tr2,0,sizeof(tr2));}
	inline void addt(int p,node x){for(int i=p;i<=n*2;i+=i&-i) tr1[i]=tr1[i]+x,tr2[i]=tr2[i]+x*p;}
	inline node quet(int p)
	{
		node re1,re2;
		for(int i=p;i>=1;i-=i&-i) re1=re1+tr1[i],re2=re2+tr2[i];
		return re1*(p+1)-re2;
	}
	void add(int l,int r,long long k,long long b)
	{
		node val(k,b);
		addt(l,val),addt(r+1,-val);
	}
	long long que(int l,int r,int tme)
	{
		node res=quet(r)-quet(l-1);
		return res.k*tme+res.b;
	}
}

namespace tr2
{
	long long val[4][S<<3];
	int tag[S<<3];
	void clear(int u,int l,int r)
	{
		val[0][u]=r-l+1,val[1][u]=val[2][u]=val[3][u]=0;
		tag[u]=0;
		if(l==r) return;
		int mid=l+r>>1;
		clear(u<<1,l,mid),clear(u<<1|1,mid+1,r);
	}
	inline void upd(int u,int l,int r)
	{
		if(l!=r)
		{
			int ls=u<<1,rs=u<<1|1;
			val[0][u]=val[0][ls]+val[0][rs];
			val[1][u]=val[1][ls]+val[1][rs];
			val[2][u]=val[2][ls]+val[2][rs];
			val[3][u]=val[3][ls]+val[3][rs];
		}
		else val[0][u]=1,val[1][u]=val[2][u]=val[3][u]=0;
		long long t0=val[0][u],t1=val[1][u],t2=val[2][u],t3=val[3][u];
		long long w0=1,w1=tag[u],w2=1ll*tag[u]*(tag[u]-1)/2,w3=1ll*tag[u]*(tag[u]-1)*(tag[u]-2)/6;
		val[0][u]=t0*w0;
		val[1][u]=t0*w1+t1*w0;
		val[2][u]=t0*w2+t1*w1+t2*w0;
		val[3][u]=t0*w3+t1*w2+t2*w1+t3*w0;
	}
	void add(int u,int l,int r,int L,int R,int val)
	{
		if(l>R||r<L) return;
		if(l>=L&&r<=R) return tag[u]+=val,upd(u,l,r),void();
		int mid=l+r>>1;
		if(L<=mid) add(u<<1,l,mid,L,R,val);
		if(R>=mid+1) add(u<<1|1,mid+1,r,L,R,val);
		upd(u,l,r);
	}
}

inline void calcsum(int bse)
{
	for(int i=1;i<=n*2;i++) vec[i].clear(),que[i].clear();
	tr1::clear();
	for(int i=1;i<=n;i++)
	{
		vec[a[i].ly].push_back((prr){a[i].lx,a[i].rx,1,-(a[i].ly-1)});
		if(a[i].ry<n*2) vec[a[i].ry+1].push_back((prr){a[i].lx,a[i].rx,-1,a[i].ry});
		if(a[i].ly>1) que[a[i].ly-1].push_back((prr){a[i].lx,a[i].rx,i,-1});
		que[a[i].ry].push_back((prr){a[i].lx,a[i].rx,i,1});
	}
	for(int i=1;i<=n*2;i++)
	{
		for(prr &u:vec[i]) tr1::add(u.lx,u.rx,u.k,u.b);
		for(prr &u:que[i]) sum[u.k]+=bse*u.b*tr1::que(u.lx,u.rx,i);
	}
} 

inline void calcans(int bse)
{
	for(int i=1;i<=n*2;i++) vec[i].clear();
	tr2::clear(1,1,n*2);
	for(int i=1;i<=n;i++)
	{
		vec[a[i].ly].push_back((prr){a[i].lx,a[i].rx,1,0});
		if(a[i].ry<n*2) vec[a[i].ry+1].push_back((prr){a[i].lx,a[i].rx,-1,0});
	}
	for(int i=1;i<=n*2;i++)
	{
		for(prr &u:vec[i]) tr2::add(1,1,n*2,u.lx,u.rx,u.k);
		ans+=bse*tr2::val[3][1];
	}
}

int main()
{
	freopen("gift.in","r",stdin);
	freopen("gift.out","w",stdout);
	scanf("%d%d",&n,&on_my_love_ruiruiruiruirui__don_t__STAY______on_my_love_ruiruiruiruirui_non_t__STAY_____);
	for(int i=1;i<=n;i++) scanf("%d%d%d%d",&a[i].lx,&a[i].rx,&a[i].ly,&a[i].ry);
	calcsum(1);
	calcans(1);
	for(int i=1;i<=n;i++) a[i].rx--;
	calcsum(-1);
	calcans(-1);
	for(int i=1;i<=n;i++) a[i].rx++;
	for(int i=1;i<=n;i++) a[i].ry--;
	calcsum(-1);
	calcans(-1);
	for(int i=1;i<=n;i++) a[i].ry++;
	for(int i=1;i<=n;i++) a[i].rx--,a[i].ry--;
	calcsum(1);
	calcans(1);
	for(int i=1;i<=n;i++) a[i].rx++,a[i].ry++;
	for(int i=1;i<=n;i++) sum[i]--;
	long long res1=1ll*n*(n-1)*(n-2)/6;
	long long res2=0,res3=0;
	for(int i=1;i<=n;i++)
	{
		res2+=1ll*sum[i]*(n-2);
		res3+=1ll*sum[i]*(sum[i]-1)/2;
	}
	res2/=2;
	printf("%lld\n",res1-res2+res3-ans);
	return 0;
}