#P8. 【USTCPC2024】F. 楼高统计
【USTCPC2024】F. 楼高统计
小仓鼠李华去的小学是一所发展飞快的学校。学校有 个路口与 条连接两个路口的道路,且每两个路口之间都可以通过道路直接或间接到达。每个路口都建有一栋楼,第 个路口的楼高为 。李华经常会从其中一个路口走到另一个路口,在走的过程中,它会记录下所能看到的每栋楼的高度,且不会重复记录同一栋楼。
当李华走到路口 时,它能看到 以及所有与 相邻路口(即通过一条路直接连接的路口)的楼。李华对校园很熟悉,所以不会绕路,也就是说,对于每一对路口 ,它从 到 的路线都是唯一的。每次李华结束行程后,它都想知道记下来的所有楼高度的均值和方差。
提示: 个数 的均值和方差为:
$$E(a) = 1/k \sum_{i=1}^k a_i\\ \text{Var}(a) = 1/k \sum_{i = 1}^k (a_i - E(a))^2 $$另外,学校也在发展,包括以下两类事件:
- 取一对点 ,将 到 的路径上(包含端点)所有的楼进行加盖操作,其高度均增加 ;
- 取一对点 ,将 到 的路径上(包含端点)所有高度超过 的楼进行降沉操作,通过挖地将低楼层降沉至地下,使楼高减小至 。
现在给定学校发展和李华行程发生的顺序,请你求出每次行程记录的楼的均值和方差。李华非常讨厌小数,所以请将答案对 998244353 取模。具体来说,若答案可以表示为 ,请输出 对 998244353 取模的值,其中 。
Input
输入第一行:两个整数 (),表示学校的路口个数,以及发生的事件数量。
第二行: 个整数 (),表示初始时每栋楼的高度。
接下来 行:每行两个整数 (),表示每条道路。
接下来 行:每行描述一个事件(),格式如下:
- 1 :第 类学校发展事件,;
- 2 :第 类学校发展事件,;
- 3 :李华行程事件,从 走到 。
Output
输出若干行:对于每次行程,输出李华希望得到的均值和方差,对 998244353 取模。
Examples
Sample Input 1
7 5
1 2 3 4 5 6 7
1 2
1 3
2 4
2 5
3 6
3 7
3 1 7
1 3 6 5
3 4 7
2 4 5 1
3 1 4
Sample Output 1
399297745 878455036
570425350 40744678
199648873 718735942
样例中,学校地图如下:
初始时各楼高度分别为 1 2 3 4 5 6 7,李华从路口 1 走到路口 7,经过的路口为 1 3 7,看到的楼的编号为 1 2 3 6 7,高度分别为 1 2 3 6 7,均值为 ,方差为 。
学校第一次发展,路口 3 到路口 6 的路径上所有的楼高增加 5,各楼高度变成 1 2 8 4 5 11 7,李华从路口 4 走到路口 7,经过的路口为 4 2 1 3 7,能看到所有的楼,均值为 ,方差为 。
学校第二次发展,路口 4 到路口 5 的路径上所有高度超过 1 的楼进行降沉操作,各楼高度变成 1 1 8 1 1 11 7,李华从路口 1 走到路口 4,经过的路口为 1 2 4,看到的楼的编号为 1 2 3 4 5,高度分别为 1 1 8 1 1,均值为 ,方差为 。
Related
In following contests: