在美妙的数学王国中畅游

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\ 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; }

转载于:https://www.cnblogs.com/yanshannan/p/9439150.html

总结

以上是生活随笔为你收集整理的在美妙的数学王国中畅游的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。