题解洛谷 P4546 【[THUWC2017]在美妙的数学王国中畅游】

首先发现有连边和删边的操作，所以我们肯定要用\(LCT\)来进行维护。

接下来考虑如何进行\(LCT\)上的信息合并。

\(f=1\),则函数为\(f(x)=sin(ax+b)\)

\(f=2\),则函数为\(f(x)=e^{ax+b}\)

\(f=3\),则函数为\(f(x)=ax+b\)

这道题中的信息为这三个函数，因为\(sin(ax+b)\)和\(e^{ax+b}\)不好处理，所以用泰勒展开都其处理为多项式的形式，再进行多项式的合并即可。

泰勒公式：

\[f(x)=\sum_{i=0}^{n} \frac{f^{(i)}(x_0)\times(x-x_0)^i}{i!}
\]

我们让\(x_0=0\)，得：

\[f(x)=\sum_{i=0}^{n} \frac{f^{(i)}(0)}{i!}x^i
\]

根据求导的知识，得：

\[(\sin x)'=\cos x
\]

\[(\cos x)'=-\sin x
\]

\[(-\sin x)'=-\cos x
\]

\[(-\cos x)'=\sin x
\]

\[(e^x)'=e^x
\]

同时再应用链式法则。

对\(sin(ax+b)\)进行泰勒展开得：

\[sin(ax+b)=\sum_{i=0}^{n} \frac{f^{(i)}(0)}{i!}x^i
\]

其中，\(f^{(i)}(0)\)为：

\[f^{(i)}(0)=\begin{cases}\sin(b)a^i\ (i\mod4=0)\\\cos(b)a^i\ (i\mod4=1)\\-\sin(b)a^i\ (i\mod4=2)\\-\cos(b)a^i\ (i\mod4=3)\end{cases}
\]

对\(e^{ax+b}\)进行泰勒展开得：

\[e^{ax+b}=\sum_{i=0}^{n} \frac{f^{(i)}(0)}{i!}x^i=\sum_{i=0}^{n} \frac{a^ie^b}{i!}x^i
\]

解决了信息合并后，修改查询什么的都是\(LCT\)的基本操作了，然后这道题就做完了。

实现细节看代码吧。

\(code:\)

#include<bits/stdc++.h>

#define maxn 100010

#define maxm 20

using namespace std;

template<typename T> inline void read(T &x)

{

	x=0;char c=getchar();bool flag=false;

	while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

	if(flag)x=-x;

}

int n,m;

char type[10];

int fa[maxn],ch[maxn][2],rev[maxn],f[maxn];

double fac[maxm],sum[maxn][maxm],a[maxn],b[maxn];

bool check(int x)

{

    return ch[fa[x]][1]==x;

}

void pushr(int x)

{

    rev[x]^=1;swap(ch[x][0],ch[x][1]);

}

void pushup(int x)

{

    for(int i=0;i<=15;++i)

        sum[x][i]=sum[ch[x][0]][i]+sum[ch[x][1]][i];

    if(f[x]==1)

    {

        double val=1,s=sin(b[x]),c=cos(b[x]);

        for(int i=0;i<=15;i+=4)

        {

            sum[x][i]+=s*val,val*=a[x];

            sum[x][i+1]+=c*val,val*=a[x];

            sum[x][i+2]-=s*val,val*=a[x];

            sum[x][i+3]-=c*val,val*=a[x];

        }

    }

    if(f[x]==2)

    {

        double val=exp(b[x]);

        for(int i=0;i<=15;++i) sum[x][i]+=val,val*=a[x];

    }

    if(f[x]==3) sum[x][1]+=a[x],sum[x][0]+=b[x];

}

void pushdown(int x)

{

    if(!rev[x]) return;

    pushr(ch[x][0]),pushr(ch[x][1]);

    rev[x]=0;

}

bool notroot(int x)

{

    return ch[fa[x]][0]==x||ch[fa[x]][1]==x;

}

void rotate(int x)

{

    int y=fa[x],z=fa[y],k=check(x),w=ch[x][k^1];

    if(notroot(y)) ch[z][check(y)]=x;

    fa[x]=z;

    ch[y][k]=w;

    if(w) fa[w]=y;

    ch[x][k^1]=y;

    fa[y]=x;

    pushup(y);

}

void all(int x)

{

    if(notroot(x)) all(fa[x]);

    pushdown(x);

}

void splay(int x)

{

    all(x);

    for(int y;notroot(x);rotate(x))

        if(notroot(y=fa[x]))

            rotate(check(x)^check(y)?x:y);

    pushup(x);

}

void access(int x)

{

    for(int y=0;x;y=x,x=fa[x])

        splay(x),ch[x][1]=y,pushup(x);

}

void makeroot(int x)

{

    access(x),splay(x),pushr(x);

}

void split(int x,int y)

{

    makeroot(x),access(y),splay(y);

}

int findroot(int x)

{

    access(x),splay(x);

    while(ch[x][0]) x=ch[x][0];

    splay(x);

    return x;

}

void link(int x,int y)

{

    makeroot(x),fa[x]=y;

}

void cut(int x,int y)

{

    split(x,y),fa[x]=ch[y][0]=0;

}

void modify(int x,int nf,double na,double nb)

{

    makeroot(x);

    f[x]=nf,a[x]=na,b[x]=nb;

}

double query(int x,int y,double q)

{

    double ans=0,now=1;

    split(x,y);

    for(int i=0;i<=15;++i)

        ans+=sum[y][i]*now/fac[i],now*=q;

    return ans;

}

void init()

{

    fac[0]=1;

    for(int i=1;i<=18;++i) fac[i]=fac[i-1]*i;

}

int main()

{

	init();

    read(n),read(m);

    scanf("%s",type);

    for(int i=1;i<=n;++i)

        read(f[i]),scanf("%lf%lf",&a[i],&b[i]);

    while(m--)

    {

        int x,y,nf;

        double na,nb,q;

        scanf("%s",type);

        if(type[0]=='a')

            read(x),read(y),link(x+1,y+1);

        if(type[0]=='d')

            read(x),read(y),cut(x+1,y+1);

        if(type[0]=='m')

        {

            read(x),read(nf),x++;

            scanf("%lf%lf",&na,&nb);

            modify(x,nf,na,nb);

        }

        if(type[0]=='t')

        {

            read(x),read(y),x++,y++;

            scanf("%lf",&q);

            if(findroot(x)!=findroot(y))

            {

                puts("unreachable");

                continue;

            }

            printf("%.10lf\n",query(x,y,q));

        }

    }

	return 0;

}

巴特西

题解洛谷 P4546 【[THUWC2017]在美妙的数学王国中畅游】

最新文章

热门文章

巴特西

题解 洛谷 P4546 【[THUWC2017]在美妙的数学王国中畅游】

最新文章

热门文章

题解洛谷 P4546 【[THUWC2017]在美妙的数学王国中畅游】