题解：P11405 [RMI 2020] 秘鲁 / Peru

Purslane · 2024-12-20 21:24:08 · 题解

Solution

写了个搞笑的 O(n \log n)，显然不是 intended solution，但是 priority_queue 常数极小，也就这么过了。

关键结论：所有攻击的区间两两不交。这个是显然的，可以直接调整法反证。

因此问题变为：将一个序列划分为若干个区间，每个区间长度 \le k，求所有区间最大值和的最小值。

设 dp_i 为前 i 个数的答案，则

这个东西呢，你用线段树 + 单调栈可以做到大常数 O(n \log n)。

但是考虑可能的 j，只有两种情况：

暴力维护第二种情况的所有值，发现 i 变更后，最多新增 O(1) 个可能的 j，直接用一个延迟删除的 priority_queue 就能做了。

#include<bits/stdc++.h>
#define ll long long 
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=3e6+10,MOD=1e9+7;
int n,k,s[MAXN],nxt[MAXN];
ll dp[MAXN];
struct INFO {int pos;ll val;};
bool operator <(INFO A,INFO B) {return A.val>B.val;}
int solve(int N,int K,int S[]) {
    n=N,k=K;
    ffor(i,1,n) s[i]=S[i-1];
    deque<INFO> q1;
    priority_queue<INFO> q2;
    stack<int> st;
    ffor(i,1,n) {
        while(!q1.empty()&&s[i]>=q1.back().val) q1.pop_back();
        q1.push_back({i,s[i]});
        while(q1.front().pos<=i-k) q1.pop_front();
        dp[i]=dp[max(0,i-k)]+q1.front().val;
        while(!st.empty()&&s[i]>=s[st.top()]) nxt[st.top()]=-1,st.pop();
        if(!st.empty()) {
            int u=st.top();
            nxt[u]=s[i];
            q2.push({u,dp[u]+s[i]});    
        }
        st.push(i);
        while(!q2.empty()&&(q2.top().pos<i-k||nxt[q2.top().pos]+dp[q2.top().pos]!=q2.top().val)) q2.pop();
        if(!q2.empty()) dp[i]=min(dp[i],q2.top().val);
    }
    ll ans=0,mul=1;
    roff(i,n,1) ans=(ans+dp[i]%MOD*mul)%MOD,mul=mul*23%MOD;
    return ans;
}