【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

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MAXSIZE=10000020;
  5. int bufpos;
  6. char buf[MAXSIZE];
  7. #define NEG 0
  8. void init(){
  9. 	#ifdef LOCAL
  10. 		freopen("5366.txt","r",stdin);
  11. 	#endif
  12. 	buf[fread(buf,1,MAXSIZE,stdin)]='\0';
  13. 	bufpos=0;
  14. }
  15. #if NEG
  16. int readint(){
  17. 	bool isneg;
  18. 	int val=0;
  19. 	for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
  20. 	bufpos+=(isneg=buf[bufpos]=='-');
  21. 	for(;isdigit(buf[bufpos]);bufpos++)
  22. 		val=val*10+buf[bufpos]-'0';
  23. 	return isneg?-val:val;
  24. }
  25. #else
  26. int readint(){
  27. 	int val=0;
  28. 	for(;!isdigit(buf[bufpos]);bufpos++);
  29. 	for(;isdigit(buf[bufpos]);bufpos++)
  30. 		val=val*10+buf[bufpos]-'0';
  31. 	return val;
  32. }
  33. #endif
  34. char readchar(){
  35. 	for(;isspace(buf[bufpos]);bufpos++);
  36. 	return buf[bufpos++];
  37. }
  38. int readstr(char* s){
  39. 	int cur=0;
  40. 	for(;isspace(buf[bufpos]);bufpos++);
  41. 	for(;!isspace(buf[bufpos]);bufpos++)
  42. 		s[cur++]=buf[bufpos];
  43. 	s[cur]='\0';
  44. 	return cur;
  45. }
  46. ll c3(ll n){
  47. 	return n*(n-1)*(n-2);
  48. }
  49. struct qwq{
  50. 	int t[1002][1002];
  51. 	void init(){
  52. 		memset(t,0,sizeof(t));
  53. 	}
  54. 	void add(int x1,int y1,int x2,int y2,int v){
  55. 		if (x1>x2 || y1>y2)
  56. 			return;
  57. 		t[x1][y1]+=v;
  58. 		t[x1][y2+1]-=v;
  59. 		t[x2+1][y1]-=v;
  60. 		t[x2+1][y2+1]+=v;
  61. 	}
  62. 	void get(){
  63. 		for(int i=1;i<=1000;i++)
  64. 			for(int j=1;j<=1000;j++)
  65. 				t[i][j]+=t[i-1][j]+t[i][j-1]-t[i-1][j-1];
  66. 	}
  67. 	int * operator [](int x){
  68. 		return t[x];
  69. 	}
  70. }a,b,c,d;
  71. int main(){
  72. 	init();
  73. 	int T=readint();
  74. 	while(T--){
  75. 		int n=readint();
  76. 		a.init(),b.init(),c.init(),d.init();
  77. 		while(n--){
  78. 			int x1=readint(),y1=readint(),x2=readint(),y2=readint();
  79. 			a.add(x1,y1,x2,y2,1);
  80. 			b.add(x1+1,y1,x2,y2,1);
  81. 			c.add(x1,y1+1,x2,y2,1);
  82. 			d.add(x1+1,y1+1,x2,y2,1);
  83. 		}
  84. 		a.get(),b.get(),c.get(),d.get();
  85. 		ll ans=0;
  86. 		for(int i=1;i<=1000;i++)
  87. 			for(int j=1;j<=1000;j++)
  88. 				ans+=c3(a[i][j])-c3(b[i][j])-c3(c[i][j])+c3(d[i][j]);
  89. 		printf("%lld\n",ans/6);
  90. 	}
  91. }

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

隐藏