在最优解问题中，支配对指的是两个方案之间的偏序关系。
其思想为：如果方案 \(s_1\) 永远劣于 \(s_2\)，则可以不考虑，以此减少方案数，达到减小复杂度的目的。
可以认为支配对就是调整法的一种。
如方案 \(s_1, s_2\)：
-
\(s_1\) 合法是 \(s_2\) 合法的充分条件。
-
\(s_1, s_2\) 均合法时，必有 \(s_2\) 优于 \(s_1\)。
-
以上条件满足时，尽可能使支配条件弱，达到减少更多无用方案的目的。
[JOI Open 2019] 三级跳 / Triple Jump
link
题意
给定序列 \(a\)，多次查询区间 \([l,r]\), \(\max \limits _ {i \lt j \lt k, j - i \le k - j} a_i + a_j + a_k\)。
\(n \le 5 \times 10 ^ 5\)。
思路
我们考虑方案：\(s_1 = (i_1, j_1, k_1), s_2 = (i_2, j_2, k_2)\)。
容易得到，\(s_2\) 支配 \(s_1\) 的条件是：
-
\(i_1 \le i_2 \lt k_2 \le k_1\)，对应上文第一条。
-
\(a_{i_1} + a_{j_1} + a_{k_1} \lt a_{i_2} + a_{j_2} + a_{k_2}\)，对应上文第二条。
显然，这样的条件太强了，考虑弱化。
我们发现，方案本身有一定性质：固定 \(i, j\)，\(k\) 即为一个后缀 \(\max\)。
我们发现，若满足 \(i_1 \le i_2 \lt j_2 \le j_1\)，则 \(s_2\) 对应的后缀是严格包含 \(s_1\) 对应的，那么关于 \(k\) 的都能去掉：
-
\(i_1 \le i_2 \lt j_2 \le j_1\)
-
\(a_{i_1} + a_{j_1} \lt a_{i_2} + a_{j_2}\)
得到了支配对条件，来推导最优解的性质。
可以表述为，若一个区间 \([l, r]\)，有一个子区间的端点 \(a\) 值和大于区间端点 \(a\) 之和，就不优秀。
易得，其充分必要条件为，\(\exists i \in [l, r], a_i \gt \min(a_l, a_r)\)。
那么也就是说，所以区间中（不含端点）最大值比两个端点都小的区间可以成为最优解的备选。
那么这种区间满足的性质是，右端点最左边第一个 \(\ge\) 它的数是左端点或左端点右边第一个 \(\ge\) 它的数是右端点。
可以用单调栈维护上述两个指针，即可得到所有的区间。
区间个数是 \(O(n)\) 的，准确地说是 \(2n\) 级别的。
接下来考虑如何处理询问。
如果我们把 \(k\) 的贡献挂在 \((i, j)\) 上，不好处理查询区间的限制，于是反过来视 \((i, j)\) 为操作，把 \(a_i + a_j\) 加到 \([2j - i, n]\) 的 \(k\) 上。
由于一个 \(k\) 可以被多个 \((i, j)\) 贡献，所以取最优。
呼之欲出了，我们应当离线下来扫描线，扫描线的顺序是如何的呢？
若从左往右扫，每次把 \(j = 当前位置\) 的 \((i, j)\) 考虑，发现不好处理查询区间左端点的限制。
所以从右往左扫，每次把 \(i = 当前位置\) 的 \((i, j)\) 考虑进来，由于现在贡献都挂在 \(k\) 上，用查询区间右端点限制 \(k\) 的取值范围即可。
时间复杂度 \(O((n + q) \log n)\)
代码
const int N = 5e5 + 5;int n, q;
int a[N];struct node{int v, mx; // v: 原序列 | mx: 原序列 + 贡献值int mx_tag; // 取 max 的 tag
} t[N << 2];#define ls(x) (x << 1)
#define rs(x) ((x << 1) | 1)
#define mid ((l + r) >> 1)void push_up(int x){t[x].v = max(t[ls(x)].v, t[rs(x)].v);t[x].mx = max(t[ls(x)].mx, t[rs(x)].mx);
}
void hard(int x, int v){t[x].mx_tag = max(t[x].mx_tag, v);t[x].mx = max(t[x].mx, t[x].v + t[x].mx_tag);
}
void push_down(int x){if(!t[x].mx_tag) return;hard(ls(x), t[x].mx_tag);hard(rs(x), t[x].mx_tag);t[x].mx_tag = 0;
}
void build(int x, int l, int r){if(l == r){t[x].v = a[l];return;}build(ls(x), l, mid);build(rs(x), mid + 1, r);push_up(x);
}
void modify(int x, int l, int r, int ql, int qr, int v){if(ql <= l && r <= qr){hard(x, v);return;}push_down(x);if(ql <= mid) modify(ls(x), l, mid, ql, qr, v);if(qr > mid) modify(rs(x), mid + 1, r, ql, qr, v);push_up(x);
}
int query(int x, int l, int r, int ql, int qr){if(ql <= l && r <= qr){return t[x].mx;}push_down(x);if(ql > mid) return query(rs(x), mid + 1, r, ql, qr);if(qr <= mid) return query(ls(x), l, mid, ql, qr);return max(query(ls(x), l, mid, ql, qr), query(rs(x), mid + 1, r, ql, qr));
}
#undef mid
#undef ls
#undef rsvector<int> range[N];
vector<pair<int, int>> qry[N];pair<int, int> stk1[N];
int top1;
pair<int, int> stk2[N];
int top2;int ans[N];void solve_test_case(){n = read();rep(i, 1, n){a[i] = read();}rep(i, 1, n){while(top1 && stk1[top1].first < a[i]) top1--;if(stk1[top1].second) range[stk1[top1].second].push_back(i);stk1[++top1] = {a[i], i};}per(i, n, 1){while(top2 && stk2[top2].first < a[i]) top2--;if(stk2[top2].second) range[i].push_back(stk2[top2].second);stk2[++top2] = {a[i], i};}build(1, 1, n);q = read();rep(i, 1, q){int l = read(), r = read();qry[l].push_back({r, i});}per(l, n, 1){for(int r : range[l]){if(2 * r - l <= n){modify(1, 1, n, 2 * r - l, n, a[l] + a[r]);}}for(auto [r, qid] : qry[l]){ans[qid] = query(1, 1, n, l, r);}}rep(i, 1, q){write(ans[i]);}
}