https://www.zybuluo.com/ysner/note/1242005
题面
数学王国有(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 nleq100,mleq200)
- (20pts) 不存在(2)操作，(u=v-1)，(x=1)
- (5pts) 不存在(2)操作，(x=1)
- (10pts) (x=1)
- (30pts) 不存在(2)操作，(u=v-1)
- (100pts) (nleq10^5,mleq2*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
",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)=asin(ax+b)$$$$sin''(ax+b)=-a^2sin(ax+b)$$$$sin'''(ax+b)=-a^3sin(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
",ans);
}
}
return 0;
}