题解 | 能量辐射

void solve(){
    int n;cin>>n;
    vector<int> a(n+1);
    vector<int> v(n+1);
    for(int i=1;i<=n;i++)cin>>a[i]>>v[i];
    stack<int> sk;
    vector<int> ans(n+1);
    for(int i=1;i<=n;i++){
        while(!sk.empty()&&a[sk.top()]<=a[i])sk.pop();
        if(!sk.empty())ans[sk.top()]+=v[i];
        sk.push(i);
    }
    sk=stack<int>();
    for(int i=n;i>=1;i--){
        while(!sk.empty()&&a[sk.top()]<=a[i])sk.pop();
        if(!sk.empty())ans[sk.top()]+=v[i];
        sk.push(i);
    }
    int maxl=-1;
    for(int i=1;i<=n;i++){
        maxl=max(maxl,ans[i]);
    }
    cout<<maxl<<endl;
}

本题的核心在于对每个发射站，快速找到左右两侧第一个比它高的发射站。这正是单调栈的经典应用场景。

单调栈是一种保持栈内元素（此处为发射站高度）具有单调性的数据结构。此处，我们维护一个从栈底到栈顶单调递减的栈，这样可以保证栈内每个元素的下一个元素就是其左侧（或右侧）第一个比它高的发射站。

核心思想

1. 两次扫描：从左向右扫描：处理每个发射站 i，找到其左侧第一个比它高的站，并将 Vi​的能量累加到该高站接收的能量值中。从右向左扫描：找到每个发射站 i的右侧第一个比它高的站，同样进行能量累加。
2. 单调栈维护：在扫描过程中，若当前站高度高于栈顶站，则栈顶站已找到其右侧高站（当前站），可被弹出；弹出后新的栈顶即为当前站的左侧高站。