#2289. 「THUWC 2017」在美妙的数学王国中畅游

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: 匿名

题目描述

数字和数学规律主宰着这个世界。

机器的运转,

生命的消长,

宇宙的进程,

这些神秘而又美妙的过程无不可以用数学的语言展现出来。

这印证了一句古老的名言:

“学好数理化,走遍天下都不怕。”

学渣小R被大学的数学课程虐得生活不能自理,微积分的成绩曾是他在教室里上的课的最低分。然而他的某位陈姓室友却能轻松地在数学考试中得到满分。为了提升自己的数学课成绩,有一天晚上(在他睡觉的时候),他来到了数学王国。

数学王国中,每个人的智商可以用一个属于 [0,1][0,1] 的实数表示。数学王国中有 nn 个城市,编号从 00n1n-1 ,这些城市由若干座魔法桥连接。每个城市的中心都有一个魔法球,每个魔法球中藏有一道数学题。每个人在做完这道数学题之后都会得到一个在 [0,1][0,1] 区间内的分数。一道题可以用一个从 [0,1][0,1] 映射到 [0,1][0,1] 的函数 f(x)f(x) 表示。若一个人的智商为 xx ,则他做完这道数学题之后会得到 f(x)f(x) 分。函数 ff 有三种形式:

  • 正弦函数 sin(ax+b) (a[0,1],b[0,π],a+b[0,π])\sin(a x + b)\ (a \in [0,1], b \in [0,\pi],a+b\in[0,\pi])

  • 指数函数 eax+b (a[1,1],b[2,0],a+b[2,0])e^{ax+b}\ (a\in [-1,1], b\in [-2,0], a+b\in [-2,0])

  • 一次函数 ax+b (a[1,1],b[0,1],a+b[0,1])ax + b\ (a\in [-1,1],b\in[0,1],a+b\in [0,1])

数学王国中的魔法桥会发生变化,有时会有一座魔法桥消失,有时会有一座魔法桥出现。但在任意时刻,只存在至多一条连接任意两个城市的简单路径(即所有城市形成一个森林)。在初始情况下,数学王国中不存在任何的魔法桥。

数学王国的国王拉格朗日很乐意传授小R数学知识,但前提是小R要先回答国王的问题。这些问题具有相同的形式,即一个智商为 xx 的人从城市 uu 旅行到城市 vv (即经过 uuvv 这条路径上的所有城市,包括 uuvv )且做了所有城市内的数学题后,他所有得分的总和是多少。

输入格式

第一行两个正整数 n,mn,m 和一个字符串 typetype 。表示数学王国中共有 nn 座城市,发生了 mm 个事件,该数据的类型为 typetypetypetype 字符串是为了能让大家更方便地获得部分分,你可能不需要用到这个输入。其具体含义在【数据范围与提示】中有解释。

接下来 nn 行,第 ii 行表示初始情况下编号为 ii 的城市的魔法球中的函数。一个魔法用一个整数 ff 表示函数的类型,两个实数 a,ba,b 表示函数的参数,若

  • f=1f=1 ,则函数为 f(x)=sin(ax+b)(a[0,1],b[0,π],a+b[0,π])f(x)=\sin(ax+b)(a \in [0,1], b \in [0,\pi],a+b\in[0,\pi])
  • f=2f=2 ,则函数为 f(x)=eax+b(a[1,1],b[2,0],a+b[2,0])f(x)=e^{ax+b}(a\in[-1,1],b\in[-2,0],a+b\in[-2,0])
  • f=3f=3 ,则函数为 f(x)=ax+b(a[1,1],b[0,1],a+b[0,1])f(x)=ax+b(a\in[-1,1],b\in[0,1],a+b\in[0,1])

接下来 mm 行,每行描述一个事件,事件分为四类。

  • appear u v 表示数学王国中出现了一条连接 uuvv 这两座城市的魔法桥 (0u,v<n,uv)(0\le u,v < n, u\ne v) ,保证连接前 uuvv 这两座城市不能互相到达。
  • disappear u v 表示数学王国中连接 uuvv 这两座城市的魔法桥消失了,保证这座魔法桥是存在的。
  • magic c f a b 表示城市 cc 的魔法球中的魔法变成了类型为 ff ,参数为 a,ba,b 的函数
  • travel u v x 表示询问一个智商为 xx 的人从城市 uu 旅行到城市 vv (即经过 uuvv 这条路径上的所有城市,包括 uuvv )后,他得分的总和是多少。若无法从 uu 到达 vv ,则输出一行一个字符串 unreachable

输出格式

对于每个询问,输出一行实数,表示得分的总和。

样例

样例输入

3 7 C1
1 1 0
3 0.5 0.5
3 -0.5 0.7
appear 0 1
travel 0 1 0.3
appear 0 2
travel 1 2 0.5
disappear 0 1
appear 1 2
travel 1 2 0.5

样例输出

9.45520207e-001
1.67942554e+000
1.20000000e+000

数据范围与提示

【小R教你学数学】

若函数 f(x)f(x)nn 阶导数在 [a,b][a,b] 区间内连续,则对 f(x)f(x)x0(x0[a,b])x_0(x_0\in[a,b]) 处使用 nn 次拉格朗日中值定理可以得到带拉格朗日余项的泰勒展开式

f(x)=f(x0)+f(x0)(xx0)1!+f(x0)(xx0)22!++f(n1)(x0)(xx0)n1(n1)!+f(n)(ξ)(xx0)nn!,x[a,b]f(x)=f(x_0)+\frac{f'(x_0)(x-x_0)}{1!}+\frac{f''(x_0)(x-x_0)^2}{2!}+ \cdots +\frac{f^{(n-1)}(x_0)(x-x_0)^{n-1}}{(n-1)!}+\frac{f^{(n)}(\xi)(x-x_0)^n}{n!},x\in[a,b]

其中,当 x>x0x>x_0 时,ξ[x0,x]\xi\in[x_0,x]。当 x<x0x<x_0 时,ξ[x,x0]\xi\in[x,x_0]

f(n)f^{(n)}表示函数 ffnn 阶导数

【数据范围】

对于 100%100\% 的数据,1n100000,1m2000001\leq n \leq 100000, 1\leq m \leq 200000

本题共有20个数据点,每个数据点5分。

对于 5%5\% 的数据,n100,m2000n\le 100,m\le 2000,数据类型为C1
对于另外 20%20\% 的数据,数据类型为A0
对于另外 5%5\% 的数据,数据类型为B0
对于另外 10%10\% 的数据,数据类型为D0
对于另外 30%30\% 的数据,数据类型为A1
对于另外 15%15\% 的数据,数据类型为C1

数据类型的含义:

A:不存在 disappear 事件,且所有appear事件中的 u=v1u=v-1

B:不存在 disappear 事件

C:所有的 travel 事件经过的城市总数 5000000\leq 5000000(不可到达的城市对不计入在内)

D:无限制

0:所有 travel 事件中,x=1x=1(即所有人的智商均为 11

1:无限制

【评分标准】

如果你的答案与标准答案的相对误差在 10710^{-7} 以内或绝对误差在 10710^{-7} 以内,则被判定为正确。

如果你的所有答案均为正确,则得满分,否则得0分。

请注意输出格式:每行输出一个答案,答案只能为 unreachable 或者一个实数(建议使用科学计数法表示)。每行的长度不得超过50。错误输出格式会被判定为0分。