带权中位数

带权中位数 ：给定数组 W,XW, X，保证 Wi≥0W_i \ge 0。求 argmin⁡k∑i=1NWi∣k−Xi∣\displaystyle \operatorname*{argmin}_{k} \sum_{i=1}^{N} W_i \lvert k - X_i \rvert。

先考虑不带权的，那么带权就是 XiX_i 出现了 WiW_i 次。按 XiX_i 升序排序，顺序累加 WiW_{i}，找到第一个使得 WiW_{i} 的前缀和 ≥12∑i=1NWi\displaystyle \ge \dfrac{1}{2}\sum \limits_{i=1}^{N} W_i 的位置 mm，则最优解为 k∗=Xmk^* = X_m。

例 1：NN 个人围成一圈，第 ii 个人初始有 AiA_i 个物品。ii 与 (i+1) mod N(i+1) \bmod N 每传递 11 个物品的代价为 BiB_i。欲通过若干次传递使每个人手中的物品数量相同，求最小总代价。

设 di=Ai−Aˉd_i = A_i - \bar{A}。设 ii 传递给 (i+1) mod N(i+1) \bmod N 了 cic_i 个（可能为负）。根据物品守恒，ci=cN+Dic_i = c_N + D_i。则总传递代价 Ans(cN)=∑i=1NBi∣ci∣=∑i=1NBi∣cN+Di∣\displaystyle \text{Ans}(c_N) = \sum_{i=1}^N B_i \lvert c_i\rvert = \sum_{i=1}^N B_i \lvert c_N + D_i\rvert。欲构造 cNc_N 以最小化 Ans(cN)\text{Ans}(c_N)，这就是带权中位数问题。

例 2：序列 A,BA, B，设有理数序列 c,dc, d 满足 (Ai+ci)(Bj+dj)=(Aj+cj)(Bi+di)(A_i+c_i)(B_j+d_j)=(A_j+c_j)(B_i+d_i)，最小化 ∑∣ci∣+∣di∣\sum |c_i|+|d_i|。(ABC479G)

要么 ci≡0c_{i} \equiv 0，要么 di≡0d_{i} \equiv 0。以 ci≡0c_{i} \equiv 0 为例，设 Bi+di=kAiB_i+d_i = k A_{i}，需最小化 ∑∣di∣=∑∣kAi−Bi∣=∑∣Ai∣∣k−BiAi∣\sum |d_{i}| = \sum |k A_{i} - B_{i}| = \sum |A_{i}| \biggl|k - \dfrac{B_{i}}{A_{i}}\biggr|，这就是带权中位数问题。注意特判非零的 AA 为空。

将 (Ai,Bi)(A_{i}, B_{i}) 看作二维坐标系的点，将每个点移动到同一条过原点的直线，代价是 ∣ci∣+∣di∣|c_i|+|d_i|。当 ∣k∣⩽1|k| \leqslant 1 时，点纵向移动不劣，∣k∣>1|k| > 1 时，横向不劣。

排序不等式

排序不等式 ：只改变配对方式，

  • ∑AiBπ(i)\sum A_{i} B_{\pi(i)}：同序最大，逆序最小
  • ∑∣Ai−Bπ(i)∣\sum |A_{i} - B_{\pi(i)}|：同序最小，逆序最大
  • ∑(Ai−Bπ(i))2\sum (A_{i} - B_{\pi(i)})^{2}：同序最小，逆序最大

例 ：序列 A,BA, B，其中 ∣A∣⩽∣B∣|A| \leqslant |B|，选取 BB 的任一 ∣A∣|A| 元子列的任一排列 bb，最大化 ∑∣Ai−bi∣\sum |A_{i}-b_{i}|。(CF1921D)

不妨设 AA 递增。由排序不等式，bb 递减，将 BB 倒序排序，再选取一个递减子列 bb。而且 bb 是 BB 的某前缀与某后缀拼接起来的。枚举分界点计算答案。O(Nlog⁡N)\mathcal{O}(N\log N)。

区间包含树

区间包含树 ：给定若干区间 [Li,Ri)[L_i,R_i)，要么互不相交（Ri≤LjR_i \le L_j），要么一个包含另一个（Li≤Lj<Rj≤RiL_i \le L_j < R_j \le R_i），不存在交叉重叠（Li<Lj<Ri<RjL_{i} < L_{j} < R_{i} < R_{j}），构造区间包含树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 区间 -> 树 (0 是虚拟根)
vector<vector<int>> build(const vector<pair<int, int>>& seg) {
    const int N = int(seg.size());
    struct Seg {
        int l, r, id;
    };
    vector<Seg> A(N + 1);
    constexpr int inf = 0x3f3f3f3f;
    A[0] = {-inf, inf, 0}; // 虚拟根 
    for (int i = 0; i < N; i++) {
        auto [l, r] = seg[i];
        A[i + 1] = {l, r, i + 1};
    }
    ranges::sort(A, {}, [](const Seg& x) { return pair(x.l, -x.r); });
    vector<int> s;
    vector<vector<int>> adj(N + 1);
    for (int i = 0; i <= N; i++) {
        while (!s.empty() && A[s.back()].r <= A[i].l) {
            s.pop_back();
        }
        if (!s.empty()) {
            adj[A[s.back()].id].push_back(A[i].id);
        }    
        s.push_back(i);
    }
    return adj;
}

异或线性基

求子集的数量，满足异或和为 0。答案为 2N−rank⁡2^{N-\operatorname{rank}}。

正则括号串

正则括号串 (Regular Bracket Sequence, RBS)：

  • 生成方式：连接与加括号
  • 前缀和保持非负
  • 一一对应于有序树 T=(T1T2…Tk)T = (T_{1}T_{2}\dots T_{k})
  • 一一对应于有序二叉树 T=(TL)TRT = (T_{L})T_{R}
    ——CuteCube
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 括号串（森林）-> 有序树，0 为虚拟根 
vector<vector<int>> build(string S) {
    S = "(" + S + ")";
    vector<vector<int>> adj;
    stack<int> s;
    for (auto c : S) {
        if (c == '(') {
            int x = int(adj.size());
            if (!s.empty()) {
                adj[s.top()].push_back(x);
            }
            s.push(x);
            adj.emplace_back();
        } else {
            s.pop();
        }
    }
    return adj;
}
// 有序树 -> 原括号串，跳过虚拟根 
string restore(const vector<vector<int>>& adj) {
    string S;
    auto dfs = [&](this auto&& self, int x) -> void {
        S += '(';
        for (auto y : adj[x]) {
            self(y);
        }
        S += ')';
    };
    for (auto y : adj[0]) {
        dfs(y);
    }
    return S;
}

例 1：删除 BS SS 至多 KK 个字符，最小化最长 RBS 子序列。(CF2233C)

先做一遍括号匹配，最后希望剩下 )))((，右括号与左括号有个分界点。重点是绝对不存在一对匹配的括号，左括号在左半区，右在右半区，所以所有匹配的括号对要么全在左半，要么全在右半。左半的括号对删左，右半删右。如此最优。

例 2：RBS SS，任意操作：选择两个不交的 RBS 子串，并交换位置。判断最终是否可以变换为 TT。(CF2210D)

在树上做，操作等价于：选两个没有祖先关系的点 x,yx, y，将 xx 的若干子节点的子树与 yy 的做交换。不变量：叶子节点数；从根到第一个分叉节点之间的节点数。