自动搬运

查看原文

来自洛谷，原作者为

	whiteqwq 寻找着梦与现实的交点 在哪呢 在哪呢

搬运于2025-08-24 21:57:26，当前版本为作者最后更新于2021-03-28 18:43:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

P4184 [USACO18JAN]Sprinklers P解题报告：

更好的阅读体验

第$600$道紫题，庆祝一下。

题意

有一个$n\times n$的矩阵，有$n$个关键点落在格点上（保证每行与每列有且仅有一个），求有多少个非空子矩阵满足左上方有一个关键点，右下方也有一个关键点（两个关键点均可以落在矩阵的边缘）。（$1\leqslant n\leqslant 10^5$）

分析

题解里差分写法看不懂，来一发比较套路的dp优化吧。

首先不难发现能选用的格点会形成一个类似这样的图形：

.xxx.
.xxx.
.xxx.
xxxx.
xxxx.

每一行能选用的格点是连续的，且左端点，右端点随着行数的增加而不断左移。

那么就很容易预处理：$l_i$（代表第$i$行区间的左端点的列号），$r_i$（代表第$i$行区间的右端点的列号），$up_i$（表示第$i$列能选用的最上方格点的行号）

然后就可以列出式子（$(i,j)$为矩阵的右下角，$(p,k)$为矩阵的左上角）：

$$\sum_{i=1}^n\sum_{j=l_i}^{r_i}\sum_{k=l_i}^{j-1}\sum_{p=up_k}^{i-1}1 $$

那么剩下的工作就很显然了，这个式子可以优化到$O(n)$，有经验的选手可以跳过下面的部分。

$$\sum_{i=1}^n\sum_{j=l_i}^{r_i}\sum_{k=l_i}^{j-1}\sum_{p=up_k}^{i-1}1=\sum_{i=1}^n\sum_{j=l_i}^{r_i}\sum_{k=l_i}^{j-1}i-up_k=\sum_{i=1}^n(\sum_{j=l_i}^{r_i}(j-l_i\times i)-\sum_{k=l_i}^{r_i-1}\sum_{j=k+1}^{r_i}up_k)\\=\sum_{i=1}^n(\frac{(r_i-l_i+1)(r_i-l_i)}{2}\times i-\sum_{k=l_i}^{r_i-1}(r_i-k)\times up_k) $$

设$sum1_x=\sum_{i=1}^x up_i,sum2_x=\sum_{i=1}^x i\times up_i$，那么就可以继续化：

$$\sum_{i=1}^n\sum_{j=l_i}^{r_i}\sum_{k=l_i}^{j-1}\sum_{p=up_k}^{i-1}1=\sum_{i=1}^n(\frac{(r_i-l_i+1)(r_i-l_i)}{2}\times i-r_i\times(sum1_{r_i-1}-sum1_{l_i-1})+(sum2_{r_i-1}-sum2_{l_i-1})) $$

利用关键点的坐标为$[0,n-1]$的整数，很容易做到$O(n)$。

代码

注意题目中关键点的坐标是从$0$开始的。

#include<stdio.h>
const int maxn=100005,mod=1000000007;
int n,pos,ans;
int l[maxn],r[maxn],up[maxn],y[maxn],sum1[maxn],sum2[maxn];
inline int min(int a,int b){
	return a<b? a:b;
}
inline int max(int a,int b){
	return a>b? a:b;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		a++,b++,y[a]=b;
	}
	l[0]=n;
	for(int i=1;i<=n;i++)
		l[i]=min(l[i-1],y[i]);
	r[n+1]=0;
	for(int i=n;i>=1;i--)
		r[i]=max(r[i+1],y[i]);
	pos=r[1];
	for(int i=1;i<=n;i++)
		while(pos>=1&&pos>=l[i])
			up[pos]=i,pos--;
	for(int i=1;i<=n;i++)
		sum1[i]=(sum1[i-1]+up[i])%mod;
	for(int i=1;i<=n;i++)
		sum2[i]=(sum2[i-1]+1ll*i*up[i]%mod)%mod;
	for(int i=1;i<=n;i++)
		ans=(ans+1ll*i*(1ll*(r[i]-l[i])*(r[i]-l[i]+1)/2ll%mod)%mod-1ll*(sum1[r[i]-1]-sum1[l[i]-1]+mod)%mod*r[i]%mod+(sum2[r[i]-1]-sum2[l[i]-1]+mod)%mod)%mod;
	printf("%d\n",(ans+mod)%mod);
	return 0;
}