思路讲解
这是问题的简单版本。版本之间唯一的区别在于和的上限。在这个版本中，且。
你有一群只圣诞驯鹿。第只驯鹿的力量是。
只圣诞驯鹿组的运载能力计算如下：
-
驯鹿的力量按非递增顺序排序。我们把排序后的力量列表表示为，其中；
-
然后，这群驯鹿的运载能力等于。
注意，一些驯鹿可能对群体的运载能力没有贡献。
你需要处理三种类型的查询：
-
添加一只力量为的驯鹿到群中；
-
从驯鹿群中移除一只力量为的驯鹿；
-
计算选择一些驯鹿（可能是所有）的方式数量，使得所选群体的运载能力至少为。
如果群中有多只力量相同的驯鹿，它们被视为不同的驯鹿。例如，如果你有两只力量各为的驯鹿，并且需要计算选择运载能力至少为的群体的方式数量，那么有种选择方式：选择第一只驯鹿，选择第二只驯鹿，或者选择它们两只。
思路讲解
这个全部都和 2 的次方有关系，我们不自觉的就会往二进制的方向想，但是问题在于，我们如何处理这个进位问题？
等等，有没有一种可能，我们不需要处理进位问题？，由于这个 C 是非严格递减的，即便在全部相等的前提下，因为右移作用越来越强烈，其为 1 的地方也在不断往后移动，因此，其实不会发生进位。
那么既然不会发生进位，第一个堵点就消失了。
接着我们就手玩一下样例，用组合计数的方式解决一下这个问题。
注意，在设计这个计数算法的过程当中，尽量让每层保持独立，即该层只考虑选了该层的数字的情况，这样子前面的数字因为选了他们的组合已经选过了，就不用考虑了，会轻松一点。
不过这道题目能不能做到这一点呢？就让我们看看解法吧。（是可以的，但需要一个关键观察，特别是对于前缀相等情况）
为了方便描述这个过程，令 为输入数组中 i 的频数， 为 i 位置前（包括自己）最晚的 1 出现位置（描述的是查询数字 x）， 这个数字指的是 i 之后所有的数字的频数之和。
答案 ，等于（前缀相同）情况下的辅助统计量 。
其实，在做这道题目的时候，我也不止一次的想过，要是这道题目是 就好了。那所以说，我们为什么不这么做呢？ 维护等于情况， 维护严格大于情况，最后 不就行了？
从高到低遍历，遇到一位 ，有这么几种情况。
- Case 1：
- 如果 ，不需要进行任何操作。
- 如果 ，这个是最复杂的情况。面对这种情况，我还想过
记忆化搜索，dp等等，以解决这个问题，不过最后发现，其实都不用，只需要一个关键观察：即需要选择多少个 i 达到这个等于状态是唯一确定的。你需要选择的数量，就是（自这位开始的）连续 1 的数量，令其为 。- 首先，如果你选择的数量超过了（自这位开始的）连续 1 的数量，那么你就已经超过了，超过的时候至少要驻守 个，才能保证超过，当然，除了 的特殊情况，这种特殊情况因为相等，所以只能更新 ***。***当然，写出这里的统计式子需要有这么一个想法，就是把 和这个前面这部分分开来看。
因为 $\text{conti1}$ 很小，这个式子中间的求和可以用从全组合减去东西的方式优化，达到 $O(W) $ 级别。
- 那么，你如果选的数量小于连续 1 的数量，那么你直接就没有资格相等（以第一个样例为例，$2\ 1\ 1$，只能凑出 $5={(101)}_{2}$，没法凑出 $6={(110)}_{2}$ 这样连续的 1，因为 2 的数量没有达到这个连续段 1 的数量要求）。因此如果 i 的频数小于连续的 1 的数量，直接 break 整个计数过程，并且使得 $eqAns\gets 0$。
- 当然，我们还需要进行**全局右移操作**，即：
1 | auto right_move=[&](ll step) { // 传入参数 step = conti1 |
- Case 2：
注意，思路要清楚， 一定要保证这个答案 ， （统计的）一定要保证前缀严格相等。还是一样， 代表运载能力为 0，只能更新 。 的时候更新 从 开始是因为至少你要选一个才超过是吧。
如果说 ，需要进行这个合法性检验，即如果 ，直接 break 整个计数过程，并且使得 。
⚠️ 注意：我们从高到低遍历，我们要遍历到 -1（就是代表这些驼鹿的运载能力归零了），因此，我们会给整个系统加一个偏移量，0 代表指数为 -1，1 代表为 0，以此类推。
⚠️ 注意：所有的 break 之前，都要使得 。
AC代码
AC，解法可以通过 F2。
https://codeforces.com/contest/2182/submission/357349404
1 | /** |
心路历程（WA，TLE，MLE……）
一开始的算法得出来的答案不太对，因为计数条件和题目规定有不同，题目的 C 数组是排好序的，因此就不在乎顺序了，求的就是组合数。
-
如果 ，还好办吗？我们先想一种，即 ，毕竟有 种选择嘛，这种自然是没什么问题。但是，选了一个 i 以后，其他的 i 我们直接放任不管吗？这是不行的，我们还需要进行右移操作，即 （先右移，再统计这个 数量）。
-
如果 ，这个是最复杂的情况，我们需要求出来新的 。，然后，我们要进行右移操作，我们进行的是全局右移操作，即对 ，，。
- Case 2：
- 如果 ，不需要进行任何操作。
- 如果 ，这个是最复杂的情况。我们发现，这里，如果我们选了第一个数，可以下放 个数字到 ，但是选了第二个数字以后，只能下放 个数字到 ，这种下放，好像不能用公式法做出来，难道每一个都要重新算吗？
- 其实我们会有一个感觉，就是好像，这个是可以记忆化搜索，或者说是 dp 的。可以发现我们的这个状态由这几个因素决定：
- 其实我们会发现这个 dp 和询问的 x 没什么关系，可以放在一起做？不过你说还有操作增删操作？呃，这个确实是一个问题，不过由于整个东西是离线的，我们可以得到每个位置的 的最大值，按照这个 dp，就不会出现问题了。
- 不过还有一个问题，就是如何将查询做到 呢？其实这个的话前缀和即可。不过折腾来，
- 其实我们会有一个感觉，就是好像，这个是可以记忆化搜索，或者说是 dp 的。可以发现我们的这个状态由这几个因素决定：
⚠️ 注意：注意有限右移操作和全局右移操作。
那么这个上面是我们脑内模拟了一下这个过程，得出来的计数结论，我们实现一下，看看对不对？
哈哈，我们会发现，这样子操作，得出来的答案不对，这是为什么呢？。
以这个第一个样例的第一个询问为例，我们会发现，其实这个答案并不在乎顺序。
那我们的计算要怎么样搞？其实，我们发现我们上面的思路还是比较混乱的，即有的时候认为是组合，有的时候又认为是排列。
不过，我们发现，题目中的 是非常重要的，这意味着，只要是为了这个相等作用，无论
⚠️ 注意：我们从高到低遍历，我们要遍历到 -1（就是代表这些驼鹿的运载能力归零了），因此，我们会给整个系统加一个偏移量。
- Case 1：（MSB 即查询数字 x 最大二进制位的位数）
- 如果 ，那么好办，直接 即可。
- 如果 ，还好办吗？这里需要有这么一个想法，就是把 和这个前面这部分分开来看，即：
这个式子这样子理解，首先，这个数组 C 是倒序排序的，即 $c'_i\ge c'_{i+1}$，因此，选了排在第一个的数，就有 $2^{rem+freq_{i}-1}$ 种组合（全组合的这个公式），选了排在第二个的数，就只有 $2^{rem+freq_{i}-2}$ 种组合了（没法选第一个数），一次类推，就得到了这个式子。之后，我们就当 i 这个数字不存在就行了。
