sqrt technology, sqrt faith.
定义一个数为幸运数字，当且仅当其十进制数位中仅有 \(4\) 和 \(7\) 组成。
给出长度为 \(n\) 的序列 \(p_1\sim p_n\)，有 \(q\) 次操作，分为两种类型：
\(\texttt{add }l\texttt{ }r\texttt{ }x\)，将 \(p_l\sim p_r\) 加上 \(x\)。
\(\texttt{count }l\texttt{ }r\)，查询当前 \(p_l\sim p_r\) 中有多少个幸运数字。
\(n,q\le 10^5\)。设 \(V\) 为序列 \(p\) 的值域，保证任意时刻 \(\boldsymbol{|V|\le 10^4}\)。
\(4.00\,\text{ms}\,/\,250.00\,\text{MB}\)。
tags：
-
\(\text{data structures}\)
-
\(\color{red}*2400\)
首先，任意时刻 \(|V|\le 10^4\) 意味着整个问题只会涉及四位及以下的幸运数字。
考虑计算每一位的幸运数字有多少个，每位可以选 \(4\) 或 \(7\)，可以计算出这个范围内的幸运数字总数 \(k=2+2^2+2^3+2^4=30\)。
发现 \(k\) 很小，肯定有用，考虑先把所有幸运数字存放到一个容器里。因为叫“幸运数字”，所以代码中存放的容器名称使用了 maze 的名字首拼缩写。
考虑序列分块，设块长为 \(B\)。记 \(i\) 所在块为 \(bel_i\)，第 \(i\) 块的范围为 \([bl_i,br_i]\)。
对于每个块，维护加标记 \(tag_i\)。再维护一个数组 \(a_i\)，其值为使得 \(\boldsymbol{x+tag_{bel_i}}\) 等于当前 \(\boldsymbol{p_i}\) 的数 \(\boldsymbol{x}\)。简单来说就是任意时刻 \(a_i+tag_{bel_i}=p_i\)。对于整块再维护桶 \(cnt_{i,j}\) 表示块 \(i\) 内有多少个位置的 \(\boldsymbol{a}\) 值为 \(j\) 。
修改的时候整块标记修改，散块 \(a\) 数组修改，维护好 \(a_i+tag_{bel_i}=p_i\)。
查询的时候，散块暴力遍历判断每个位置的真实值是否是幸运数字。整块则枚举 \(k\) 个幸运数字 \(y\)，若当前块 \(i\) 内有一个位置 \(j\) 满足 \(p_j=y\)，则 \(a_j=y-tag_i\)。即查询块内有多少个位置的 \(a\) 值等于 \(y-tag_i\)，贡献为 \(cnt_{i,y-tag_i}\)。
接下来分析时间复杂度。因为空间复杂度显然为 \(\mathcal{O}\left(n+\dfrac{n|V|}{B}\right)\)。
单次修改：
整块 \(\mathcal{O}\left(\dfrac{n}{B}\right)\) 个，单个修改的时间复杂度为 \(\mathcal{O}(1)\)；散块 \(\mathcal{O}(1)\) 个，单个修改的时间复杂度为 \(\mathcal{O}(B)\)。总时间复杂度为 \(\mathcal{O}\left(\dfrac{n}{B}+B\right)\)。
单次查询：
整块 \(\mathcal{O}\left(\dfrac{n}{B}\right)\) 个，单个查询的时间复杂度为 \(\mathcal{O}(k)\)；散块 \(\mathcal{O}(1)\) 个，单个查询的时间复杂度为 \(\mathcal{O}(B)\)。总时间复杂度为 \(\mathcal{O}\left(\dfrac{nk}{B}+B\right)\)。
综上，该算法的时间复杂度为 \(\mathcal{O}\left(n+q\left( \dfrac{nk}{B}+B \right)\right)\)。
取 \(B=\mathcal{O}\left(\sqrt{nk}\right)\) 时，时间复杂度为 \(\mathcal{O}\left(n+q\sqrt{nk}\right)\)，空间复杂度为 \(\mathcal{O}\left(n+|V|\cdot \sqrt{\dfrac{n}{k}}\right)\)。可以接受。
提交记录（\(\color{limegreen}\bf{Accepted}\) \(\boldsymbol{780\, \text{ms}\,/\,3.46\,\text{MB}}\)，含代码）
标签：right,dfrac,CF121E,Lucky,tag,mathcal,Array,复杂度,left From： https://www.cnblogs.com/MnZnOIerLzy/p/17829247.html