洛谷题面

不需 \(\operatorname{Discretization}\&\operatorname{BIT}\) 并且时间复杂度优秀的一篇题解！

本篇题解是对 这篇题解 的补充。

题目大意

网格图上有 \(N\) 头奶牛，第 \(i\) 头奶牛坐标为 \((x_i,y_i)\)。

现在用一个大小至少为 \(1\) 的矩形覆盖若干格子，问被覆盖的区域包含的奶牛集合有多少种情况，包含空集。（矩形恰好完整覆盖若干格子）

题目分析

我们没必要将边界放在空格上。

我们首先对所有坐标按照行从小到大排序。之后所有的牛都按照这个顺序来操作。

设 \(y[i]\) 表示第 \(i\) 头牛的列，\(l[j]\) 表示第 \(j\) 行的牛与当前第 \(i\) 行的牛之间,有多少头牛在第 \(j\) 行的牛的左边，\(r[j]\) 表示第 \(j\) 行的牛与当前第 \(i\) 行的牛之间,有多少头牛在当前第 \(i\) 行的牛的右边。

因为我们需要求出包含的奶牛集合有多少种情况 ，所以我们不妨讨论第 \(i\) 头奶牛作为下方边界，第 \(j\) 头奶牛作为上方边界。

这样子，我们就将题目简化了。接下来分情况讨论：

1. 第 \(j\) 头牛在第 \(i\) 头牛的左边时：

   • 当第 \(k\) 行的牛在第 \(i\) 行的牛在第 \(j\) 头牛之间且在第 \(j\) 头牛左边，即 \(i\lt k\lt j,y[k]\lt y[j]\) 时：

   \(k\) 一定可以作为当前框定的左边界，当前情况的方案数为 \((rnum+1)\times(l[j]+1)\)。

   \(rnum\) 表示第 \(i\) 行的牛与当前第 \(j\) 行的牛之间，有多少头牛在第 \(i\) 行的牛右边。加 \(1\) 是因为可以选择边界。

   • 当第 \(k\) 行的牛在第 \(i\) 行的牛在第 \(j\) 头牛之间且在第 \(i\) 头牛右边，即 \(i\lt k\lt j,y[k]\gt y[i]\) 时：

   \(k\) 一定可以作为当前框定的右边界，当前情况的方案数为 \((lnum+1)\times(r[j]+1)\)。

   \(lnum\) 表示第 \(i\) 行的牛与当前第 \(j\) 行的牛之间，有多少头牛在第 \(j\) 行的牛左边。加 \(1\) 是因为可以选择边界。

2. 第 \(j\) 头牛在第 \(i\) 头牛的右边时同理。

---

时间复杂度 \(\mathcal{O}(n^2)\)。

代码

#define int long long

const int ma=2505;

struct Node
{
	int x;
	
	int y;
};

Node node[ma];

int l[ma],r[ma];
//l[j]:排序后,第 j 行的牛与当前第 i 行的牛之间,有多少头牛在第 j 行的牛的左边
//r[j]:排序后,第 j 行的牛与当前第 i 行的牛之间,有多少头牛在当前第 i 行的牛的右边

int n;

inline bool cmp(Node x,Node y)
{
	if(x.x!=y.x)
	{
		return x.x<y.x;
	}
	
	return x.y<y.y;
}

#undef int

int main(void)
{
	#define int long long
	
	n=read();
	
	for(register int i=1;i<=n;i++)
	{
		node[i].x=read(),node[i].y=read();
	}
	
	sort(node+1,node+n+1,cmp);
	
	int ans=1;
	 
	for(register int i=1;i<=n;i++)
	{
		ans++;
		
		int lnum=0,rnum=0;
		
		for(register int j=i-1;j>=1;j--)
		{
			if(node[i].y>node[j].y)
			{
				ans+=(rnum+1)*(l[j]+1);
				
				lnum++,r[j]++; 
			}
			
			else
			{
				ans+=(lnum+1)*(r[j]+1);
				
				rnum++,l[j]++;
			}
		}
	}
	
	printf("%lld\n",ans);
	
	return 0;
}