[THUWC2017] 在美妙的数学王国中畅游

题目背景

数字和数学规律主宰着这个世界。 机器的运转, 生命的消长, 宇宙的进程, 这些神秘而又美妙的过程无不可以用数学的语言展现出来。 这印证了一句古老的名言: “学好数理化,走遍天下都不怕。”

题目描述

学渣小R 被大学的数学课程虐得生活不能自理,微积分的成绩曾是他在教室里上的课的最低分。然而他的某位陈姓室友却能轻松地在数学考试中得到满分。为了提升自己的数学课成绩,有一天晚上(在他睡觉的时候),他来到了数学王国。 数学王国中,每个人的智商可以用一个属于 $ [0,1]$ 的实数表示。数学王国中有 $n$ 个城市,编号从 $0 \sim n-1$,这些城市由若干座魔法桥连接。每个城市的中心都有一个魔法球,每个魔法球中藏有一道数学题。 每个人在做完这道数学题之后都会得到一个在 $[0,1]$ 内的分数。一道题可以用一个函数 $f(x)$ 表示。若一个人的智商为 $x$,则他做完这道数学题之后会得到 $f(x)$ 分。有三种形式: - 正弦函数 $f(x)=\sin(a x + b)\ (a \in [0,1], b \in [0,\pi],a+b\in[0,\pi])$ - 指数函数 $f(x)=\text e^{ax+b}\ (a\in [-1,1], b\in [-2,0], a+b\in [-2,0])$ - 一次函数 $f(x) = ax + b\ (a\in [-1,1],b\in[0,1],a+b\in [0,1])$ 数学王国中的魔法桥会发生变化,有时会有一座魔法桥消失,有时会有一座魔法桥出现。但在任意时刻,只存在至多一条连接任意两个城市的简单路径(即所有城市形成一个森林)。在初始情况下,数学王国中不存在任何的魔法桥。 数学王国的国王拉格朗日很乐意传授小R 数学知识,但前提是小R 要先回答国王的问题。这些问题具有相同的形式,即一个智商为 $x$ 的人从城市 $u$ 旅行到城市 $v$(即经过 $u \to v$ 这条路径上的所有城市,包括 $u$ 和 $v$)且做了所有城市内的数学题后,他所有得分的总和是多少。

输入输出格式

输入格式


第一行两个正整数 $n,m$ 和一个字符串 $type$。表示数学王国中共有 $n$ 座城市,发生了 $m$ 个事件,该数据的类型为 $type$。 $type$ 字符串是为了能让大家更方便地获得部分分,你可能不需要用到这个输入。其具体含义在 **【限制与约定】** 中有解释。 接下来 $n$ 行,第 $i$ 行表示初始情况下编号为 $i$ 的城市的魔法球中的函数。一个魔法用一个整数 $f$ 表示函数的类型,两个实数 $a,b$ 表示函数的参数,若 - $f=1$,则函数为 $f(x)=\sin(ax+b)$ - $f=2$,则函数为 $f(x)=\text e^{ax+b}$ - $f=3$,则函数为 $f(x)=ax+b$ 接下来 $m$ 行,每行描述一个事件,事件分为四类。 - `appear u v` 表示数学王国中出现了一条连接 $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$,则输出一行一个字符串 `unreachable`。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

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

说明

【限制与约定】 对于 $100\%$ 的数据,$1\le n\le 10^5, 1\le m \le 2 \times 10^5$ 。 本题共有 20 个数据点,每个数据点 5 分。 测试点|$n$|$m$|数据类型 :-:|:-:|:-:|:-:| $1$|$\leq 100$|$\leq 200$|C1 $2 \sim 5$|$\leq 10^5$|$\leq 2 \times 10^5$|A0 $6$|$\leq 10^5$|$\leq 2 \times 10^5$|B0 $7 \sim 8$|$\leq 10^5$|$\leq 2 \times 10^5$|D0 $9 \sim 14$|$\leq 10^5$|$\leq 2 \times 10^5$|A1 $15 \sim 17$|$\leq 10^5$|$\leq 2 \times 10^5$|C1 $18 \sim 20$|$\leq 10^5$|$\leq 2 \times 10^5$|D1 数据类型的含义: A:不存在 `disappear` 事件,且所有`appear`事件中的 $u=v-1$ B:不存在 `disappear` 事件 C:所有的 `travel` 事件经过的城市总数 $\le 5 \times 10^6$(不可到达的城市对不计入在内) D:无限制 0:所有 `travel` 事件中,$x=1$(即所有人的智商均为 $1$) 1:无限制 【评分标准】 如果你的答案与标准答案的相对误差在 $10^{-7}$ 以内或绝对误差在 $10^{-7}$ 以内,则被判定为正确。 如果你的所有答案均为正确,则得满分,否则得 0 分。 请注意输出格式:每行输出一个答案,答案只能为 `unreachable` 或者一个实数(建议使用科学计数法表示)。每行的长度不得超过 50。错误输出格式会被判定为 0 分。 【小R 教你学数学】 若函数 $f(x)$ 的 $n$ 阶导数在 $[a,b]$ 区间内连续,则对 $f(x)$ 在 $x_0 \ (x_0\in[a,b])$ 处使用 $n$ 次拉格朗日中值定理可以得到带拉格朗日余项的泰勒展开式 $$f(x)=\sum_{k=0}^{n-1}\frac{f^{(k)}(x_0)(x-x_0)^k}{k!}+\frac{f^{(n)}(\xi)(x-x_0)^n}{n!},x\in[a,b]$$ 其中,当 $x>x_0$ 时,$\xi\in[x_0,x]$。当 $x<x_0$ 时,$\xi\in[x,x_0]$。 $f^{(n)}$ 表示函数 $f$ 的 $n$ 阶导数