P4184 [USACO18JAN]Sprinklers P解题报告

解题报告

---

P4184 [USACO18JAN]Sprinklers P解题报告：

更好的阅读体验

题意

有一个$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;
}