题解 P2248 【分段】
标签：线段树，单调队列，动态规划。
令front[i]表示最近的不能和i共区间的元素位置，显然front[i]可以在输入时通过取最大值处理出来。显然，i不能和front[i]以及位置更靠前的元素划为一段。
令dp[i]表示使区间[1, i]中的元素合法分段所需要的最小代价
考虑向位置i转移，假设有位置j在i前且合法。则要么dp[i] = dp[i - 1] + k，即元素i单独分一段，要么找到某个值j使得dp[j] + cost(j + 1, i)最小。其中cost(j + 1, i) = s * (Max(j + 1, i) - Min(j + 1, i)),即将区间[j + 1, i]分为一段的代价。
显然，重点在于如何高效地找到j使得dp[j] + cost(j + 1, i)最小。
用线段树维护。线段树维护的是从之前某一位置j进行转移且将位置j与当前位置划为一段的最小代价，当然使用时是区间查询而不关心具体位置。假定我们已经求得了dp[i]，且将区间[j, i - 1]划为一段的代价记为V0，那么我们发现，如果有位置j < i且Vj为Min(j + 1, i - 1)且Vi < Vj，即在位置j之后除了Vi没有比Vj小的值，那么如果位置i+1希望从j位置或者更靠前一些的位置转移，则代价为V0 + s * (Vj - Vi)，因为Vi取代了Vj最小值的地位，需要补上增加的代价。为什么说是更靠前“一些”呢？因为位置j之前可能有比Vj还小的元素，而这个时候如果有Vk > Vi，那么对应需要增加的代价就是s * (Vk - Vi)。因此，这些位置是从后往前值递减的，因为如果出现了位置j > k且Vj < Vk，那么k不可能是之后计算代价用到的最小值，我们就不再关心了。因此，可以用一个从前往后单调递增的单调队列Min来维护这个位置的序列，然后用线段树做区间加法维护最小代价。
最大值同理利用单调队列维护。
显然，文字叙述过于繁琐，更简明的思路请参照代码。
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <algorithm>
namespace my {
template <class T> inline void getmax(T& a, T b) { if (b > a) a = b; }
template <class T> inline void getmin(T& a, T b) { if (b < a) a = b; }
}
const int maxn(112345);
namespace seg {
long long val[maxn << 2], tag[maxn << 2];
#define ls (n << 1)
#define rs (n << 1 | 1)
inline void push(int n) {
if (tag[n]) {
val[ls] += tag[n], tag[ls] += tag[n];
val[rs] += tag[n], tag[rs] += tag[n];
tag[n] = 0;
}
}
inline void update(int n) {
val[n] = std::min(val[ls], val[rs]);
}
long long quary(int n, int left, int right, int l, int r) {
if (left == l && right == r) {
return val[n];
}
push(n);
int mid(left + right >> 1);
if (r <= mid) return quary(ls, left, mid, l, r);
else if (l > mid) return quary(rs, mid + 1, right, l, r);
return std::min(quary(ls, left, mid, l, mid), quary(rs, mid + 1, right, mid + 1, r));
}
void modify(int n,int left, int right, int l, int r, long long v) {
if (left == l && right == r) {
val[n] += v, tag[n] += v;
return;
}
push(n);
int mid(left + right >> 1);
if (r <= mid) modify(ls, left, mid, l, r, v);
else if (l > mid) modify(rs, mid + 1, right, l, r, v);
else modify(ls, left, mid, l, mid, v), modify(rs, mid + 1, right, mid + 1, r, v);
update(n);
}
}
std::deque<int> min, max;
int n, m, front[maxn];
long long k, s, v[maxn], dp[maxn];
void solve() {
int f(0);
for (int i(1); i <= n; ++i) {
my::getmax(f, front[i]);
while (!min.empty() && min.front() <= f) min.pop_front();
int fp(i - 1);//在fp之后的最小值不是v[min.back()]，因此只加区间[fr + 1, fp]
while (!min.empty() && v[min.back()] >= v[i]) {
//v[i]取代v[pos]成为之后的最小值，v[pos]对之后无“贡献”
int pos(min.back()); min.pop_back();
int fr(min.empty() ? f : min.back());
seg::modify(1, 1, n, fr + 1, fp, s * (v[pos] - v[i]));
//v[i]取代v[pos]成为之后的最小值，故增加s * (v[pos] - v[i])
fp = fr;
} min.push_back(i);
while (!max.empty() && max.front() <= f) max.pop_front();
fp = i - 1;
while (!max.empty() && v[max.back()] <= v[i]) {
int pos(max.back()); max.pop_back();
int fr(max.empty() ? f : max.back());
seg::modify(1, 1, n, fr + 1, fp, s * (v[i] - v[pos]));
fp = fr;
} max.push_back(i);
dp[i] = dp[i - 1] + k;
if (f + 1 < i) my::getmin(dp[i], seg::quary(1, 1, n, f + 1, i) + k);
//从[f + 1, i]中找到一个最合适的位置p使得p与i划分为一段且总代价最小
if (i != n) seg::modify(1, 1, n, i + 1, i + 1, dp[i]);
//读者可以体会一下为什么要在i + 1处加上dp[i]以及为什么这么做是对的
}
printf("%lld\n", dp[n]);
}
int main() {
scanf("%d%d%lld%lld", &n, &m, &k, &s);
for (int i(1); i <= n; ++i) scanf("%d", v + i);
for (int i(0); i != m; ++i) {
int a, b; scanf("%d%d", &a, &b);
if (a > b) std::swap(a, b);
my::getmax(front[b], a);
}
solve();
return 0;
}