「THUWC 2017」在美妙的数学王国中畅游

题目链接

问题分析

首先，有连边删边操作，那么LCT逃不了了。那么如何维护函数信息？注意到题目末尾的提示，结合题目所给的精度要求，我们取前十几项就可以了。那么我们就只需要维护多项式就行。

对于第一种函数
$$
f(x)=\sin(ax+b)\\\\
f’(x)=a\cos(ax+b)\\\\
f’’(x)=-a^2\sin(ax+b)\\\\
f^{(3)}=-a^3\cos(ax+b)
$$
对于第二种函数
$$
f(x)=e^{ax+b}\\\\
f^{(n)}(x)=a^ne^{ax+b}
$$
对于第三种函数
$$
f(x)=ax+b\\\\
f’(x)=a\\\\
f^{(n)}(x)=0(n>1)
$$
那么就做完了。

参考程序

常规操作，常规操作。

#include <bits/stdc++.h>
using namespace std;

const int Maxn = 100010;

namespace readInformation {

    int n, m;
    char Type[ 10 ];
    struct readFuntionType {
        int f;
        double a, b;
    };
    readFuntionType Function[ Maxn ];

    struct readOpt {
        char Opt[ 10 ];
        int u, v, c, f;
        double a, b, x;
    };

    void Read() {
        scanf( "%d%d%s", &n, &m, Type );
        for( int i = 1; i <= n; ++i ) 
            scanf( "%d%lf%lf", &Function[ i ].f, &Function[ i ].a, &Function[ i ].b );
        return;
    }

    readOpt GetOpt() {
        readOpt Ans;
        scanf( "%s", Ans.Opt );
        if( Ans.Opt[ 0 ] == 'a' ) {
            scanf( "%d%d", &Ans.u, &Ans.v );
            ++Ans.u; ++Ans.v;
        }
        if( Ans.Opt[ 0 ] == 'd' ) {
            scanf( "%d%d", &Ans.u, &Ans.v );
            ++Ans.u; ++Ans.v;
        }
        if( Ans.Opt[ 0 ] == 'm' ) {
            scanf( "%d%d%lf%lf", &Ans.c, &Ans.f, &Ans.a, &Ans.b );
            ++Ans.c;
        }
        if( Ans.Opt[ 0 ] == 't' ) {
            scanf( "%d%d%lf", &Ans.u, &Ans.v, &Ans.x );
            ++Ans.u; ++Ans.v;
        }
        return Ans;
    }
} // readInformation

namespace Splay {

    const int MaxNum = 16;

    struct splayNode {
        int Father, Child[ 2 ], IsReverse;
        double Poly[ MaxNum ];
    };
    splayNode Splay[ Maxn ];

    int Stack[ Maxn ], Size;

    bool IsRoot( int x ) {
        return Splay[ Splay[ x ].Father ].Child[ 0 ] != x && Splay[ Splay[ x ].Father ].Child[ 1 ] != x;
    }

    void Reverse( int x ) {
        Splay[ x ].IsReverse ^= 1;
        swap( Splay[ x ].Child[ 0 ], Splay[ x ].Child[ 1 ] );
        return;
    }

    void Collect( int x ) {
        for( int i = 0; i < MaxNum; ++i ) 
            Splay[ x ].Poly[ i ] = Splay[ Splay[ x ].Child[ 0 ] ].Poly[ i ] + Splay[ Splay[ x ].Child[ 1 ] ].Poly[ i ];
        if( readInformation::Function[ x ].f == 1 ) {
            double t = 1, Sin = sin( readInformation::Function[ x ].b ), Cos = cos( readInformation::Function[ x ].b );
            for( int i = 0; i < MaxNum; i += 4 ) {
                Splay::Splay[ x ].Poly[ i ] += Sin * t; t *= readInformation::Function[ x ].a;       
                Splay::Splay[ x ].Poly[ i + 1 ] += Cos * t; t *= readInformation::Function[ x ].a;       
                Splay::Splay[ x ].Poly[ i + 2 ] -= Sin * t; t *= readInformation::Function[ x ].a;       
                Splay::Splay[ x ].Poly[ i + 3 ] -= Cos * t; t *= readInformation::Function[ x ].a;       
            }
        }
        if( readInformation::Function[ x ].f == 2 ) {
            double Exp = exp( readInformation::Function[ x ].b );
            Splay[ x ].Poly[ 0 ] += Exp;
            for( int i = 1; i < MaxNum; ++i ) {
                Exp *= readInformation::Function[ x ].a;
                Splay[ x ].Poly[ i ] += Exp;
            }
        }
        if( readInformation::Function[ x ].f == 3 ) {
            Splay[ x ].Poly[ 0 ] += readInformation::Function[ x ].b;
            Splay[ x ].Poly[ 1 ] += readInformation::Function[ x ].a;
        }
        return;
    }

