题意简述

有一个人在写树状数组题，模$2$意义。

题目需要支持单点加，求区间和。

写的时候把所有$x$的变化方向都写反了。

现在你需要执行两种操作：

1 l r : 在$[l, r]$中等概率随机一点$x$执行单点加。

2 l r : 询问在此时调用错误的代码求答案有多大的概率出错。

输出概率时要求对$998244353$取模。

$1 \le n, m \le 10 ^ 5, 1 \le l \le r \le n$

算法讨论

补题时发现真是清真题，可能亏了一个亿啊？？

不过反正我考场上也没时间写，还是自己太菜啊。

首先找一发规律可以知道错误写法求出来的就是后缀和。

由于这里是模$2$意义，那么加法就等价于异或操作。

假设原来调用$sum(x)$操作求出来的答案是$s_x$，区间$[l, r]$的答案是$s_r \oplus s_{l-1}$。

现在错误的$sum(x)$求出来的就是$s_x \oplus A_x \oplus T$，区间$[l, r]$的答案就是$s_r \oplus s_{l-1} \oplus A_{l-1} \oplus A_r$，注意这个结论在$l \neq 1$才成立，$l = 1$时求出来的是$s_r \oplus s_{l-1} \oplus A_r \oplus T$，其中$T$是现在所有$A_i$的异或和，即当前1操作的总数的奇偶性。

所以我们现在就知道了，原答案和新答案的异或在$l = 1$时是$T \oplus A_r$，在$l \neq 1$时是$A_{l-1} \oplus A_r$。这样就可以把问题规模降成单点，暴力DP就是$O(q ^ 2)$啦。

我们发现DP的过程满足结合律和交换律，而且和询问有关的量只有询问点和修改点的关系，分别对应了四种转移。而且我们发现四种转移的范围分别是一个矩形。于是修改时我们就在二维线段树直接打标记，查询时就是一个清真的单点查询啦。

时间复杂度$O(m \log ^ 2 n)$。