题解 P4184【[USACO18JAN]Sprinklers P】

· · 题解

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;
}