2022牛客寒假算法基础集训营5 E.复苏小孩 详解

题目描述

获得鬼手后，九峰成功让鬼眼，无头鬼影，鬼手三者形成了奇妙的平衡，短时间内不用担心厉鬼复苏，且可以使用厉鬼的力量。

但想要让三者保持平衡，必须按照一定的规律轮流使用各部分的力量，于是九峰向神秘的人皮纸询问得到了以下结果：“我叫九峰，当你看到这句话的时候我已经…虽然目前三个鬼暂时形成了平衡，但这样下去我仍然撑不过几个月，我需要按照一定的顺序分别使用它们的力量才可以存活，经历无数次推算，我终于找到了这个顺序：（一个仅包含数字123的字符串）”，众所周知人皮纸会把正确的信息显示出来，但也有可能对这个字符串增删改查了一些字符使得其变错，还好九峰还有与鬼橱交易的一些机会，但鬼橱告诉九峰它最多只能对一串字符串进行正确性的判定并只能提供少量纠错，具体规则如下：

九峰每使用其中一个鬼的能力，这个鬼就会吸收其他两个鬼各一半的力量，九峰给鬼橱一个字符串后鬼橱会返回一个三元一次方程，假设一开始三种鬼的能力值为1，按照这个字符串顺序使用对应鬼的能力后，将三种鬼的力量值膜998244353意义下的数字代入这个方程，等式成立则表示该字符串为正确的，鬼橱中途可能返回一些需要修改的地方给九峰。

这个过程听起来很简单，但九峰由于高三还没毕业就被卷进了灵异事件，没有很好的数学功底，他希望你帮他完成需要的修改，并算出每次和鬼橱交易需要代入方程的三个数字。

输入

第一行两个整数 n , m ( 1 ≤ n , m ≤ 1 e 5 ) n,m(1\leq n,m\leq 1e5) n,m(1≤n,m≤1e5)表示人皮纸给出的字符串长度和与鬼橱交易的次数

第二行一个长度为 n n n的字符串 S S S，表示人皮纸的答案，字符串中的字符仅包含’1’,‘2’,‘3’,分别表示使用鬼眼，鬼影和鬼手的能力

接下来 m m m行每行三个整数，表示一次操作，格式如下：

1 x y:表示修改字符串的第 x x x位修改成数字 y y y. ( 1 ≤ x ≤ n , 1 ≤ y ≤ 3 ) (1\leq x \leq n, 1\leq y \leq 3) (1≤x≤n,1≤y≤3)

2 l r:查询l,r这段字符串 ( 1 ≤ l ≤ r ≤ n ) (1\leq l \leq r \leq n) (1≤l≤r≤n)

输出

对于每次 2 2 2操作输出一行三个整数，表示按这个字符串使用厉鬼的能力后，鬼眼鬼影鬼手的能力值，对 998244353 998244353 998244353取模

样例输入

3 3
123
2 1 3
1 1 3
2 1 3

样例输出

499122177 124780545 374341634 
873463809 124780545 2

样例解释

第一组查询中三种力量的变化过程为(1,1,1)->(2,1/2,1/2)->(1,7/4,1/4)->(1/2,7/8,13/8)

思路

题面确实很生草，但是关键信息还是描述清楚了的：“每使用其中一个鬼的能力，这个鬼就会吸收其他两个鬼各一半的力量”。然后结合样例的解释理解，我们可将操作序列串的操作描述如下：

按照给定操作串的顺序，每次选择一个鬼 i , i ∈ 1 , 2 , 3 i, i \in {1, 2, 3} i,i∈1,2,3，假设该鬼的力量为 x x x，由于三个鬼的总能量= 3 3 3守恒，那么该鬼吸收能量后由 x x x变为 x + x − 3 2 = x 2 + 3 2 x + \frac{x - 3}{2} = \frac x2 + \frac 32 x+2x−3​=2x​+23​。

如果当前鬼没有被选择，那么就会被吸收能量，那么就会由 x x x变为 x 2 \frac x2 2x​。

所以对于一个鬼，有两种操作：

• 吸收能量： x → x 2 + 3 2 x \rightarrow \frac x2 + \frac 32 x→2x​+23​
• 被吸能量： x → x 2 x \rightarrow \frac x2 x→2x​

我们对一个鬼分析，对于一段操作序列，我们可以将以上的两个操作合并维护，首先公共部分是 x 2 \frac x2 2x​，吸取能量会带来 3 2 \frac 32 23​的增益(由于这个增益是单独加的，我们可以把他剥离出来单独算)，如果加上从左到右的操作顺序，我们不难发现实际上可以将一段序列看作一个 1 2 \frac 12 21​进制数，从高位到低位(对应串的 [ l , r ] [l,r] [l,r]区间)位权分别为 ( 1 2 ) r − l + 1 , ( 1 2 ) r − l , … ( 1 2 ) 1 (\frac 12)^{r - l + 1}, (\frac 12)^{r - l}, \dots (\frac 12)^1 (21​)r−l+1,(21​)r−l,…(21​)1。

那么我们可以对三个人分别建立线段树，用三棵线段树分别维护三个人 3 2 \frac 32 23​的区间和和单点修改。然后单独计算区间 x 2 \frac x2 2x​加和即可。

Accepted Code

#include 
#define int long long
using namespace std;

const int N = 2e5 + 10, MOD = 998244353;
int tree[4][N