Codeforce 1217E – Sum Queries

题目链接:Codeforce 1217E

首先我们考虑一个Balanced Multiset总和的每个位置可能存在两种情况:

  • 总和$s_i$就是这个集合内某个数字$x$的第$i$位,除了$x$之外的其余数字的第$i$位均为$0$
  • 总和$s_i$就是这个集合内某个数字$x$的第$i$位,但是不满足除了$x$之外的其余数字的第$i$位均为$0$,所以$\sum x_i \bmod 10 = s_i$,这种情况下一定会产生进位

经过分析可以知道第二种情况是不可能的,我们可以这样反证:如果第$i$位置是这种情况,第$i+1$位是会接受到第$i$位的进位,那么第$i+1$位就不可能是第一种情况,即第$i+1$位会产生进位,以此类推,最前面一位也会产生进位,假设这个进位的位置为$p$,这显然是不符合定义的,因为原集合当中$p$位置都是$0$,故不可能成立。

因此我们可以得到一个推论,任何一个Unbalanced Multiset,无论怎么添加元素,这个集合依旧是Unbalanced。那么我们要找一个和最小的Unbalanced Multiset,其实也就是找一个两个元素的集合,使得这两个元素不满足上述的第一类情况。简而言之,对于每个询问,我们需要找到一组$(a_i,a_j)$,满足$l \leq i < j \leq r$,使得第一类Balanced条件被破坏,最小的$a_i+a_j$就是问题的答案。

考虑用线段树维护区间的一些信息。我们可以把一个十进制数按位置拆分,对于要维护的区间用一个长度为$\lceil \log_{10} \max\{ a_i \} \rceil$的数组来记录区间内的数中,那些不为$0$的位置被哪些数使用,这些数的最小值是多少。接着还需要一个变量来维护区间最小的$a_i+a_j$。在Push-Up操作的时候,第一个数组很好维护,我们考虑如何维护第二个量,这里记录为$f_o$,首先$f \leq \min \{ f_l, f_r \}$,$f_o$、$f_l$和$f_r$分别是线段树当前的根、左子树和右子树维护的$a_i+a_j$的值,这意味着在左半个区间选择两个或者在右半个区间选择两个,当然我们也可以在左区间选择一个,右区间选择一个,这个时候就要用我们维护的第一个量来更新第二个量,详见代码。

渐进时间复杂度$O((n+m)\log n \times \lceil \log_{10} \max\{ a_i \} \rceil)$。

 

说点什么

avatar
50
  Subscribe  
提醒