在美妙的数学王国中畅游

数论

---

题面

数学王国有$n$座城市（森林状），每个城市有三个参数$f,a,b$，当一个智商为$x$的人经过会得到$f(x)$的收益。

• $f=1,f(x)=sin(ax+b)$
• $f=2,f(x)=e^{ax+b}$
• $f=3,f(x)=ax+b$

有$m$个事件，分为$4$类：
1、建边
2、断边
3、修改一个城市的参数
4、询问一个智商为$x$的人，判断是否联通，若联通则答从$u$到$v$的收益和。

（除最下一档，各档分互不包含）

• $5pts\ n\leq100,m\leq200$
• $20pts$ 不存在$2$操作，$u=v-1$，$x=1$
• $5pts$　不存在$2$操作，$x=1$
• $10pts$　$x=1$
• $30pts$　不存在$2$操作，$u=v-1$
• $100pts$ $n\leq10^5,m\leq2*10^5$

解析

“删边”这操作钦定使用$LCT$。于是一只不会lct的蒟蒻就gg啦
没有人像我一样在计算器上二分出$e=2.718281828$的吧。

$5pts$算法

我们可以用邻接矩阵维护一条边有没有被删掉。
暴力修改。
询问收益就从$u$出发对全图$dfs$。
复杂度$O(mn^2)$

$5+20pts$算法

不需要删边，判连通性就可以并查集了。

$x=1$代表可以$O(n)$预处理出每个城市收益。
询问就是问一条链上的区间和。
用树状数组维护前缀和即可做到$O(logn)$查询与修改。
总复杂度$O(qlogn)$

il void BL2()
{
  fp(i,1,n) ff[i]=i;
  fp(i,1,n)
    {
      if(f[i]==1) w[i]=sin(a[i]+b[i]);
      if(f[i]==2) w[i]=pow(E,a[i]+b[i]);
      if(f[i]==3) w[i]=a[i]+b[i];
      Add(i,w[i]);
    }
  while(m--)
    {
      cin>>op;re int u,v;
      if(op[0]=='a')
    {
      cin>>u>>v;++u;++v;
          ff[find(v)]=find(u);
    }
      if(op[0]=='m')
    {
      cin>>u;++u;cin>>f[u]>>a[u]>>b[u];
      re double las=w[u];
      if(f[u]==1) w[u]=sin(a[u]+b[u]);
          if(f[u]==2) w[u]=pow(E,a[u]+b[u]);
          if(f[u]==3) w[u]=a[u]+b[u];
      Add(u,w[u]-las);
    }
      if(op[0]=='t')
    {
      cin>>u>>v>>x;++u;++v;if(u>v) swap(u,v);
      if(find(u)!=find(v)) puts("unreachable");
      else printf("%.9Lf\n",Query(v)-Query(u-1));
    }
    }
}

$5+20+5pts$算法

这是个森林，不太好搞出$dfs$序,于是应该只能上$LCT$。

$5+20+5+10$算法

怕是$LCT$模板。

$5+20+30$算法

注意到题目最下方有一个奇奇怪怪的公式。
那个玩意儿能够方便地近似将$f(x_0)$转化为$f(x)$。

题目中$x=1$这一条件显然能给我们以启迪。
如果我们一开始预处理所有的$f(0)$，我们在询问时就可以先得到$\sum f(0)$，再在常数时间内将$\sum f(0)$转化为答案$\sum f(x)$。

但是对一个不会求导的高一学生就很伤了：

