题解 P4184 【[USACO18JAN]Sprinklers P】

· · 题解

模拟赛2h上肝出此题，故发题解纪念一下

首先，我们先根据样例画一幅图：

其中，粉色格子是肥料和水全喷到的地方。

我们发现，对于一行里面，粉色格子的左界是在这一行上面的所有蓝点中，最靠左的那一个，而右界是在这一行下面的所有蓝点中，最靠右的那一个。

如果这不太清楚的话，我们再提供一组样例及它对应的图：

11
0 5
1 4
2 8
3 3
4 2
5 1
6 10
7 6
8 0
9 9
10 7

是不是明白了？

我们接下来考虑如何对于一行求答案。设每一行的左界是dw_i，右界是up_i。

则我们将第i行当作矩形下界，枚举一个j\leq i当作矩形上界。则矩形左界是dw_j，右界是up_i。设L=dw_j,R=up_i，则以i为下界，j为上界的矩形的方案数为\dfrac{(R-L)(R-L+1)}{2}。

这样预处理出来up和dw后，枚举i和j，复杂度就是O(n^2)的。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,up[100100],dw[100100],res;
pair<int,int>p[100100];
int main(){
    scanf("%d",&n),dw[0]=0x3f3f3f3f;
    for(int i=1;i<=n;i++)scanf("%d%d",&p[i].first,&p[i].second);
    sort(p+1,p+n+1);
    for(int i=n-1;i;i--)up[i]=max(up[i+1],p[i+1].second);
    for(int i=1;i<n;i++)dw[i]=min(dw[i-1],p[i].second);
//  for(int i=1;i<n;i++)printf("%d %d\n",up[i],dw[i]);
    for(int i=1;i<n;i++)for(int j=i;j>=1&&dw[j]<up[i];j--)(res+=(1ll*(up[i]-dw[j])*(up[i]-dw[j]+1)/2)%mod)%=mod;
    printf("%lld\n",res);
    return 0;
}

然后，考虑优化。

当i增加的时候，最大的有L\leq R的j也是递增的。因为对于\dfrac{(R-L)(R-L+1)}{2}差分后，得到\dfrac{(R-L)(R-L+1)}{2}=\sum\limits_{i=0}^{R-L}i，因此我们可以通过差分地更新它。

具体地说，我们设两个值k和l，其中k=\sum\limits_{q=j}^{i}R_q-L_q，l=\sum\limits_{q=j}^{i}\dfrac{(R_q-L_q)(R_q-L_q+1)}{2}。

则，当R减小1时，有l减小k和k减小(i-j+1)。

因此就可以差分地在O(n)时间内完成。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,up[100100],dw[100100],res;
pair<int,int>p[100100];
int main(){
    scanf("%d",&n),dw[0]=up[0]=n;
    for(int i=1;i<=n;i++)scanf("%d%d",&p[i].first,&p[i].second);
    sort(p+1,p+n+1);
    for(int i=n-1;i;i--)up[i]=max(up[i+1],p[i+1].second);
    for(int i=1;i<n;i++)dw[i]=min(dw[i-1],p[i].second);
//  for(int i=1;i<n;i++)printf("U:%d D:%d\n",up[i],dw[i]);
    for(int i=1,j=1,k=0,l=0;i<n;i++){
        if(up[i-1]>=dw[i])(k+=up[i-1]-dw[i])%=mod,(l+=(1ll*(up[i-1]-dw[i])*(up[i-1]-dw[i]+1)/2)%mod)%=mod;
        for(int q=up[i-1];q>up[i];q--){
            while(dw[j]==q)j++;
            (l-=k)%=mod,(k-=(i-j+1))%=mod;
        }
//      printf("(%d,%d,%d,%d)\n",i,j,k,l);
        (res+=l)%=mod;
    }
    printf("%lld\n",res);
    return 0;
}