P14973 『GTOI - 2D』木棍

木棍 + 木棍 = 木棍。

对于一个 $01$ 串 $S$，定义 $f(S)$ 为：删除 $S$ 中所有的 `01` 子串，重复若干次直到 $S$ 中不含有 `01` 子串，此时剩下的字符串即为 $f(S)$。可以证明删除顺序不影响最终结果。 定义价值函数 $V(S)=\sum\limits_T [|S|=|T|][f(S)=f(T)]$。 给定长度为 $n$ 的 $01$ 串 $S$，需要支持以下两种操作： - `1 l r` 对于 $S$ 中第 $l$ 个字符到第 $r$ 个字符中的每一个字符，若其是 $0$ 则修改为 $1$，否则修改为 $0$。 - `2 l r` 对于 $S$ 中第 $l$ 个字符到第 $r$ 个字符所组成的子串 $T$，求 $V(T)\bmod 998244353$。

第一行一个正整数 $n$，表示 $S$ 的长度。 第二行 $n$ 个字符，表示 $01$ 串 $s$。 第三行一个正整数 $q$，表示操作次数。 接下来 $q$ 行，每行三个正整数 $op,l,r$，表示操作类型和参数。

对于每个操作 $2$，输出 $V(T)\bmod 998244353$。

**【数据范围】** **本题采用捆绑测试。** 对于 $100\%$ 的数据，保证 $1\le n,q\le 5\times 10^5,op\in\{1,2\},1\le l\le r\le n$。 |$\text{Subtask}$|$n\le$ |$q\le$ |特殊性质|分值 | |:---:|:--------:|:--------:|:--:|:--:| |$1$ |$20$ |$20$ |无 |$5$ | |$2$ |$500$ |$1$ |有|$15$| |$3$ |$5000$ |^ |^ |$15$| |$4$ |$5\times 10^5$|^ |^ |$25$| |$5$ |$5000$ |$5000$ |无 |$10$| |$6$ |$10^5$ |$10^5$ |^ |$10$| |$7$ |$5\times 10^5$|$5\times 10^5$|^ |$20$| 特殊性质：保证存在一次操作 $2$ 满足 $l=1,r=n$。