自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:07:04，当前版本为作者最后更新于2024-12-20 21:24:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Solution

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

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

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

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

$$dp_i = \min_{0< i-j \le k} \{ dp_j + \max_{j < k \le i} f_j \} $$

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

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

1. $i-j=k$。
2. $f_{j+1}$ 在 $i$ 时的单调栈中。

暴力维护第二种情况的所有值，发现 $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;
}