【BZOJ5366】【Lydsy1805月赛】代码派对

Author Avatar
q234rty 5月 29, 2018

容斥+二维前缀和即可。

首先一个naive的想法是枚举一个点 (x,y) ，用二维前缀和预处理出有多少个矩形包含 (x,y) ，设有 k 个，那么给答案加上 \binom{k}{3} 。但是这样显然会算重。

注意到 3 个矩形的交要么是空，要么还是矩形，我们考虑只在交的左上角计数这 3 个矩形一次。也就是说，对于每个点 (x,y) ，我们要算有多少矩形三元组的交包含这个点，但是不包含 (x-1,y) 和 (x,y-1) 。

考虑容斥，可以发现这就等于包含 (x,y) 的矩形三元组的数量，减去同时包含 (x,y) 和 (x-1,y) 的矩形三元组的数量，减去同时包含 (x,y) 和 (x,y-1) 的矩形三元组的数量，再加上同时包含 (x,y) 和 (x-1,y) 和 (x,y-1) 的矩形三元组的数量。后面三个量的计算和第一个是类似的，只是要把矩形缩小一行和/或一列，直接二维前缀和即可。

时间复杂度 O(T(n+1000^2))

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=10000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
	#ifdef LOCAL
		freopen("5366.txt","r",stdin);
	#endif
	buf[fread(buf,1,MAXSIZE,stdin)]='\0';
	bufpos=0;
}
#if NEG
int readint(){
	bool isneg;
	int val=0;
	for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
	bufpos+=(isneg=buf[bufpos]=='-');
	for(;isdigit(buf[bufpos]);bufpos++)
		val=val*10+buf[bufpos]-'0';
	return isneg?-val:val;
}
#else
int readint(){
	int val=0;
	for(;!isdigit(buf[bufpos]);bufpos++);
	for(;isdigit(buf[bufpos]);bufpos++)
		val=val*10+buf[bufpos]-'0';
	return val;
}
#endif
char readchar(){
	for(;isspace(buf[bufpos]);bufpos++);
	return buf[bufpos++];
}
int readstr(char* s){
	int cur=0;
	for(;isspace(buf[bufpos]);bufpos++);
	for(;!isspace(buf[bufpos]);bufpos++)
		s[cur++]=buf[bufpos];
	s[cur]='\0';
	return cur;
}
ll c3(ll n){
	return n*(n-1)*(n-2);
}
struct qwq{
	int t[1002][1002];
	void init(){
		memset(t,0,sizeof(t));
	}
	void add(int x1,int y1,int x2,int y2,int v){
		if (x1>x2 || y1>y2)
			return;
		t[x1][y1]+=v;
		t[x1][y2+1]-=v;
		t[x2+1][y1]-=v;
		t[x2+1][y2+1]+=v;
	}
	void get(){
		for(int i=1;i<=1000;i++)
			for(int j=1;j<=1000;j++)
				t[i][j]+=t[i-1][j]+t[i][j-1]-t[i-1][j-1];
	}
	int * operator [](int x){
		return t[x];
	}
}a,b,c,d;
int main(){
	init();
	int T=readint();
	while(T--){
		int n=readint();
		a.init(),b.init(),c.init(),d.init();
		while(n--){
			int x1=readint(),y1=readint(),x2=readint(),y2=readint();
			a.add(x1,y1,x2,y2,1);
			b.add(x1+1,y1,x2,y2,1);
			c.add(x1,y1+1,x2,y2,1);
			d.add(x1+1,y1+1,x2,y2,1);
		}
		a.get(),b.get(),c.get(),d.get();
		ll ans=0;
		for(int i=1;i<=1000;i++)
			for(int j=1;j<=1000;j++)
				ans+=c3(a[i][j])-c3(b[i][j])-c3(c[i][j])+c3(d[i][j]);
		printf("%lld\n",ans/6);
	}
}

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2018/05/29/bzoj5366/

隐藏