题目概述

有 $n$ 个点，每个点是一个函数：$sin(ax+b),e^{ax+b},ax+b$ 。有 $4$ 种操作：1.连接 $x,y$ 。2.断开 $x,y$ 。3.修改 $x$ 点函数。4.询问从 $u$ 到 $v$ 自变量为 $x$ 获得的函数值的和。

解题报告

最近文化课学导数学了泰勒展开……想到了这一题，发现是裸题……

泰勒展开：一个函数 $f(x)$ 可以在 $x_0$ 处近似展开成 $n$ 次多项式：

$f(x)=\sum_{i=0}^{n}f^{(i)}(x_0)(x-x_0)^{i}$ ，其中 $f^{(i)}$ 是 $f$ 的 $i$ 阶导数，证明问数竞去。

把每个函数在 $x_{0}=0$ 进行泰勒展开，然后就可以用LCT维护一条路径的多项式了。我展开了 $15$ 层就过了。

示例程序

#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long double DB;
const int maxn=100000,maxm=15;

int n,te,son[maxn+5][2],fa[maxn+5];
DB A[maxn+5][maxm+5],S[maxn+5][maxm+5];bool flip[maxn+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return (l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r))?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
template<typename T> inline int readf(T &x){
    T tot=0,now=10;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=tot*10+(ch^48),ch=readc();
    if (ch=='.') for (ch=readc();isdigit(ch);ch=readc(),now*=10) tot+=(ch^48)/now;
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define is_ro(x) ((x)!=son[fa[x]][0]&&(x)!=son[fa[x]][1])
#define Son(x) ((x)==son[fa[x]][1])
inline void Pushup(int p) {for (int i=0;i<=maxm;i++) S[p][i]=S[son[p][0]][i]+S[son[p][1]][i]+A[p][i];}
inline void Rotate(int t){
    int p=fa[t],d=Son(t);son[p][d]=son[t][d^1];son[t][d^1]=p;
    if (!is_ro(p)) son[fa[p]][Son(p)]=t;Pushup(p);Pushup(t);
    if (son[p][d]) fa[son[p][d]]=p;fa[t]=fa[p];fa[p]=t;
}
inline void Addflip(int p) {swap(son[p][0],son[p][1]);flip[p]^=1;}
inline void Pushdown(int p) {if (flip[p]) Addflip(son[p][0]),Addflip(son[p][1]),flip[p]^=1;}
inline void Splay(int p){
    static int top,stk[maxn+5];stk[top=1]=p;
    for (int i=p;!is_ro(i);i=fa[i]) stk[++top]=fa[i];
    while (top) Pushdown(stk[top--]);
    for (int pre=fa[p];!is_ro(p);Rotate(p),pre=fa[p])
        if (!is_ro(pre)) Rotate(Son(pre)==Son(p)?pre:p);
}
inline void Access(int p) {for (int lst=0;p;lst=p,p=fa[p]) Splay(p),son[p][1]=lst,Pushup(p);}
inline void Makero(int x) {Access(x);Splay(x);Addflip(x);}
inline void Link(int x,int y) {Makero(x);fa[x]=y;}
inline void Cut(int x,int y) {Makero(x);Access(y);Splay(x);son[x][1]=fa[y]=0;Pushup(x);}
inline void Ask(int x,int y,DB z){
    Makero(x);Access(y);Splay(x);while (fa[y]) y=fa[y];if (y!=x) {puts("unreachable");return;}
    DB ans=0,w=1;for (int i=0;i<=maxm;i++) ans+=w*S[x][i],w*=z;printf("%.8e\n",(double)ans);
}
inline void Fun(int x,int tp,DB a,DB b){
    if (Splay(x),tp==1){
        int g=0,f=1;DB w=1,fac=1;
        for (int i=0;i<=maxm;i++,w*=a,fac*=i) A[x][i]=(g?cos(b):sin(b))*(f>0?w:-w)/fac,g?f=-f:0,g^=1;
    } else if (tp==2){
        DB w=1,pw=pow(2.718281828,b),fac=1;
        for (int i=0;i<=maxm;i++,w*=a,fac*=i) A[x][i]=pw*w/fac;
    } else {A[x][0]=b;A[x][1]=a;for (int i=2;i<=maxm;i++) A[x][i]=0;}Pushup(x);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);readi(te);int orz;readi(orz);
    for (int i=1;i<=n;i++) {int tp;DB a,b;readi(tp);readf(a);readf(b);Fun(i,tp,a,b);}
    for (int x,y;te;te--){
        char tp=readc();while (!islower(tp)) tp=readc();readi(x);x++;DB a,b;
        if (tp=='a') readi(y),y++,Link(x,y); else if (tp=='d') readi(y),y++,Cut(x,y);
        else if (tp=='m') readi(y),readf(a),readf(b),Fun(x,y,a,b); else readi(y),y++,readf(a),Ask(x,y,a);
    }return 0;
}