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\)，那么：

考虑最坏的情况，区间内的 \(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\)，此做法的时间复杂度不变，而空间复杂度变为线性。

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