题目描述
数字和数学规律主宰着这个世界。
机器的运转,
生命的消长,
宇宙的进程,
这些神秘而又美妙的过程无不可以用数学的语言展现出来。
这印证了一句古老的名言:
“学好数理化,走遍天下都不怕。”
学渣小R被大学的数学课程虐得生活不能自理,微积分的成绩曾是他在教室里上的课的最低分。然而他的某位陈姓室友却能轻松地在数学考试中得到满分。为了提升自己的数学课成绩,有一天晚上(在他睡觉的时候),他来到了数学王国。
数学王国中,每个人的智商可以用一个属于 [0,1] 的实数表示。数学王国中有 n 个城市,编号从 0 到 n−1 ,这些城市由若干座魔法桥连接。每个城市的中心都有一个魔法球,每个魔法球中藏有一道数学题。每个人在做完这道数学题之后都会得到一个在 [0,1] 区间内的分数。一道题可以用一个从 [0,1] 映射到 [0,1] 的函数 f(x) 表示。若一个人的智商为 x ,则他做完这道数学题之后会得到 f(x) 分。函数 f 有三种形式:
-
正弦函数 sin(ax+b) (a∈[0,1],b∈[0,π],a+b∈[0,π])
-
指数函数 eax+b (a∈[−1,1],b∈[−2,0],a+b∈[−2,0])
-
一次函数 ax+b (a∈[−1,1],b∈[0,1],a+b∈[0,1])
数学王国中的魔法桥会发生变化,有时会有一座魔法桥消失,有时会有一座魔法桥出现。但在任意时刻,只存在至多一条连接任意两个城市的简单路径(即所有城市形成一个森林)。在初始情况下,数学王国中不存在任何的魔法桥。
数学王国的国王拉格朗日很乐意传授小R数学知识,但前提是小R要先回答国王的问题。这些问题具有相同的形式,即一个智商为 x 的人从城市 u 旅行到城市 v (即经过 u 到 v 这条路径上的所有城市,包括 u 和 v )且做了所有城市内的数学题后,他所有得分的总和是多少。
输入格式
第一行两个正整数 n,m 和一个字符串 type 。表示数学王国中共有 n 座城市,发生了 m 个事件,该数据的类型为 type 。 type 字符串是为了能让大家更方便地获得部分分,你可能不需要用到这个输入。其具体含义在**【数据范围与提示】**中有解释。
接下来 n 行,第 i 行表示初始情况下编号为 i 的城市的魔法球中的函数。一个魔法用一个整数 f 表示函数的类型,两个实数 a,b 表示函数的参数,若
- f=1 ,则函数为 f(x)=sin(ax+b)(a∈[0,1],b∈[0,π],a+b∈[0,π])
- f=2 ,则函数为 f(x)=eax+b(a∈[−1,1],b∈[−2,0],a+b∈[−2,0])
- f=3 ,则函数为 f(x)=ax+b(a∈[−1,1],b∈[0,1],a+b∈[0,1])
接下来 m 行,每行描述一个事件,事件分为四类。
appear u v
表示数学王国中出现了一条连接 u 和 v 这两座城市的魔法桥 (0≤u,v<n,u=v) ,保证连接前 u 和 v 这两座城市不能互相到达。
disappear u v
表示数学王国中连接 u 和 v 这两座城市的魔法桥消失了,保证这座魔法桥是存在的。
magic c f a b
表示城市 c 的魔法球中的魔法变成了类型为 f ,参数为 a,b 的函数
travel u v x
表示询问一个智商为 x 的人从城市 u 旅行到城市 v (即经过 u 到 v 这条路径上的所有城市,包括 u 和 v )后,他得分的总和是多少。若无法从 u 到达 v ,则输出一行一个字符串 unreachable
。
输出格式
对于每个询问,输出一行实数,表示得分的总和。
数据范围与提示
【小R教你学数学】
若函数 f(x) 的 n 阶导数在 [a,b] 区间内连续,则对 f(x) 在 x0(x0∈[a,b]) 处使用 n 次拉格朗日中值定理可以得到带拉格朗日余项的泰勒展开式
f(x)=f(x0)+1!f′(x0)(x−x0)+2!f′′(x0)(x−x0)2+⋯+(n−1)!f(n−1)(x0)(x−x0)n−1+n!f(n)(ξ)(x−x0)n,x∈[a,b]
其中,当 x>x0 时,ξ∈[x0,x]。当 x<x0 时,ξ∈[x,x0]。
f(n)表示函数 f 的 n 阶导数
【数据范围】
对于 100% 的数据,1≤n≤100000,1≤m≤200000 。
本题共有20个数据点,每个数据点5分。
对于 5% 的数据,n≤100,m≤2000,数据类型为C1
;
对于另外 20% 的数据,数据类型为A0
;
对于另外 5% 的数据,数据类型为B0
;
对于另外 10% 的数据,数据类型为D0
;
对于另外 30% 的数据,数据类型为A1
;
对于另外 15% 的数据,数据类型为C1
;
数据类型的含义:
A:不存在 disappear
事件,且所有appear
事件中的 u=v−1
B:不存在 disappear
事件
C:所有的 travel
事件经过的城市总数 ≤5000000(不可到达的城市对不计入在内)
D:无限制
0:所有 travel
事件中,x=1(即所有人的智商均为 1 )
1:无限制
【评分标准】
如果你的答案与标准答案的相对误差在 10−7 以内或绝对误差在 10−7 以内,则被判定为正确。
如果你的所有答案均为正确,则得满分,否则得0分。
请注意输出格式:每行输出一个答案,答案只能为 unreachable
或者一个实数(建议使用科学计数法表示)。每行的长度不得超过50。错误输出格式会被判定为0分。