一个赛时想到的另类 DP 做法。
Solution
容易将原题转化为一个人乘电梯每次上下一层。
对于 \(a_i<b_i\) 是好处理的，记 \(\displaystyle m=\max_{1\leq i\leq n}\{a_i,b_i\}\)，只需要跑到 \(m\) 即可解决所有这种条件。
对于 \(a_i>b_i\) 的条件，我们除了到 \(m\) 外，还需要额外地从上往下跑。显然我们跑一轮可以解决掉多个询问，设解决的询问集合是 \(S\)，则分两类：
- 先下后上，代价为 \(\displaystyle(\max_{i\in S}\{a_i\}-\min_{i\in S}\{b_i\})\times 2\)，可以跑若干轮。
- 到 \(m\) 再下去，代价为 \(m-\min_{i\in S}\{b_i\}\)，只能跑一轮。
第二种跑法只能最后跑，故在计算答案时考虑，下文考虑第一种跑法。
将 \(a_i>b_i\) 的询问按 \(a_i\) 排序，设 \(f_{i}\) 是用第一种跑法满足前 \(i\) 个条件的最小额外次数。观察发现，每次处理的条件是一个区间。
证明（可以跳过不看）：假设原来两个区间里元素组成的集合分别是是 \(P,Q\)，\(\forall i\in P,j\in Q\)，\(a_i\leq a_j\)。则考虑将 \(Q\) 中的一个元素放入 \(P\) 中使答案变优。由于放入后，\(P\) 的代价会变大，要是答案变优，需要 \(Q\) 代价变小。若取 \(Q\) 中 \(b_i\) 最小的元素 \(k\) 加入 \(p\)，则 \(Q\) 中 \(a_i\) 小于 \(a_k\) 的元素加入 \(P\) 代价不变；若取 \(Q\) 中 \(a_i\) 最大的元素加入 \(P\) 中，由于 \(\forall i\in P,j\in Q\)，\(a_i\leq a_j\)，代价和变大。证明 \(P\) 中元素加入 \(Q\) 中不优同理。
易得转移方程：
\[f_{i}=\min_{0\leq j<i}\{f_{j}+(a_i-\min_{j<k\leq i}\{b_k\})\times 2\}=\min_{0\leq j<i}\{f_{j}-2\times\min_{j<k\leq i}\{b_k\}\}+2\times a_i \]考虑优化这个 DP。
令 \(\displaystyle d_x=\min_{x<j\leq i}\{b_j\}\)，则转移方程为 \(\displaystyle f_i=\min_{1< j\leq i}\{f_{j-1}-2\times d_j\}+2\times a_i\)。每次更新 \(d_x\gets\min\{d_x,b_i\}\)。
容易发现 \(d\) 是不降序列。用珂朵莉树维护段连续相同的 \(d\)。加入 \(a_i\) 只需要二分出第一个 \(a_i\leq d_j\) 的位置 \(j\)，然后将 \(j\sim i\) 合并为新段即可。
为了求出 \(f_i\)，还需要维护每块里面的 \(\displaystyle\min_{j-1\leq k\leq i-1}\{f_{k}\}+2\times d\) 和它的前缀 \(\min\)。为了维护它们，合并时还需要用一颗线段树来求出 \(\displaystyle\min_{j-1\leq k\leq i-1}\{f_{k}\}\)。
最后，只需要枚举第二种跑法从哪里开始就行啦，答案为 \(\displaystyle\min_{0\leq i\leq n}\{f_{i}+2m-\min_{i<j\leq n}\{b_i\}\}\)。
时间复杂度 \(\mathcal{O}(n\log n)\)。
Code
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
namespace Milkcat {
typedef long long LL;
typedef pair<LL, LL> pii;
typedef vector<LL> poly;
const int N = 1e6 + 5;
namespace SGT {
LL sum[N << 2];
inline void push_up(int p) { sum[p] = min(sum[p << 1], sum[p << 1 | 1]); }
void modify(int p, int l, int r, int t, LL k) {
if (l == r) { sum[p] = k; return; }
int mid = (l + r) >> 1;
if (t <= mid) modify(p << 1, l, mid, t, k);
if (t > mid) modify(p << 1 | 1, mid + 1, r, t, k);
push_up(p);
}
LL query(int p, int l, int r, int nl, int nr) {
if (nl <= l && r <= nr) return sum[p];
LL mid = (l + r) >> 1;
if (nl <= mid && nr > mid)
return min(query(p << 1, l, mid, nl, nr), query(p << 1 | 1, mid + 1, r, nl, nr));
if (nl <= mid) return query(p << 1, l, mid, nl, nr);
if (nr > mid) return query(p << 1 | 1, mid + 1, r, nl, nr);
}
};
using namespace SGT;
struct node {
mutable LL v, l, r, pre;
node(LL HCY, LL AK, LL IOI, LL Orz) : v(HCY), l(AK), r(IOI), pre(Orz) {}
bool operator < (const node& x) const { return v < x.v; }
};
LL n, m, cnt, x, y, mn, ans, f[N]; pii a[N];
set<node> s;
int main() {
memset(sum, 0x3f, sizeof sum);
memset(f, 0x3f, sizeof f);
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> x >> y, m = max({m, x, y});
if (x > y) a[++ cnt] = pii(x, y);
}
n = cnt, sort(a + 1, a + 1 + n);
f[0] = 0, modify(1, 0, n, 0, 0);
for (int i = 1; i <= n; i ++) {
auto it = s.lower_bound(node(a[i].se, 0, 0, 0));
LL t = (it == s.end() ? i : it->l), last = (it == s.begin() ? m + 1 : prev(it)->pre);
s.erase(it, s.end());
s.insert(node(a[i].se, t, i, min(last, query(1, 0, n, t - 1, i - 1) - a[i].se * 2)));
f[i] = prev(s.end())->pre + a[i].fi * 2, modify(1, 0, n, i, f[i]);
}
mn = m, ans = INT_MAX;
for (int i = n; i >= 0; i --)
ans = min(ans, f[i] + m * 2 - mn), mn = min(mn, a[i].se);
cout << ans << '\n';
return 0;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
while (T --) Milkcat::main();
return 0;
}