Java教程

2022.5 杂题

本文主要是介绍2022.5 杂题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

P5608 [Ynoi2013] 文化课

用线段树维护。对于区间修改符号的操作,记录区间的数字之和以及数字积即可。对于区间修改数字的操作,发现修改后的值无法快速求出来,考虑在每个线段树的节点 \(p\) 上,记录二元组的集合 \(S_p=\{(c_i,d_i)\mid 1\le i\le len_p\}\),表示长为 \(c_i\) 的极长乘法连续段有 \(d_i\) 个。那么,当一个区间要整体赋值为 \(k\) 时,新的答案就是 \(\sum_{i=1}^{len_p} d_i\times k^{c_i}\)。在这里如果直接快速幂会多出一个 \(\log\),但如果按照 \(c_i\) 从小到大的顺序处理,每次在上一次的基础上进行快速幂,可以证明这样是不会多 \(\log\) 的。

对于 pushup 操作,直接归并两个子节点的 \(S\),假如子结点间的符号是 \(\times\),那么还需要去掉左右两个乘法区间,加入一个新的乘法区间。

考虑这种做法的时间复杂度:对于线段树上的节点 \(p\),设它的左、右端点是 \(l_p,r_p\),长度 \(L_p=r_p-l_p+1\),那么:

\[\sum_{i=1}^{len_p} c_i\le \sum_{i=1}^{len_p} c_id_i=L_p \]

考虑最坏的情况,区间内的 \(c_i=i,d_i=1\),此时 \(len_p\approx 2\sqrt{L_p}\)。

所以这里有一个自然根号:\(len_p=\mathcal{O}(\sqrt{L_p})\)。所以数据和数据的合并、标记和数据的合并的时间复杂度都是 \(\mathcal{O}(\sqrt{L_p})\) 的。因为线段树在最坏情况下,会操作 \(\log n\) 个节点,它们的长度分别是 \(n,\frac{n}{2},\frac{n}{4},\dots,1\),所以单次操作的总复杂度是 \(\sqrt{n}+\sqrt{\frac{n}{2}}+\sqrt{\frac{n}{4}}+\dots+\sqrt{1}=\mathcal{O}(\sqrt{n})\)。

代码写起来比较繁琐。

P7447 [Ynoi2007] rgxsxrs

考虑倍增地分块,设定一个常数 \(B\),值在 \([B^k,B^{k+1})\) 间的所有元素分在同一个块中。每块开一棵序列上的线段树,记录区间最小值、最大值、区间和以及区间内在这棵线段树上的元素个数。当我们要对序列上的一段区间减一个数 \(x\) 时,枚举每棵线段树,对于线段树上的一段区间,设它的最大值、最小值分别为 \(R,L\),有三种情况:

  1. 区间最大值 \(\le x\),此时区间内没有数会被操作;
  2. 区间完全被修改区间包含,且 \(L-x\ge B^k\),此时直接打标记;
  3. 否则,说明区间中存在一些元素,它们减 \(x\) 以后掉落到了下面的某个块中。此时递归到两侧。

考虑这种做法的时间复杂度:假设 \(n,m\) 同阶,显然每个数至多跌落 \(\log_B V\) 次,这部分是 \(\mathcal{O}(n\log n\log_B V)\);直接打标记的部分是 \(\mathcal{O}(n\log n\log_B V)\);每次操作中,对于满足 \(B^k\le x<B^{k+1}\) 的那个块,最坏情况下需要遍历每个数,而这种情况不超过 \(B\) 次(因为减了 \(B\) 个 \(x\) 以后就全部跌落到其它块中了),所以这部分是 \(\mathcal{O}(n\log_B V(\log n+B))\)。再算上计算数字所在块的时间复杂度,总的是 \(\mathcal{O}(n\log_B V(B+\log n)\log\log_B V)\),其中 \(\log\log_B V\) 几乎可以忽略不计;空间是 \(\mathcal{O}(n\log_B V)\)。

但空间限制是 64MB,上面的方法显然超了。一种办法是线段树底层分块(另一种是压缩 Trie,不过我不会),设定阈值 \(B'\),当线段树的 \(r-l+1\le B'\) 时便不再向下递归,直接暴力。假如令 \(B\sim \log n,B'\sim \log_B V\),此做法的时间复杂度不变,而空间复杂度变为线性。

底层分块巨大难写。代码。

这篇关于2022.5 杂题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!