P9100 [PA 2020] Miny Solution

Ptll · 2026-05-18 15:10:23 · 题解

竞选全谷最慢解法。

题解

定义 f_i 表示不选 i 的时候的方案数，找到一个 < i 中最大的 j 使得 j 能引爆 i。

这个引起的性质就是引爆 j 到 i 之间的任意一个，都不会波及到这两个点。

对于 f_i 的转移是显然的：

答案就是 f_{n+1}。

我们可以用线段树加倍增来处理出每个点所能爆炸的的最大以及最小的点的编号。

然后考虑二分加区间查询处理出对于每个点 i 满足条件的位置的值。

最后用树状数组维护完成答案统计即可。

时间复杂度：O(n \log ^2 n)。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <stack>
#ifdef _WIN32
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#else
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef __int128 i128;
namespace io {
    using namespace std;
    template <typename T> void debug (T x) {
        cerr<<x<<'\n';
    }
    template <typename T> void debuglen (T x) {
        cerr<<x<<' ';
    }
    template <typename T,typename...Args> void debug (T x,Args...args) {
        cerr<<x<<' ';
        debug(args...);
    }
    template <typename T> void debug (T*lt,T*rt) {
        ll len=rt-lt;
        for (ll i=0;i<len;i++) {
            debuglen(*(lt+i));
        }
        cerr<<'\n';
    }
    inline ll read () {
        char x=getchar();
        ll ans=0,f=1;
        while (x<'0'||x>'9') {
            if (x=='-') {
                f=-1;
            }
            x=getchar();
        }
        while (x>='0'&&x<='9') {
            ans=(ans<<1)+(ans<<3);
            ans+=(x^'0');
            x=getchar();
        }
        return ans*f;
    }
    void print (ll x) {
        if (x<0) {
            x=-x;
            putchar('-');
        }
        if (x>=10) {
            print(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace io;
const ll N=3e5+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
struct node {
    ll l,r;
} num[N];
ll n,a[N],rl[N],f[N],L[N],R[N];
vector<ll> v[N];
struct Segtree {
    ll mn[N<<2],mx[N<<2];
    inline void push_up (ll pos) {
        mn[pos]=min(mn[pos<<1],mn[pos<<1|1]);
        mx[pos]=max(mx[pos<<1],mx[pos<<1|1]);
    }
    void build (ll pos,ll l,ll r) {
        if (l==r) {
            mn[pos]=num[l].l;
            mx[pos]=num[l].r;
            return ;
        }
        ll mid=(l+r)>>1;
        build(pos<<1,l,mid);
        build(pos<<1|1,mid+1,r);
        push_up(pos);
    }
    pll query (ll pos,ll l,ll r,ll L,ll R) {
        if (L<=l&&r<=R) {
            return {mn[pos],mx[pos]};
        }
        ll mid=(l+r)>>1,mnl=inf,mxl=-inf;
        if (L<=mid) {
            pll d=query(pos<<1,l,mid,L,R);
            mnl=d.first,mxl=d.second;
        }
        if (R>mid) {
            pll d=query(pos<<1|1,mid+1,r,L,R);
            mnl=min(mnl,d.first),mxl=max(mxl,d.second);
        }
        return {mnl,mxl};
    }
} tr;
struct BIT {
    ll t[N];
    #define lowbit(x) (x&(-x))
    inline void add (ll x,ll val) {
        while (x<=n+1) {
            t[x]=(t[x]+val+mod)%mod;
            x+=lowbit(x);
        }
    }
    inline ll query (ll x) {
        ll cnt=0;
        while (x) {
            cnt=(cnt+t[x])%mod;
            x-=lowbit(x);
        }
        return cnt;
    }
} trl;
inline void solve () {
    n=read();
    for (ll i=1;i<=n;i++) {
        a[i]=read(),rl[i]=read();
    }
    for (ll i=1;i<=n;i++) {
        ll l=1,r=i,cnt=i;
        while (l<=r) {
            ll mid=(l+r)>>1;
            if (a[i]-a[mid]<=rl[i]) {
                cnt=mid;
                r=mid-1;
            }
            else {
                l=mid+1;
            }
        }
        num[i].l=cnt;
        l=i,r=n,cnt=i;
        while (l<=r) {
            ll mid=(l+r)>>1;
            if (a[mid]-a[i]<=rl[i]) {
                cnt=mid;
                l=mid+1;
            }
            else {
                r=mid-1;
            }
        }
        num[i].r=cnt;
    }
    for (ll j=1;j<=20;j++) {
        tr.build(1,1,n);
        for (ll i=1;i<=n;i++) {
            pll d=tr.query(1,1,n,num[i].l,num[i].r);
            num[i].l=d.first,num[i].r=d.second;
        }
    }
    num[0]=num[n+1]={0,n+1};
    tr.build(1,0,n+1);
    for (ll i=1;i<=n;i++) {
        ll l=0,r=i-1;
        while (l<=r) {
            ll mid=(l+r)>>1;
            if (tr.query(1,0,n+1,mid,i-1).second>=i) {
                L[i]=mid;
                l=mid+1;
            }
            else {
                r=mid-1;
            }
        }
        l=i+1,r=n+1;
        while (l<=r) {
            ll mid=(l+r)>>1;
            if (tr.query(1,0,n+1,i+1,mid).first<=i) {
                R[i]=mid;
                r=mid-1;
            }
            else {
                l=mid+1;
            }
        }
    }
    for (ll i=1;i<=n;i++) {
        v[R[i]].push_back(i);
    }
    trl.add(1,1);
    for (ll i=1;i<=n+1;i++) {
        f[i]=(trl.query(i)-trl.query(L[i])+mod)%mod;
        for (auto it : v[i]) {
            trl.add(it+1,-f[it]);
        }
        trl.add(i+1,f[i]);
    }
    print(f[n+1]);
}
int main () {
    // freopen("miny.in","r",stdin);
    // freopen("miny.out","w",stdout);
    ll T=1;
    // T=read();
    while (T--) {
        solve();
    }
    return 0;
}