并不对劲的bzoj5020:loj2289:p4546:[THUWC2017]在美妙的数学王国中畅游

题目大意

有一个n(\(n\leq 10^5\))个点的森林，每个点\(u\)上有个函数\(f_u(x)\)，是形如\(ax+b\)或\(e^{ax+b}\)或\(sin(ax+b)\)的函数，保证当\(x\in[0,1]\)时，\(f_u(x)\in[0,1]\)

有\(q(q\leq 2*10^5)\)个操作，每个操作是以下三个中的一个：

1.连接一条边，保证这条边的两个端点之前不连通

2.切断一条边，保证这条边存在

3.查询，给出\(u,v,x(u,x\leq n, 0\leq x \leq 1)\)，表示从\(u\)到\(v\)每个点\(a\)的\(f_a(x)\)之和

题解

要维护一个森林，支持连边、删边，很可能是用LCT做

如果只有第一类函数，那么直接算出\(u\)到\(v\)路径上所有点的一次项系数和零次项系数之和就行

所以将后两类函数转化成多项式函数

可以用泰勒展开，算出十几项，精度基本上就够了

代码

#include<algorithm>

#include<cmath>

#include<complex>

#include<ctime>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iomanip>

#include<iostream>

#include<map>

#include<stack>

#include<queue>

#include<vector>

#define rep(i,x,y) for(int i=(x);i<=(y);++i)

#define dwn(i,x,y) for(int i=(x);i>=(y);--i)

#define D double

#define maxn 100010

#define ls son[u][0]

#define rs son[u][1]

using namespace std;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)&&ch!='-')ch=getchar();

    if(ch=='-')f=-1,ch=getchar();

    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

    return x*f;

}

void write(int x)

{

    if(x==0){putchar('0'),putchar('\n');return;}

    if(x<0)putchar('-'),x=-x;

    char ch[20];int f=0;

    while(x)ch[++f]=x%10+'0',x/=10;

    while(f)putchar(ch[f--]);

    putchar('\n');return;

}

D key[maxn][20],sum[maxn][20];

int son[maxn][2],fa[maxn],s[maxn],re[maxn],tp,lim=15;

void pu(int u)

{

    rep(i,0,lim)sum[u][i]=key[u][i];

    if(ls)rep(i,0,lim)sum[u][i]+=sum[ls][i];

    if(rs)rep(i,0,lim)sum[u][i]+=sum[rs][i];

    return;

}

void mark(int u){if(u)swap(ls,rs),re[u]^=1;}

void pd(int u){if(re[u])mark(ls),mark(rs),re[u]=0;}

int nort(int u){return son[fa[u]][0]==u||son[fa[u]][1]==u;}

int getso(int u){return son[fa[u]][0]!=u;}

void rot(int u)

{

    int fu=fa[u],ffu=fa[fu],l=getso(u),fl=getso(fu),r=l^1,rson=son[u][r];

    if(nort(fu))son[ffu][fl]=u;son[fu][l]=rson,son[u][r]=fu,fa[rson]=fu,fa[u]=ffu,fa[fu]=u;

    pu(fu),pu(u);

}

void splay(int u)

{

    int v=u;s[tp=1]=u;while(nort(v))s[++tp]=v=fa[v];while(tp)pd(s[tp--]);

    while(nort(u)){int fu=fa[u];if(nort(fu))rot(getso(u)^getso(fu)?u:fu);rot(u);}

}

void acs(int u){for(int v=0;u;v=u,u=fa[u])splay(u),rs=v,pu(u);}

void chrt(int u){acs(u),splay(u),mark(u);}

int getrt(int u){acs(u),splay(u);while(ls)u=ls;return u;}

void link(int u,int v){chrt(u);fa[u]=v;}

void cut(int u,int v){chrt(u),acs(v),splay(v);son[v][0]=fa[u]=0;}

int getrd(int u,int v){chrt(u);if(getrt(v)!=u)return 0;acs(v),splay(v);return v;}

int n,m;

D po[20];

char typ[20];

int main()

{

    scanf("%d%d%s",&n,&m,typ);po[0]=1;

    rep(i,1,lim)po[i]=po[i-1]*1.0*i;

    rep(i,1,n)

    {

        int x;D a,b;

        scanf("%d%lf%lf",&x,&a,&b);

        if(x==1)

        {

            D val=1,Sin=sin(b),Cos=cos(b);

            for(int j=0;j<=lim;j+=4)

            {

        	    key[i][j]=Sin*val;val*=a;

        	    key[i][j+1]=Cos*val;val*=a;

        	    key[i][j+2]=-Sin*val;val*=a;

        	    key[i][j+3]=-Cos*val;val*=a;

    	    }

        }

        else if(x==2)

        {

            D val=exp(b);key[i][0]=val;

       		for (int j=1;j<=lim;++j)val*=a,key[i][j]=val;

        }

        else{key[i][0]=b,key[i][1]=a;}

    }

    while(m--)

    {

        scanf("%s",typ);

        if(typ[0]=='a'){int u=read()+1,v=read()+1;link(u,v);}

        else if(typ[0]=='d'){int u=read()+1,v=read()+1;cut(u,v);}

        else if(typ[0]=='m')

        {

            int c=read()+1,f=read();D a,b;scanf("%lf%lf",&a,&b);

            splay(c);

            rep(i,0,lim)key[c][i]=0;

            if(f==1)

            {

                D val=1,Sin=sin(b),Cos=cos(b);

                for(int j=0;j<=lim;j+=4)

                {

            	    key[c][j]=Sin*val;val*=a;

            	    key[c][j+1]=Cos*val;val*=a;

            	    key[c][j+2]=-Sin*val;val*=a;

            	    key[c][j+3]=-Cos*val;val*=a;

        	    }

            }

            else if(f==2)

            {

                D val=exp(b);key[c][0]=val;

           		for (int j=1;j<=lim;++j)val*=a,key[c][j]=val;

            }

            else{key[c][0]=b,key[c][1]=a;}

            pu(c);

        }

        else if(typ[0]=='t')

        {

            int u=read()+1,v=read()+1;D x,now=1.0,ans=0;scanf("%lf",&x);

            int f=getrd(u,v);

            if(!f)puts("unreachable");

            else

            {

                rep(i,0,lim)ans+=sum[f][i]*now/po[i],now*=x;

                printf("%.8e\n",ans);

            }

        }

    }

    return 0;

}

巴特西

并不对劲的bzoj5020:loj2289:p4546:[THUWC2017]在美妙的数学王国中畅游

题目大意

题解

代码

最新文章

热门文章