题解：P9100 [PA 2020] Miny

sqzyz · 2026-08-09 10:19:50 · 题解

思路

考虑 dp，我们对于 dp 状态的设计要满足无后效性。

本题中如果设计 f_i 表示 i 引爆的方案并从 j 转移，那么 j 之前的元素也可能影响 f_i，有后效性。

因此我们考虑重新设计状态避免后效性，可以设计 f_i 表示 i 不引爆的方案，这样从 j 转移时，既然 j 不会被前面的元素引爆，那么 j 后面的元素也不会被前面的元素引爆，完美避免了后效性。

定义 l_i,r_i 分别表示 i 左右第一个能引爆 i 的位置，可以得到转移方程 f_i=\sum_{j=0}^{i-1}f_j\times [r_j\ge i]-\sum_{j=0}^{l_i-1}f_j\times [r_j\ge i]，需要用树状数组维护来优化时间复杂度，难点在于 l_i 没有单调性，如果直接按照顺序转移的话时间轴不对应。

注意到每一个转移相当于树状数组上的一次查询，我们把这些查询离线下来按照时间顺序依次处理即可。

注意特殊处理特殊的位置（从 j=0 转移的情况）。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10;
const int mod=1e9+7;
int n;
int a[N],D[N];
int pl[N],pr[N];
int l[N],r[N];
int stk[N],top=0;
vector<int>qry1[N],qry2[N];
int t[N];
int lowbit(int x){
    return x&(-x); 
} 
void add(int x,int k){
    while(x<=n+1){
        t[x]=(t[x]+k)%mod;
        x+=lowbit(x);
    }
}
int query(int x){
    int res=0;
    while(x>0){
        res=(res+t[x])%mod;
        x-=lowbit(x);
    }
    return res;
}
int f[N];
signed main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i]>>D[i];
    }
    r[0]=r[n+1]=n+1;
    l[0]=l[n+1]=0;
    a[0]=-2000000000000000001,a[n+1]=2000000000000000001,D[0]=D[n+1]=4000000000000000005;
    for(int i=0;i<=n+1;i++){
        pl[i]=a[i]-D[i];
        pr[i]=a[i]+D[i];
    } 
    for(int i=0;i<=n+1;++i){
        int L=1,R=top;
        l[i]=0; 
        while(L<=R){
            int mid=(L+R)>>1;
            if(pr[stk[mid]]>=a[i]){
                l[i]=stk[mid];
                L=mid+1;
            }
            else R=mid-1;
        }
        while(top>0&&pr[stk[top]]<pr[i])top--;
        stk[++top]=i;
    }
    top=0;
    for(int i=n+1;i>=0;--i){
        int L=1,R=top;
        r[i]=n+1;
        while(L<=R){
            int mid=(L+R)>>1;
            if(pl[stk[mid]]<=a[i]){
                r[i]=stk[mid];
                L=mid+1;
            }
            else R=mid-1;
        }
        while(top>0&&pl[stk[top]]>pl[i])top--;
        stk[++top]=i;
    }
    for(int i=1;i<=n+1;i++){
        if(!l[i])++f[i];
        if(i>1)qry1[i-1].push_back(i);
        if(l[i]>1)qry2[l[i]-1].push_back(i);
    }
    for(int i=0;i<=n;i++){
        add(r[i],f[i]);
        for(auto x:qry1[i]){
            f[x]=((f[x]+query(n+1))%mod-query(x-1)+mod)%mod; 
        }
        for(auto x:qry2[i]){
            f[x]=((f[x]+query(x-1))%mod-query(n+1)+mod)%mod;
        }
    }
    cout<<f[n+1];
    return 0;
}