一、题意理解

我们初始有 $1$ 棵线段树（编号 $1$），所有节点标记 $tag = 0$。

两种操作：

1. 修改操作 $1\ l\ r$：

   • 把当前 $t$ 棵线段树每棵复制成两棵（新编号规则：原树 $i$ 变成 $2i-1$ 与 $2i$），于是树的数量 $t \to 2t$。
   • 然后对所有编号为奇数的树执行一次 $Modify(root, 1, n, l, r)$，即对区间 $[l, r]$ 打上懒标记（标记永久化，不下传，且标记为 $1$ 后不会再变回 $0$）。

2. 查询操作 $2$：

   • 定义一棵树的权值 = 该树中 $tag=1$ 的节点个数。
   • 求当前所有树的权值之和。

---

二、关键观察

设当前有 $t$ 棵树，执行一次 $1\ l\ r$：

• 复制前，每棵树 $i$ 的权值为 $w_i$。
• 复制后，树 $2i-1$ 和 $2i$ 初始权值都是 $w_i$。
• 然后对奇数编号的树（$2i-1$）进行一次 $Modify(l, r)$，这次修改会给该树新增一些标记为 $1$ 的节点（这些节点之前 $tag=0$，现在变 $1$）。

设一次 $Modify(l, r)$ 操作在一棵全新空树（全 $0$ 标记）上执行后，新增的 $tag=1$ 的节点数为 $X$（注意 $X$ 只与 $[l, r]$ 和线段树结构有关，与之前标记无关，因为标记永久化，已经为 $1$ 的节点不会再新增）。

但是，如果树上某些节点之前已经是 $1$，那么这次修改不会重复计数。所以实际新增的节点数 = 在这次修改中被覆盖且原来 $tag=0$ 的节点的数量。

---

三、数学建模

设 $f_{node}$ 表示在所有树中，节点 $node$ 的 $tag=1$ 的树的数量。

初始 $f_{node} = 0$ 对所有节点。

当进行 $1\ l\ r$ 时：

1. 首先 $t \to 2t$，并且对于任意节点，原来有 $f_{node}$ 棵树该节点为 $1$，复制后，$f_{node} \to 2 f_{node}$（因为每棵树复制成两棵，标记继承）。

2. 然后对奇数编号的树（恰好一半的树）进行 $Modify(l, r)$。
   对于在 $Modify(l, r)$ 中会被标记的节点 $node$（即该节点对应的区间 $[L, R] \subseteq [l, r]$），在这次修改前，这些奇数树中该节点 $tag=0$ 的数量 = 奇数树总数 $t$（因为复制后树总数为 $2t$，奇数树有 $t$ 棵）减去该节点在奇数树中已经是 $1$ 的数量。
   注意奇数树中该节点为 $1$ 的数量 = 总 $f_{node}$ 的一半（因为复制时均匀分配），即 $\frac{f_{node}}{2}$。

   所以新增的 $1$ 的数量 = $t - \frac{f_{node}}{2}$。

   因此 $f_{node} \gets 2 f_{node} + \left(t - \frac{f_{node}}{2}\right)$。

   化简：

   $$f_{node} \gets \frac{3}{2} f_{node} + t$$

   对于被 $[l, r]$ 完全覆盖的节点。

3. 对于不被 $[l, r]$ 完全覆盖的节点，$f_{node}$ 只是复制加倍：$f_{node} \gets 2 f_{node}$。

---

四、线段树维护

我们可以在值域 $[1, n]$ 的线段树（用于模拟题中的线段树结构）上维护每个节点（指值域线段树的节点）的 $f_{node}$。

每次 $1\ l\ r$：

1. 总树数量 $t \gets 2t$（模 $998244353$）。
2. 对值域线段树进行区间更新：
   对完全包含在 $[l, r]$ 的节点 $x$，执行：$$f_x \gets \frac{3}{2} f_x + t$$ 对不被 $[l, r]$ 完全包含但与之相交的节点，需要递归，并标记懒标记。

注意 $\frac{1}{2}$ 在模 $998244353$ 下是 $inv(2) = (998244353+1)/2$。

---

五、查询操作

查询时，答案 = $\sum_{\text{所有节点}} f_{node}$（因为每棵树该节点为 $1$ 就贡献 $1$，总贡献就是 $f_{node}$）。

