THUWC2017 在美妙的数学王国中畅游（LCT）

发表于 |
字数统计: 2,558字 | 阅读时长 ≈ 12min

问题描述

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

机器的运转，

生命的消长，

宇宙的进程，

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

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

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

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

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

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

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

  • 一次函数 $ax + b\ (a\in [-1,1],b\in[0,1],a+b\in [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 \in [0,1], b \in [0,\pi],a+b\in[0,\pi])$
  • $f=2$ ,则函数为 $f(x)=e^{ax+b}(a\in[-1,1],b\in[-2,0],a+b\in[-2,0])$
  • $f=3$ ,则函数为 $f(x)=ax+b(a\in[-1,1],b\in[0,1],a+b\in[0,1])$

接下来 $m$ 行，每行描述一个事件，事件分为四类。

  • appear u v 表示数学王国中出现了一条连接 $u$ 和 $v$ 这两座城市的魔法桥 $(0\le u,v < n, u\ne 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
2
3
4
5
6
7
8
9
10
11
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
2
3
9.45520207e-001
1.67942554e+000
1.20000000e+000

提示

【小R教你学数学】

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

$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>x_0$ 时，$\xi\in[x_0,x]$。当 $x<x_0$ 时，$\xi\in[x,x_0]$。

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

【数据范围】

对于 $100\%$ 的数据，$1\leq n \leq 100000, 1\leq m \leq 200000$ 。

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

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

数据类型的含义：

A：不存在 disappear 事件，且所有appear事件中的 $u=v-1$

B：不存在 disappear 事件

C：所有的 travel 事件经过的城市总数 $\leq 5000000$（不可到达的城市对不计入在内）

D：无限制

0：所有 travel 事件中，$x=1$（即所有人的智商均为 $1$ ）

1：无限制

【评分标准】

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

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

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

提示里已经将做法点明了，直接将题给的函数在 $x_0=0$ 处展开成一个多项式，然后就可以直接上 $LCT$ 维护了

注意到展开位数越多则精度越高，但运行速度越慢，所以展开十几位就差不多了

剩下的都是 $LCT$ 的基本操作了

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 100005
#define db double
using namespace std;
const int K=11;
struct poly{db a[K];}v[N],sum[N];
poly operator+(poly a,poly b)
{
    poly c;
    for(int i=0;i<K;i++)c.a[i]=a.a[i]+b.a[i];
    return c;
}
db getval(poly a,db x)
{
    db sum=0,t=1.0;
    for(int i=0;i<K;i++,t*=x)sum+=a.a[i]*t;
    return sum;
}
poly trans(int f,db a,db b)
{
    poly c;
    if(f==1)
    {
        db S=sin(b),C=cos(b),t=1.0;
        for(int i=0;i<K;i++,t=t/i*a)
        {
            if(i&1)c.a[i]=((i&3)==1)?t*C:-t*C;
            else c.a[i]=((i&3)==0)?t*S:-t*S;
        }
        return c;
    }
    if(f==2)
    {
        db t=exp(b);
        for(int i=0;i<K;i++,t=t/i*a)c.a[i]=t;
        return c;
    }
    if(f==3)
    {
        memset(c.a,0,sizeof(c.a));
        c.a[0]=b;c.a[1]=a;return c;
    }
}
int n,m,ls[N],rs[N],fa[N],tot,rt,rev[N],S[N],tp;
bool isroot(int x){return ls[fa[x]]!=x&&rs[fa[x]]!=x;}
void update(int x){sum[x]=v[x]+sum[ls[x]]+sum[rs[x]];}
void zig(int x)
{
    int y=fa[x],z=fa[y];
    if(!isroot(y))y==ls[z]?ls[z]=x:rs[z]=x;fa[x]=z;
    ls[y]=rs[x];fa[rs[x]]=y;
    rs[x]=y;fa[y]=x;
    update(y);update(x);
}
void zag(int x)
{
    int y=fa[x],z=fa[y];
    if(!isroot(y))y==ls[z]?ls[z]=x:rs[z]=x;fa[x]=z;
    rs[y]=ls[x];fa[ls[x]]=y;
    ls[x]=y;fa[y]=x;
    update(y);update(x);
}
void putdown(int x)
{
    if(rev[x])
    {
        swap(ls[x],rs[x]);
        rev[ls[x]]^=1;
        rev[rs[x]]^=1;
        rev[x]=0;
    }
}
void splay(int x)
{
    int i,y,z;S[tp=1]=x;
    for(i=x;!isroot(i);i=fa[i])S[++tp]=fa[i];
    while(tp)putdown(S[tp--]);
    while(!isroot(x))
    {
        y=fa[x],z=fa[y];
        if(!isroot(y))
        {
            if(y==ls[z])x==ls[y]?(zig(y),zig(x)):(zag(x),zig(x));
            else x==rs[y]?(zag(y),zag(x)):(zig(x),zag(x));
        }
        else x==ls[y]?zig(x):zag(x);
    }
}
void access(int x)
{
    for(int t=0;x;x=fa[x])
    {
        splay(x);
        rs[x]=t;
        update(x);t=x;
    }
}
void makeroot(int x)
{
    access(x);
    splay(x);
    rev[x]^=1;
}
int findroot(int x)
{
    access(x);
    splay(x);
    while(ls[x])x=ls[x];
    return x;
}
void link(int x,int y)
{
    makeroot(x);
    fa[x]=y;
}
void cut(int x,int y)
{
    makeroot(x);
    access(y);
    splay(y);
    ls[y]=fa[x]=0;
}
void modify(int x,poly d)
{
    makeroot(x);
    splay(x);
    v[x]=d;update(x);
}
db getans(int x,int y,db d)
{
    makeroot(x);
    access(y);
    splay(y);
    return getval(sum[y],d);
}
int main()
{
    int i,j,k,x,y;double a,b,d;char s[12];
    scanf("%d%d%s",&n,&m,s);
    for(i=1;i<=n;i++)
    {
        scanf("%d%lf%lf",&k,&a,&b);
        v[i]=sum[i]=trans(k,a,b);
    }
    for(i=1;i<=m;i++)
    {
        scanf("%s",s);
        if(s[0]=='a')
        {
            scanf("%d%d",&x,&y);
            link(x+1,y+1);
        }
        if(s[0]=='d')
        {
            scanf("%d%d",&x,&y);
            cut(x+1,y+1);
        }
        if(s[0]=='m')
        {
            scanf("%d%d%lf%lf",&x,&k,&a,&b);
            modify(x+1,trans(k,a,b));
        }
        if(s[0]=='t')
        {
            scanf("%d%d%lf",&x,&y,&d);
            if(findroot(x+1)==findroot(y+1))printf("%.10lf\n",getans(x+1,y+1,d));
            else puts("unreachable");
        }
    }
}