$$(a^x)'=a^x*\ln a$$ $$(e^x)'=e^x$$ $$(a+b)'=a'+b'$$ $$(ab)'=ab'+a'b$$ $$(x^a)'=ax^{a-1}$$ $$b'=0$$ ($b$为常数）
$$(\sin x)'=\cos x$$ $$(\cos x)'=-\sin x$$ $$(-\sin x)'=-\cos x$$ $$(-\cos x)'=\sin x$$
（周期！）
对复合函数： $$[f(g(x))]'=g(x)'*f(g(x))'$$
代入这道题
对三角函数：
$$\sin'(ax+b)=a\sin(ax+b)$$ $$\sin''(ax+b)=-a^2\sin(ax+b)$$ $$\sin'''(ax+b)=-a^3\sin(ax+b)$$
对自然对数幂次方： $$(e^{ax+b})'=(ax+b)'*(e^{ax+b})'$$ $$=((ax)'+b')*e^{ax+b}$$ $$=a*e^{ax+b}$$
则 $$(e^{ax+b})^{(n)}=a^ne^{ax+b}$$ $(n)$代表$n$阶导数。
对一次函数： $$(ax+b)'=(ax)'+b'=ax'+a'x=a$$
(一阶导数就是斜率）
于是代入公式即可得解。

$100pts$算法

用$LCT$维护信息。

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define M 15
#define eps 1e-12
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=5e5+100;
const double E=2.718281828;
int n,m,f[N],ff[N],t[N][2],st[N];
bool r[N];
double a[N],b[N],ans,x,sum[20][N],jc[N],ssin[N],ccos[N];
char c[10],op[20];
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il double Sin(re int u,re double x)
{
  if(ssin[u]>-eps&&ssin[u]<eps) return ssin[u]=sin(x);
  else return ssin[u];
}
il double Cos(re int u,re double x)
{
  if(ccos[u]>-eps&&ccos[u]<eps) return ccos[u]=cos(x);
  else return ccos[u];
}
il bool isrt(re int u){return t[f[u]][0]==u||t[f[u]][1]==u;}
il void pushup(re int u)
{
  fp(i,0,M) sum[i][u]=sum[i][t[u][0]]+sum[i][t[u][1]];
  if(ff[u]==1)
    {
      double tmp=1;
      fp(i,0,M)
    {
      if(i%4==0) sum[i][u]+=Sin(u,b[u])*tmp;
      if(i%4==1) sum[i][u]+=Cos(u,b[u])*tmp;
      if(i%4==2) sum[i][u]+=-Sin(u,b[u])*tmp;
      if(i%4==3) sum[i][u]+=-Cos(u,b[u])*tmp;
      tmp*=a[u];
    }
    }
  if(ff[u]==2)
    {
      double w=pow(E,b[u]);sum[0][u]+=w;
      fp(i,1,M) w*=a[u],sum[i][u]+=w;
    }
  if(ff[u]==3)
    sum[0][u]+=b[u],sum[1][u]+=a[u];
}
il void pushr(re int u)
{
  swap(t[u][0],t[u][1]);r[u]^=1;
}
il void pushdown(re int u)
{
  if(r[u])
    {
      if(t[u][0]) pushr(t[u][0]);if(t[u][1]) pushr(t[u][1]);
      r[u]=0;
    }
}
il void rotate(re int x)
{
  re int y=f[x],z=f[y],k=t[y][1]==x,v=t[x][!k];
  if(isrt(y)) t[z][t[z][1]==y]=x;t[x][!k]=y;t[y][k]=v;
  if(v) f[v]=y;f[y]=x;f[x]=z;
  pushup(y);
}
il void splay(re int u)
{
  re int v=u,top=0;
  st[++top]=v;
  while(isrt(v))  st[++top]=v=f[v];
  while(top) pushdown(st[top--]);
  while(isrt(u))
    {
      v=f[u];top=f[v];
      if(isrt(v)) rotate((t[v][0]==u)^(t[top][0]==v)?v:u);
      rotate(u);
    }
  pushup(u);
}
il void access(re int u)
{
  for(re int v=0;u;u=f[v=u])
    {
      splay(u),t[u][1]=v,pushup(u);
    }
}
il void makert(re int u)
{
  access(u);splay(u);pushr(u);
}
il int findrt(re int u)
{
  access(u);splay(u);while(t[u][0]) pushup(u),u=t[u][0];//
  return u;
}
il void split(re int u,re int v)
{
  makert(u);access(v);splay(v);
}
il void link(re int u,re int v)
{
  makert(u);
  if(findrt(v)!=u) f[u]=v;
}
il void cut(re int u,re int v)
{
  split(u,v);//
  f[u]=t[v][0]=0;pushup(v);
}
int main()
{
  freopen("math.in","r",stdin);
  freopen("math.out","w",stdout);
  ios::sync_with_stdio(false);
  jc[0]=1;
  fp(i,1,M) jc[i]=jc[i-1]*i;
  cin>>n>>m>>c;
  fp(i,1,n) cin>>ff[i]>>a[i]>>b[i];
  while(m--)
    {
      re int u,v,w;
      cin>>op;
      if(op[0]=='a') cin>>u>>v,++u,++v,link(u,v);
      if(op[0]=='d') cin>>u>>v,++u,++v,cut(u,v);
      if(op[0]=='m') cin>>u,++u,makert(u),cin>>ff[u]>>a[u]>>b[u],ssin[u]=0,ccos[u]=0,pushup(u);
      if(op[0]=='t')
    {
      cin>>u>>v>>x;++u;++v;re double  tmp=1;
      if(findrt(u)^findrt(v)) {puts("unreachable");continue;}
      split(u,v);ans=0;
      fp(i,0,M) ans+=sum[i][v]*tmp/jc[i],tmp*=x;
      printf("%.8e\n",ans);
    }
    }
  return 0;
}