（最近做题太少，只能水一个简单的文章。）

大概就是三个题目混合起来。

首先给出定义：一个可重集 $S$ 可以表示出数 $x$，当且仅当存在 $T\subset S$ 使得 $T$ 中元素的和恰为 $x$。

例 1

题意：给定数组 $a$ 和数 $n$，问最少向 $a$ 中插入多少个在 $[1,n]$ 中的正整数，能让 $a$ 构成的可重集表示出 $x$。（来源：Leetcode 330）

贪心。

一个很显然的想法是：如果当前数组覆盖不到 $x$，那么我们肯定要添加一个 $\le x$ 的数到数组中去。我们现在就考虑怎么把这个数填上，让它产生的效果尽量好。

我们假设当前可以覆盖到的区间是 $[1,x)$，那么如果把 $y\le x$ 加到数组中，那么整个数组就可以多覆盖 $y,y+1,\cdots ,y+x-1$ 这些数，换言之，覆盖范围就多了 $[y,y+x)$ 这一块。由于 $y\le x$，故两个区间可以合并为 $[1,y+x)$。那么显然，如果要加入的话当然是加入 $x$ 可以使得覆盖范围增加的最多。这就回答了我们之前的问题。

这样算法的雏形就出来了：我们维护这样一个区间，记录最小的无法覆盖到的数 $x$。一开始设 $x=1$。然后从小到大用 $a$ 中的值去更新 $x$，如果当前的值大于 $x$ 就表明一定要新加入一个数，由上一段的结论可知加入 $x$ 是最好的。如此反复，直到全部覆盖为止。

---

例 1 中说明了如何利用贪心思想确定一个可重集 $S$ 能否表示出 $x$。很容易将其扩展到区间询问上。

例 2

题意：给定长为 $n$ 的序列 $a$，$m$ 次询问，每次给出 $l,r$，问 $a[l:r]$ 构成的可重集无法表示的最小非负整数是多少。（来源：FJOI 2016 神秘数）

方法一

主席树？

方法二

建线段树，对每个点维护一个值 $x$ 和一个有序 pair 列表，表示这个点对应的区间做完合并后，可以覆盖的区间为 $[0,x)$，且剩余的待合并的数为 $(y_1,z_1),(y_2,z_2),\cdots$。

这个列表的意义是：如果 $x$ 增大到某个不小于 $y_1$ 的 $x^{\prime }$，那么新的可覆盖区间会变成 $[0,x^{\prime }+y_1+z_1)$，但这时仍然有 $y_2>x^{\prime }+y_1+z_1$。

对于 $(y_2,z_2)$ 的定义类似：如果 $x^{\prime }+y_1+z_1$ 增大到某个不小于 $y_2$ 的 $x^{\prime \prime }$，那么新的可覆盖区间会变成 $[0,x^{\prime \prime }+y_2+z_2)$，但这时仍然有 $y_3>x^{\prime \prime }+y_2+z_2$。对于 $(y_3,z_3)$ 之类的可以类似定义下去。

这样定义之后，容易发现一个列表的长度至多是 $\log 10^9$，因为 $y$ 是两倍两倍增长的。而合并两个点的信息也只需要归并两个列表的信息。因此总的时间复杂度为 $O((n+m)\log n\log ({\max }_i{a}_i))$。

例 3

题意：在例 2 的基础上加入单点修改操作。（来源：2019 ICPC 徐州区域赛 H 题）

直接在例 2 的方法二上进行稍许修改就能得到解法，代码如下。

#include <bits/stdc++.h> #define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp) #define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp) using namespace std; typedef long long ll; typedef pair<ll, ll> intpair; int read(){ int f = 1, x = 0; char c = getchar(); while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();} while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar(); return f * x; } int n, m; int a[200005], siz; ll seg1[526000] = {0}, tmpv; vector<intpair > seg2[526000], tmp, tmp2; ll mmerge(ll xx1, ll xx2, vector<intpair >& v1, vector<intpair >& v2, vector<intpair >& res){ ll newx = xx1 + xx2 - 1; int siz1 = v1.size(), siz2 = v2.size(); int lp = 0, rp = 0; while (lp < siz1 || rp < siz2){ if (lp == siz1 || (rp < siz2 && v2[rp].first < v1[lp].first)){ // rp if (v2[rp].first <= newx) newx += v2[rp].first + v2[rp].second; else { if (res.empty() || v2[rp].first > 2ll * res.back().first + res.back().second) res.push_back(v2[rp]); else res.back().second += v2[rp].first + v2[rp].second; } ++rp; } else { if (v1[lp].first <= newx) newx += v1[lp].first + v1[lp].second; else { if (res.empty() || v1[lp].first > 2ll * res.back().first + res.back().second) res.push_back(v1[lp]); else res.back().second += v1[lp].first + v1[lp].second; } ++lp; } } return newx; } void init(){ n = read(), m = read(); REP(i, 1, n) a[i] = read(); for (siz = 1; siz < n; siz <<= 1) ; REP(i, 1, n) { if (a[i] == 1) seg1[i + siz - 1] = 2; else seg1[i + siz - 1] = 1, seg2[i + siz - 1].push_back(make_pair(a[i], 0)); } REP(i, siz + n, siz + siz - 1) seg1[i] = 1; REPR(i, siz - 1, 1){ seg1[i] = mmerge(seg1[i << 1], seg1[i << 1 | 1], seg2[i << 1], seg2[i << 1 | 1], seg2[i]); } } int _a, _b; void query(int id, int l, int r){ if (l > _b || r < _a) return ; if (l >= _a && r <= _b){ tmp2.clear(); tmpv = mmerge(tmpv, seg1[id], tmp, seg2[id], tmp2); tmp.clear(); for (const auto& p: tmp2) tmp.push_back(p); return ; } int mid = (l + r) >> 1; query(id << 1, l, mid); query(id << 1 | 1, mid + 1, r); } void solve(){ while (m--){ int opr = read(); _a = read(), _b = read(); if (opr == 1){ _a += siz - 1; seg2[_a].clear(); if (_b == 1) seg1[_a] = 2; else seg1[_a] = 1, seg2[_a].push_back(make_pair(_b, 0)); while (_a > 1) _a >>= 1, seg2[_a].clear(), seg2[_a] = mmerge(seg1[_a << 1], seg1[_a << 1 | 1], seg2[_a << 1], seg2[_a << 1 | 1], seg2[_a]); } else { tmpv = 1, tmp.clear(); query(1, 1, siz); printf("%lld\n", tmpv); } } } int main(){ init(); solve(); return 0; }

小结

这类问题是利用值域倍增的好例子，或许解决这类问题的方法能够推广到其他类似的值域倍增型题目上，从而避免去写主席树之类的复杂数据结构。