自动搬运

查看原文

来自洛谷，原作者为

	chala_tea -L'appel du Vide-

搬运于2025-08-24 22:51:19，当前版本为作者最后更新于2023-10-16 19:39:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

→更好的阅读体验

题目大意

题目链接：P9737 Lampice

给定一个坐标系（仅使用 $(0,0)$ 至 $(n,m)$ 的部分），输入 $k$ 个整数点对 $(x_1,y_1),(x_2,y_2)$。

要求在坐标轴上找到矩形（顶点坐标均为自然数），使每个点对的两个点均在矩形内或均在矩形外，最终输出满足条件的矩形个数。

题解

下面将讨论各个 subtask 中的可行解法（subtask 颜色表示个人认为的难度）：

$\text{\textcolor{#7de749}{Subtask 1 (28 pts)}}$

特殊条件：

对于每种颜色的灯，$x_1=y_1=0$。

解法：

我们发现，如果我们将 $(0,0)$ 加入矩形，则必须将所有点全部加入矩形内。由此可以进行分类讨论：

①将 $(0,0)$ 加入矩形：为将所有点全部加入矩形内，通过打擂获取最大的 $x,y$ 值 $\max(x_2),\max(y_2)$。

则 $x$ 共有 $(n+1-\max(x_2))$ 种可能，$y$ 共有 $(m+1-\max(y_2))$ 种可能。

易得，该种情况下共有 $(n+1-\max(x_2))\cdot(m+1-\max(y_2))$ 个矩形。

②不将 $(0,0)$ 加入矩形：那么它不能包含任何其他点，因此我们的目标是找到没有任何点的矩形个数。

先遍历矩形的下行 $j$ ，那么对于每一列，我们可以计算并存下该列的最大高度（也就是从第 $j$ 行开始，在不碰到点的情况下向上可以走多远）。

再遍历列 $i$ ，可以通过找到比第 $i$ 高度小的最左/最右行 来计算矩形数量 这里就不多赘述了。

→时间复杂度最终为 $O(nm^2 + k)$ （懒得写程序了（）。

$\text{\textcolor{#fe4f64}{Subtask 2 (12 pts)}}$

特殊条件：

$n,m≤10,k≤1000$。

解法：

直接暴力扫每一种可能的矩形并判断是否合法。

→时间复杂度最终为 $O(k(nm)^2)$。

$\text{\textcolor{#a64ed3}{Subtask 3 (36+12 pts)}}$

特殊条件：

$m≤150$。

解法：

此时我们可以借助随机化。

→什么是uniform_int_distribution （省流：均匀分布的随机数）。

给每一个颜色赋予一个唯一的值（设这个值在 $0 \sim 2 ^ {60} - 1$ 之间），那么当我们判断矩形的合法性时，则可以将矩形内所有点所对应的值全部进行异或操作。

那么显然，当矩形合法时，内部的 xor 结果应为零，不合法则不为零。

那么此时我们可以列举每个矩形，并用该种方法检查合法性。

我们可以进行“前缀 xor 和”的预处理以更快的计算每个矩形的 xor 和。

→时间复杂度最终为 $O((nm)^2+k)$。

$\text{\textcolor{#a64ed3}{Subtask 4 (110 pts)}}$

特殊条件：

无特殊条件。

解法：

进一步优化 sub#3 的算法：

遍历矩形左端的列 $l$ 和右端的列 $r$，再使用数组 $v[i]$ 储存第 $i$ 行中第 $l$ 列到第 $r$ 列所有值的 xor 和。

此时问题就转化为了：找到 xor 和 = 0 且 长度至少为 2 的 $v[]$ 的子数组的数量。

tips：“长度至少为 2”这一条件可以后期处理（删去长度为 1 的情况数）。

→时间复杂度最终为 $O(n^2 \cdot m \log m)$。

代码实现

//solution of P9737 [COCI2022-2023#2] Lampice

#include <bits/stdc++.h>
using namespace std;

#define MAXN 3010
#define int long long

mt19937 rng(random_device{}());

int m,n,k;
int a[MAXN][MAXN];

int solve(vector<int> v){
	sort(v.begin(),v.end());
	int cnt=1,ans=0;
	for(int i=1;i<(int)v.size();++i){
		if (v[i]!=v[i-1]) cnt=0;
		ans+=cnt;
		++cnt;
	}
	return ans;
}

signed main(){
	//解绑快读 
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	//生成均匀分布的随机数 （见sub#3题解） 
	uniform_int_distribution<int> dis(0,(1ll<<60)-1);
	
	cin>>n>>m>>k;
	++n,++m;//这里将所有坐标+1易于后期操作 
	
	for(int i=1;i<=k;i++){
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		++x1,++y1,++x2,++y2;//同理
		int u=dis(rng);
		a[x1][y1]^=u;//给点赋予随机值 
		a[x2][y2]^=u;
	}
	
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			a[i+1][j+1]^=a[i][j]^a[i+1][j]^a[i][j+1];//预处理 
			
	int ans=0;
	for(int l=0;l<n;l++)
		for(int r=l+2;r<=n;r++){//遍历矩形左右坐标 
			vector<int> v(m+1);
			for(int i=0;i<=m;i++){
				v[i]=a[l][i]^a[r][i];
			}
			ans+=solve(v);
			for(int i=0;i<m;i++){//删去长度为1的子数组 （不要忘记了哦！！！） 
				ans-=(v[i]^v[i+1])==0;
			}
		}
	
	cout<<ans<<endl;
	
	return 0;
}