网站建设那个网站好,项目管理流程,河南郑州汽车网网站建设,做英语教具的网站bzoj2631#xff08;权限题。。。#xff09;:链接 落咕:链接 考察的是LCT维护链上信息。 但是这个题不一样的是又有加法又有乘法。。。#xff08;有木有想到落咕的模板——线段树2qwq#xff09; 因为乘法的运算优先度比加法高#xff0c;所以我们要先做乘法再做加法权限题。。。:链接 落咕:链接 考察的是LCT维护链上信息。 但是这个题不一样的是又有加法又有乘法。。。有木有想到落咕的模板——线段树2qwq 因为乘法的运算优先度比加法高所以我们要先做乘法再做加法证明去看线段树2的题解吧push_down的时候要注意一下。 处理一条路径的时候直接split拉出来然后在根节点进行修改就行了push_down的时候会把它的标记传递下去也就完成了一条路径上的加乘操作。 注意计算乘法的时候别忘了*1ll因为有可能爆int好吧作为惯例一般涉及到乘法再取模操作的时候中间都要加一个强制类型转换防止爆int qwqwq 最后还有一个坑点数据输入的时候有乘0的情况所以我们在push_down的时候判断有没有乘法标记不能写if(t[x].mul1)正确写法应该是if(t[x].mul!1)。。。。 代码如下 #includeiostream
#includecstdio
#includecstring
#includealgorithm
#define MAXN 100010
#define mod 51061
using namespace std;
int n,m,tot;
int s[MAXN];
struct Node{int add,mul,v,rev,son,sum,ff,ch[2];}t[MAXN];
inline void push_up(int x)
{t[x].sum(t[t[x].ch[0]].sumt[t[x].ch[1]].sumt[x].v)%mod;t[x].sont[t[x].ch[0]].sont[t[x].ch[1]].son1;
}
inline bool isroot(int x){return t[t[x].ff].ch[0]!xt[t[x].ff].ch[1]!x;}
inline void rotate(int x)
{int yt[x].ff;int zt[y].ff;int kt[y].ch[1]x;if(!isroot(y)) t[z].ch[t[z].ch[1]y]x; t[x].ffz;t[y].ch[k]t[x].ch[k^1]; t[t[x].ch[k^1]].ffy;t[x].ch[k^1]y; t[y].ffx;push_up(y),push_up(x);
}
inline void Mul(int x,int k)
{t[x].mul1ll*t[x].mul*k%mod;t[x].add1ll*t[x].add*k%mod;t[x].v1ll*t[x].v*k%mod;t[x].sum1ll*t[x].sum*k%mod;
}
inline void Add(int x,int k)
{t[x].add(t[x].addk)%mod;t[x].v(t[x].vk)%mod;t[x].sum1ll*k*t[x].son%mod,t[x].sum%mod;
}
inline void push_down(int x)
{if(t[x].rev){if(t[x].ch[0]) t[t[x].ch[0]].rev^1;if(t[x].ch[1]) t[t[x].ch[1]].rev^1;swap(t[x].ch[0],t[x].ch[1]);t[x].rev^1;}if(t[x].mul!1){if(t[x].ch[0]) Mul(t[x].ch[0],t[x].mul);if(t[x].ch[1]) Mul(t[x].ch[1],t[x].mul);t[x].mul1;}if(t[x].add){if(t[x].ch[0]) Add(t[x].ch[0],t[x].add);if(t[x].ch[1]) Add(t[x].ch[1],t[x].add);t[x].add0;}
}
inline void splay(int x)
{s[tot1]x;for(int ix;!isroot(i);it[i].ff) s[tot]t[i].ff;while(tot) push_down(s[tot--]);while(!isroot(x)){int yt[x].ff;int zt[y].ff;if(!isroot(y))((t[y].ch[0]x)^(t[z].ch[0]y))?rotate(x):rotate(y);rotate(x);}
}
inline void access(int x)
{for(int y0;x;yx,xt[x].ff)splay(x),t[x].ch[1]y,push_up(x);
}
inline void makeroot(int x){access(x);splay(x);t[x].rev^1;}
inline void split(int x,int y){makeroot(x);access(y);splay(y);}
inline void cut(int x,int y){split(x,y);t[y].ch[0]t[x].ff0;push_up(y);}
inline void link(int x,int y){makeroot(x);t[x].ffy;}
inline int findroot(int x)
{ access(x);splay(x);while(t[x].ch[0]) xt[x].ch[0];return x;
}
int main()
{#ifndef ONLINE_JUDGEfreopen(ce.in,r,stdin);#endifscanf(%d%d,n,m);for(int i1;in;i){int u,v;scanf(%d%d,u,v);link(u,v);}for(int i1;in;i) t[i].sont[i].mult[i].v1;for(int i1;im;i){char op;int u,v,c,u2,v2;scanf(%c,op),scanf(%c,op);if(op){scanf(%d%d%d,u,v,c);split(u,v);Add(v,c);}else if(op-){scanf(%d%d%d%d,u,v,u2,v2);cut(u,v);link(u2,v2);}else if(op*){scanf(%d%d%d,u,v,c);split(u,v);Mul(v,c);}else{scanf(%d%d,u,v);split(u,v);printf(%d\n,t[v].sum%mod);}} return 0;
} 转载于:https://www.cnblogs.com/fengxunling/p/10285777.html
