P4587 [FJOI2016]神秘数 题解

[传送门：P4587 [FJOI2016]神秘数](https://www.luogu.com.cn/problem/P4587) **主席树** ## Solution 思路其实就是一楼大佬的思路，只不过大佬写的有些内容我太弱看不懂，所以来补充一下。 ### 1 对于区间 $[l,r]$，将它升序排序后从左往右扫，设当前可以表示出的数为$[1,x]$，$ans$ 为 $(x + 1)$。 显然，对于当前扫到的数 $a_i$，当且仅当它小于等于 $ans$ 时，才对 $ans$ 有用。 用处即将值域扩大到 $[1,x+a_i]$。 因为在原先 $[1,x]$ 的基础上我们可以依次得到 $(1+a_i),(2+a_i),(3+a_i)+\cdots +(x+a_i)$。 所以只用考虑每次在区间 $[l,r]$ 中小于等于 $ans$ 的数。 ### 2 按照 1 中的思路，若小于等于 $ans$ 的数的和 $res\geq ans$，则一定有未选的且小于等于 $ans$ 的数，令 $ans=res+1$ 即可。（大佬原话，不难理解。） 反之则说明了答案就是 $ans$。 这样可以使得我们不断去更新 $ans$，直到得出最大的 $ans$。 ### 3 按照 2 中的思路，对于每一个查询，我们都要不断去询问区间 $[l,r]$ 中值小于等于 $ans$ 的数，直到找到答案。 所以，要用主席树来维护。**此题的主席树是对值域的划分。** 对于 $root_i$，它的子树维护的是 $a_1$ 到 $a_i$ 中每一个数在值域里的状态。 正因如此，我们才可以查询某一区间内小于等于某数的所有数之和。 具体地，可以看主席树模板：[P3834 【模板】可持久化线段树 2](https://www.luogu.com.cn/problem/P3834)，它也是类似的对值域的划分。 ## Code ```cpp #include<bits/stdc++.h> using namespace std; #define rep(i, a, b) for(int i = a; i <= b; ++i) const int maxn = 1e5 + 5; const int inf = 1e9; int n; int a[maxn]; struct node{ int l, r; int sum; }t[maxn << 5]; int m; int lt, rtm; int tot; int rt[maxn]; inline int addt(int lst, int l, int r, int k, int d) { int nw = ++tot; t[nw] = t[lst], t[nw].sum += d; if(l == r) return nw; int mid = (l + r) >> 1; if(k <= mid) t[nw].l = addt(t[lst].l, l, mid, k, d); else t[nw].r = addt(t[lst].r, mid + 1, r, k, d); return nw; } inline int query(int pl, int pr, /*在 a[pl] 到 a[pr] 这一区间中*/int l, int r,/*当前询问范围*/ int ql, int qr/*权值的合法范围*/) { if(ql <= l and qr >= r) return t[pr].sum - t[pl].sum; int mid = (l + r) >> 1, res = 0; if(ql <= mid) res += query(t[pl].l, t[pr].l, l, mid, ql, qr); if(qr > mid) res += query(t[pl].r, t[pr].r, mid + 1, r, ql, qr); return res; } int main() { scanf("%d", &n); rep(i, 1, n) scanf("%d", &a[i]); rep(i, 1, n) rt[i] = addt(rt[i - 1], 1, inf, a[i], a[i]); scanf("%d", &m); rep(i, 1, m) { scanf("%d%d", &lt, &rtm); int ans = 1; while(531) { int tmp = query(rt[lt - 1], rt[rtm], 1, inf, 1, ans); if(tmp >= ans) ans = tmp + 1; else break; } printf("%d\n", ans); } return 0; } ``` ------------ 感谢阅读。 辛苦管理员审核，如有问题烦请指出。