所以我们只需维护值域线段树的所有 $f_{node}$ 之和 $S$，查询时输出 $S$。

---

六、递推公式总结

设 $S$ = 当前所有树的权值和（即答案）。

设 $t$ = 当前树的数量。

初始：

$$t = 1,\quad S = 0$$

操作 $1\ l\ r$：

1. 复制树：

$$t' = 2t,\quad S' = 2S$$

因为每棵树权值复制成两份。

2. 对奇数树进行 $Modify(l, r)$：

   设 $A$ = 一次 $Modify(l, r)$ 在一棵全 $0$ 标记树上新增的 $1$ 的节点数（即该操作覆盖的节点数）。

   注意 $A$ 是固定的，只与 $[l, r]$ 有关，可以在值域线段树上 $O(\log n)$ 计算。

   在奇数树中，某个节点如果原本是 $0$ 且被本次覆盖，才会新增 $1$。
   考虑某个节点 $u$，在所有树中它为 $1$ 的比例是 $p = f_u / (2t)$（复制后、修改前）。
   在奇数树中它为 $1$ 的比例也是 $p$（因为复制均匀）。
   所以奇数树中该节点为 $0$ 的比例是 $1-p$，奇数树总数是 $t$，所以新增数 = $t(1-p)$。

   对所有被覆盖的节点求和：

   $$\Delta = \sum_{u \in \text{cover}} t\left(1 - \frac{f_u}{2t}\right) $$

   即

   $$\Delta = t\cdot |\text{cover}| - \frac12 \sum_{u \in \text{cover}} f_u $$

   其中 $|\text{cover}| = A$。

   所以：

   $$S'' = S' + \Delta = 2S + tA - \frac12 \sum_{u \in \text{cover}} f_u $$

3. 更新 $f_u$ 对于被覆盖的节点：

   $$f_u' = 2f_u + \left(t - \frac{f_u}{2}\right) = \frac{3}{2}f_u + t $$

   对 $u \in \text{cover}$。

---

七、实现方法

我们建一棵值域线段树，维护：

• $sumf$: 区间内 $f_u$ 之和。
• $sumfCov$: 区间内被覆盖节点的 $f_u$ 之和（用于计算 $\Delta$）。
• 标记 $(mul, add)$ 表示 $f \gets mul\cdot f + add$。

操作 $1\ l\ r$：

1. $t \gets 2t$。
2. $S \gets 2S$。
3. 计算 $A$ = 覆盖的节点数（在递归时统计）。
4. 递归更新区间 $[l, r]$：
   • 对完全包含在 $[l, r]$ 的节点，打标记 $(3/2, t)$，并记录它们的 $sumf$ 到 $sumfCov$。
   • 对部分包含的，递归下去。
5. $\Delta = t\cdot A - \frac12 \cdot sumfCov$。
6. $S \gets S + \Delta$。

查询 $2$：输出 $S$。

---

八、复杂度

每次 $O(\log n)$，总 $O(m\log n)$。

---

九、示例推导（对应样例）

初始 $t=1, S=0$。

第一次查询：输出 $0$。

操作 $1\ 1\ 3$：

• $t=2$。
• $S=0$。
• $A$ = 覆盖节点数：$[1,3]$ 对应节点 $[1,3]$（可能拆成 $[1,2]$ 和 $[3,3]$ 等，根据线段树结构），假设标准线段树 $[1,5]$ 结构： 根 $[1,5]$ 不包含在 $[1,3]$，递归： 左 $[1,3]$ 包含，右 $[4,5]$ 不交。 左 $[1,3]$ 不完全是叶子，递归： $[1,2]$ 包含，$[3,3]$ 包含。 所以覆盖节点：$[1,2]$, $[3,3]$, $[1,3]$ 三个节点。 所以 $A=3$。
• 初始 $f_u=0$ 对所有节点，所以 $sumfCov=0$。
• $\Delta = 2\cdot 3 - 0.5\cdot 0 = 6$。
• $S = 0 + 6$？不对，这里要小心：我们是在复制后 $S'=2S=0$ 基础上加 $\Delta$，所以 $S=6$？但样例第二次查询输出 $1$，说明我直接这样算不对。

