P5025 [SNOI2017] 炸弹 邪修做法

· · 题解

邪！邪！邪！

我們假設一個點能炸到的區間的左端點和右端點都只由對應的方向來影響，也就是，左端點只被左邊的炸彈更新，右端點只被右邊的炸彈更新，這樣顯然有簡單的 \mathcal O(n) 做法，維護一個單調棧即可。

但是這樣是錯的，因為右邊可能會有超級炸彈可以影響左端點。

但是我們仔細思考，這樣更新而來的左端點要是想要再次更新右端點則其跟右邊的超級炸彈比較半徑至少翻倍，所以我們發現這樣的更新最多左右來回跳 \mathcal O(\log |w|) 次。

所以我們只需要考慮這個更新問題然後跑 \mathcal O(\log |w|) 次樸素做法即可。

這個做法可能存在錯誤，歡迎 Hack。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=5e5+5;
const LL Mod=1e9+7;
LL n,L[N],R[N],Ans,A[N],B[N];
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&A[i],&B[i]);
        L[i]=A[i]-B[i];
        R[i]=A[i]+B[i];
    }
    for(int TT=1;TT<=64;TT++)
    {
        vector<int>V;
        for(int i=1;i<=n;i++)
        {
            vector<int>T;
            while(!V.empty()&&L[i]<=A[V.back()])
            {
                L[i]=min(L[i],L[V.back()]);
                R[i]=max(R[i],R[V.back()]);
                if(A[i]<=R[V.back()])T.push_back(V.back());
                V.pop_back();
            }
            for(int j:T)
            {
                L[j]=min(L[i],L[j]);
                R[j]=max(R[i],R[j]);            
            }
            V.push_back(i);
        }
        V.clear();
        for(int i=n;i>=1;i--)
        {
            vector<int>T;
            while(!V.empty()&&A[V.back()]<=R[i])
            {
                L[i]=min(L[i],L[V.back()]);
                R[i]=max(R[i],R[V.back()]);
                if(L[V.back()]<=A[i])T.push_back(V.back());
                V.pop_back();
            }
            for(int j:T)
            {
                L[j]=min(L[i],L[j]);
                R[j]=max(R[i],R[j]);            
            }
            V.push_back(i);
        }
    }
    for(int i=1;i<=n;i++)
    {
        int k=upper_bound(A+1,A+n+1,R[i])-lower_bound(A+1,A+n+1,L[i]);
        Ans=(Ans+1ll*i*k)%Mod;
    }
    printf("%lld\n",Ans);
    return 0;
}