标签: 主席树

5 篇文章

P4587 [FJOI2016]神秘数
Description 题目链接:P4587 一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如S={1,1,1,4,13}, 1 = 1 2 = 1+1 3 = 1+1+1 4 = 4 5 = 4+1 6 = 4+1+1 7 = 4+1+1+1 8无法表示为集合S的子集的和,故集合S的神秘数为8。 现给定n个正整数a[1…
LuoguP2839 [国家集训队]middle
Description 题目链接 一个长度为 $n$ 的序列 $a$,设其升序排序之后为 $b$,那么序列 $a$ 的中位数定义为 $b_{\lfloor\frac{n}{2}\rfloor}$,其中 $a,b$ 从 $0$ 开始标号,除法取下整。 给你一个长度为 $n$ 的序列 $s$。回答 $Q$ 个这样的询问:$s$ 的左端点在 $[a,b]…
Luogu P2617 Dynamic Rankings 题解
Description 题目链接 给定一个含有 $n$ 个数的序列 $a_1,a_2 \dots a_n$​,需要支持两种操作: Q l r k 表示查询下标在区间 $[l,r]$ 中的第 $k$ 小的数C x y 表示将 $a_x$​ 改为 $y$ Solution 树状数组套主席树 Code #include<…