实际上样例中第一次 $1\ 1\ 3$ 后，只有一棵树（编号1）被修改，因为初始 $t=1$，复制成两棵（编号1和2），只改编号1的树。
编号1的树在 $[1,3]$ 上标记了 $1$ 个节点（因为标准线段树 $[1,5]$ 的结构中，$[1,3]$ 区间本身就是一个节点，不会下到 $[1,2]$ 和 $[3,3]$ 去标记，这是标记永久化的特点：在第一个完全包含的节点打标记，不再递归）。

所以 $A=1$（只有节点 $[1,3]$ 被打标记）。
初始 $f_{[1,3]}=0$，$sumfCov=0$，$t=1$（注意复制前 $t=1$，复制后 $t=2$，但修改的奇数树数量是 $t_{\text{old}}=1$？这里要仔细）。

---

为了符合样例，我们修正模型：

设 $t$ = 操作前的树的数量。

操作 $1\ l\ r$：

1. 复制后树数 $t' = 2t$。
2. 奇数树数量 = $t$。
3. 对每个覆盖的节点 $u$，新增 $1$ 的数量 = 奇数树中该节点为 $0$ 的数量 = $t - f_u$（因为 $f_u$ 是操作前该节点为 $1$ 的树的数量，这些树在复制后变成 $2f_u$ 棵树该节点为 $1$，均匀分布在奇偶中，所以奇数树中该节点为 $1$ 的数量 = $f_u$）。

所以 $\Delta = \sum_{u \in cover} (t - f_u)$。

更新 $f_u$：复制后 $f_u' = 2f_u$，然后奇数树中该节点为 $0$ 的 $t - f_u$ 个变为 $1$，所以：

$$f_u' = 2f_u + (t - f_u) = f_u + t$$

那么 $S' = 2S + \Delta$。

---

用这个模型验证样例：

初始 $t=1, S=0, f_u=0$。

第一次查询：输出 $0$。

操作 $1\ 1\ 3$：

• $t=1$（操作前）。
• $A=1$（节点 $[1,3]$）。
• $\Delta = (1 - 0) = 1$。
• $S' = 2\cdot 0 + 1 = 1$。
• $f_{[1,3]} = 0 + 1 = 1$。
• $t \gets 2$（操作后）。

第二次查询：输出 $1$，符合。

操作 $1\ 3\ 5$：

• $t=2$（操作前）。

• $A$：节点 $[3,5]$？不，线段树 $[1,5]$ 结构： 根 $[1,5]$ 不包含 $[3,5]$，递归： 左 $[1,3]$ 不包含，相交，递归？其实 $[3,5]$ 会覆盖节点 $[3,3]$, $[4,5]$, $[3,5]$？
  实际标记永久化：$[3,5]$ 与 $[1,5]$ 不包含，递归左右： 左 $[1,3]$ 与 $[3,5]$ 相交，递归： $[1,2]$ 不交，$[3,3]$ 包含。 右 $[4,5]$ 包含。 所以覆盖节点：$[3,3]$, $[4,5]$, $[3,5]$？不对，$[3,5]$ 不是节点，因为 $[1,5]$ 不包含 $[3,5]$，所以不会标记 $[3,5]$，只会标记 $[3,3]$ 和 $[4,5]$ 两个节点。
  所以 $A=2$。

• 计算 $\Delta$： 对 $[3,3]$：$f=0$，贡献 $t - f = 2 - 0 = 2$。 对 $[4,5]$：$f=0$，贡献 $2$。 总 $\Delta = 4$。

• $S' = 2\cdot 1 + 4 = 6$。

• 更新 $f$： $f_{[3,3]} = 0 + 2 = 2$， $f_{[4,5]} = 0 + 2 = 2$。

• $t \gets 4$。

第三次查询：输出 $6$，符合。

---

十、最终公式

操作 $1\ l\ r$（当前 $t, S, f_u$）：

1. 计算覆盖的节点集合 $C$ 和 $A = |C|$。
2. $\Delta = \sum_{u \in C} (t - f_u) = t\cdot A - \sum_{u \in C} f_u$。
3. $S' = 2S + \Delta$。
4. 对每个 $u \in C$：$f_u \gets f_u + t$。
5. $t \gets 2t$。

查询 $2$：输出 $S$。