BZPRO

#5020. [THUWC 2017]在美妙的数学王国中畅游

内存限制：512 MiB 时间限制：80 Sec
提交 提交记录 讨论

题目描述

数字和数学规律主宰着这个世界。
机器的运转，
生命的消长，
宇宙的进程，
这些神秘而又美妙的过程无不可以用数学的语言展现出来。
这印证了一句古老的名言：
“学好数理化，走遍天下都不怕。”
学渣小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,π])
    指数函数 e^(ax+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 。 
typet 字符串是为了能让大家更方便地获得部分分，你可能不需要用到这个输入。
其具体含义在【数据范围与提示】中有解释。
接下来 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)=e^(ax+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。
1≤n≤100000,1≤m≤200000

输出格式

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

样例

样例输入


			
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

数据范围与提示

BZPRO Powered by Remmina.
Github Repository