P15129 题解

DHeasy · 2026-03-06 14:34:25 · 题解

首先如果一个矩形被另一个矩形包含，则可以删去它，不会对答案产生影响，然后将剩下的矩形按 r_i 降序排序。

发现这些矩形的边将整个盘面分成了若干个小矩形，将这些子矩阵缩成一个格子，权值即为原来的格子数量，如图所示：

缩完之后依次考虑每一列，设 f_i 表示钦定第 i 有选择的方案数。枚举上一次选择的是哪一列，那么在这一列对应的那个矩阵下边都是可以选择的，即：

直接做是 \mathcal O(n^2) 的，可以获得 65 分。

::::info[65 分代码]

#include<bits/stdc++.h>
#define ll long long
#define re register
#define fi first
#define se second
#define LL __int128
#define ull unsigned ll
using namespace std;
inline ll read(){
    ll res=0ll,f=1;
    char c;
    for(;(c=getchar())<'0'||c>'9';c=='-'?f=-f:0);
    while(c>='0' && c<='9') res=(res<<1) + (res<<3) + c-'0',c=getchar();
    return res*f;
}
inline ll Max(re ll x,re ll y){return x>y?x:y;}
inline ll Min(re ll x,re ll y){return x<y?x:y;}
inline void cmax(re auto &x,re auto y){x=Max(x,y);}
inline void cmin(re auto &x,re auto y){x=Min(x,y);}
const int mod=1000000007;
inline int add(re int x,re int y){return (x+y)%mod;}
inline int mul(re int x,re int y){return (ll)x*y%mod;}
inline void Add(re auto &x,re auto y){x=add(x,y);}
inline void Mul(re auto &x,re auto y){x=mul(x,y);}
inline int qpow(re int x,re ll y){
    if(y==0) return 1;
    int sum=1,now=x;
    while(y){
        if(y&1) Mul(sum,now);
        Mul(now,now),y>>=1;
    }
    return sum;
}
/*-----------------*/
const int N=2e5+10;
int n,m,t,dp[N],ans; ll sum;
struct P{int x,y;}p[N];
int main(){
    n=read();m=read();
    for(re int i=1;i<=n;i++)
        p[i].x=read(),p[i].y=read();
    sort(p+1,p+n+1,[](re P X,re P Y){
        if(X.x==Y.x) return X.y>Y.y;
        return X.x>Y.x;
    });
    for(re int i=1,h=0;i<=n;i++){
        if(h>=p[i].y) continue;
        p[++t]=p[i]; cmax(h,p[i].y);
    }

    n=t,dp[0]=1; p[0].x=m,p[n+1].x=0;
    for(re int i=1;i<=n;i++)
    for(re int j=i-1;~j;j--){
        int A=p[i].x-p[i+1].x,B=p[i].y-p[j].y;
        Add(dp[i],mul(dp[j],mul(A,B)));
    }
    for(re int i=0;i<=n;i++) Add(ans,dp[i]);
    for(re int i=0;i<=n;i++)
        sum+=(ll)(p[i].x-p[i+1].x)*(m-p[i].y);
    return !printf("%d\n",mul(ans,qpow(2,sum)));
}

::::

考虑优化，注意到 r_i-r_{i+1} 只和 i 有关，可以提出来。剩下的部分可以拆成 c_if_j-c_jf_j，设 a_n=\displaystyle\sum_{i=1}^{n}f_i,b_n=\displaystyle\sum_{i=1}^{n}c_if_i，将转移方程改写为：

dp 部分时空复杂度为 \mathcal O(n)。

然后还要考虑没有被覆盖的位置，算出他们的数量 c，将答案乘上 2^c。

时间复杂度为 \mathcal O(n\log m)，瓶颈在快速幂。

#include<bits/stdc++.h>
#define ll long long
#define re register
#define fi first
#define se second
#define LL __int128
#define ull unsigned ll
using namespace std;
inline ll read(){
    ll res=0ll,f=1;
    char c;
    for(;(c=getchar())<'0'||c>'9';c=='-'?f=-f:0);
    while(c>='0' && c<='9') res=(res<<1) + (res<<3) + c-'0',c=getchar();
    return res*f;
}
inline ll Max(re ll x,re ll y){return x>y?x:y;}
inline ll Min(re ll x,re ll y){return x<y?x:y;}
inline void cmax(re auto &x,re auto y){x=Max(x,y);}
inline void cmin(re auto &x,re auto y){x=Min(x,y);}
const int mod=1000000007;
inline int add(re int x,re int y){return (x+y)%mod;}
inline int mul(re int x,re int y){return (ll)x*y%mod;}
inline void Add(re auto &x,re auto y){x=add(x,y);}
inline void Mul(re auto &x,re auto y){x=mul(x,y);}
inline int qpow(re int x,re ll y){
    if(y==0) return 1;
    int sum=1,now=x;
    while(y){
        if(y&1) Mul(sum,now);
        Mul(now,now),y>>=1;
    }
    return sum;
}
/*-----------------*/
const int N=2e5+10;
int n,m,t,dp[N],ans; ll sum;
struct P{int x,y;}p[N];
int main(){
    n=read();m=read();
    for(re int i=1;i<=n;i++)
        p[i].x=read(),p[i].y=read();
    sort(p+1,p+n+1,[](re P X,re P Y){
        if(X.x==Y.x) return X.y>Y.y;
        return X.x>Y.x;
    });
    for(re int i=1,h=0;i<=n;i++){
        if(h>=p[i].y) continue;
        p[++t]=p[i]; cmax(h,p[i].y);
    }

    n=t,dp[0]=1; p[0].x=m,p[n+1].x=0;
    for(re int i=1,sx=1,sy=0;i<=n;i++){
        int A=p[i].x-p[i+1].x,B=mul(p[i].y,sx);
        dp[i]=mul(A,add(B,mod-sy));
        Add(sx,dp[i]),Add(sy,mul(dp[i],p[i].y));
    }
    for(re int i=0;i<=n;i++) Add(ans,dp[i]);
    for(re int i=0;i<=n;i++)
        sum+=(ll)(p[i].x-p[i+1].x)*(m-p[i].y);
    return !printf("%d\n",mul(ans,qpow(2,sum)));
}