线段树

CodeForces Round #502 Problem G – The Tree

这是lty数据结构专题里唯二自己做出来的题目中的一道。

如果不包含“将 $x$ 的子树全部染白”的操作，应当怎样处理？

题目所给操作可以这样转述：令 $x$ 为本次染色操作的节点。若 $x$ 为白色，则立刻染黑并退出；否则我们找到其子树中的，与 $x$ 相连的黑色连通块，则对于每个连通块底部节点，若其不是叶子节点，我们将其儿子染黑。

由于本题的树没有特殊性质，且将来加入回退操作，故而难以维护整个连通块以及其叶子节点。因此，我们可以从“在何种情况下，节点 $x$ 被染黑”的方向考虑。

显然，只有从在 $x$ 到根的路径上的节点开始的染色操作，才可能波及到 $x$。假如最终 $x$ 被染黑的一瞬，它被包含在了以 $\text{comprt}$ 为根的连通块中。令链 $\langle\text{comprt}, x\rangle$ 为 $\left\{x_1,x_2,\dots,x_n \right\},x_1=\text{comprt},x_n=x$，那么自然想到，一种一定合法的染色序列是 $\{y_1,y_2,\cdots,y_n\}$，其中有 $\forall k \in [1, n] \cap \mathbb{Z},y_k \in \{x_1,\cdots,x_k\}$，也即我们每一步都在该连通块内部，并将连通块的最大深度推进一层。

这种序列确实合法（它是充分条件），但这真的是 $x$ 被染黑的必要条件么？ （更多…）

一道让我做得相当高兴的题目。

原题链接 （这是付费比赛。）

题意简述

给定长度为 $n$ 的序列 $a$。定义函数 $f(S)=\sum\limits_{T\subseteq S} F^2(\sum_{s\in T} s)$，也即“对于 $S$ 的所有子集，求 $F(\text{子集所有元素之和})\text{的平方}$ 之和”。其中 $F(x)$ 为斐波那契数列的第 $x$ 项。有$F(0)=0, F(1)=1, F(x)=F(x-1)+F(x-2) (x > 1)$。

你需要支持以下操作，操作总数为 $m$：

1 x y：将 $a_x$ 修改为 $y$；

2 l r：输出 $\sum\limits_{i=l}^{r}\sum\limits_{j=i}^{r}f(\{a_i, a_{i+1}, \cdots, a_{j}\})$，对 $998244353$ 取模。

数据范围：对于 $\text{50\%}$ 的数据，有 $n,m\leq 100$；对于 $\text{70\%}$ 的数据，有 $n,m\leq 1000$；对于 $\text{100\%}$ 的数据，有 $n,m\leq 10^5, a_i \leq 10^5$。

（更多…）