    void PushDown( int x ) {
        if( !Splay[ x ].IsReverse ) return;
        Reverse( Splay[ x ].Child[ 0 ] );
        Reverse( Splay[ x ].Child[ 1 ] );
        Splay[ x ].IsReverse ^= 1;
        return;
    }

    void Rotate( int x ) {
        int y = Splay[ x ].Father;
        int z = Splay[ y ].Father;
        int Tag = Splay[ y ].Child[ 1 ] == x;
        if( !IsRoot( y ) ) Splay[ z ].Child[ Splay[ z ].Child[ 1 ] == y ] = x;
        Splay[ x ].Father = z;
        Splay[ Splay[ x ].Child[ Tag ^ 1 ] ].Father = y;
        Splay[ y ].Child[ Tag ] = Splay[ x ].Child[ Tag ^ 1 ];
        Splay[ x ].Child[ Tag ^ 1 ] = y;
        Splay[ y ].Father = x;
        Collect( y ); Collect( x );
        return;
    }

    void splay( int x ) {
        Size = 0;
        Stack[ ++Size ] = x;
        int t = x;
        for( ; !IsRoot( t ); t = Splay[ t ].Father ) Stack[ ++Size ] = Splay[ t ].Father;
        for( ; Size; --Size ) PushDown( Stack[ Size ] );
        while( !IsRoot( x ) ) {
            int y = Splay[ x ].Father;
            int z = Splay[ y ].Father;
            if( !IsRoot( y ) )
                if( ( Splay[ z ].Child[ 0 ] == y ) ^ ( Splay[ y ].Child[ 0 ] == x ) )
                    Rotate( x );
                else
                    Rotate( y );
            Rotate( x );
        }
        return;
    }

} // Splay

namespace LCT {

    void Access( int x ) {
        for( int Last = 0; x; Last = x, x = Splay::Splay[ x ].Father ) {
            Splay::splay( x );
            Splay::Splay[ x ].Child[ 1 ] = Last;
            Splay::Collect( x );
        }
        return;
    }

    void MakeRoot( int x ) {
        Access( x );
        Splay::splay( x );
        Splay::Reverse( x );
        return;
    }

    int FindRoot( int x ) {
        Access( x );
        Splay::splay( x );
        Splay::PushDown( x );
        while( Splay::Splay[ x ].Child[ 0 ] ) {
            x = Splay::Splay[ x ].Child[ 0 ];
            Splay::PushDown( x );
        }
        Splay::splay( x );
        return x;
    }

    void Split( int x, int y ) {
        MakeRoot( x );
        Access( y );
        Splay::splay( y );
        return;
    }

    void Link( int x, int y ) {
        MakeRoot( x );
        if( FindRoot( y ) == x ) return;
        Splay::Splay[ x ].Father = y;
        return;
    }

    void Cut( int x, int y ) {
        MakeRoot( x );
        if( FindRoot( y ) != x || Splay::Splay[ y ].Child[ 0 ] || Splay::Splay[ y ].Father != x ) return;
        Splay::Splay[ y ].Father = Splay::Splay[ x ].Child[ 1 ] = 0;
        Splay::Collect( x );
        return;
    }

} // LCT

namespace Main {

    double Fact[ Splay::MaxNum ];

    void Main() {
        Fact[ 0 ] = 1;
        for( int i = 1; i < Splay::MaxNum; ++i ) Fact[ i ] = Fact[ i - 1 ] * i;
        for( int i = 1; i <= readInformation::m; ++i ) {
            readInformation::readOpt ReadOpt = readInformation::GetOpt();
            if( ReadOpt.Opt[ 0 ] == 'a' ) LCT::Link( ReadOpt.u, ReadOpt.v );
            if( ReadOpt.Opt[ 0 ] == 'd' ) LCT::Cut( ReadOpt.u, ReadOpt.v );
            if( ReadOpt.Opt[ 0 ] == 'm' ) { 
                LCT::MakeRoot( ReadOpt.c ); 
                readInformation::Function[ ReadOpt.c ].f = ReadOpt.f;
                readInformation::Function[ ReadOpt.c ].a = ReadOpt.a;
                readInformation::Function[ ReadOpt.c ].b = ReadOpt.b;
                Splay::Collect( ReadOpt.c );
            }
            if( ReadOpt.Opt[ 0 ] == 't' ) {
                if( LCT::FindRoot( ReadOpt.u ) != LCT::FindRoot( ReadOpt.v ) ) {
                    printf( "unreachable\n" ); 
                    continue;
                }
                LCT::Split( ReadOpt.u, ReadOpt.v );
                double Ans = 0, x = 1;
                for( int j = 0; j < Splay::MaxNum; ++j ) 
                    Ans += Splay::Splay[ ReadOpt.v ].Poly[ j ] * x / Fact[ j ], x = x * ReadOpt.x;
                printf( "%.8e\n", Ans );
            }
        }
        return;
    }

} // Main

int main() {
    readInformation::Read();
    Main::Main();
    return 0;
}