温州市手机网站制作,网店运营计划书范文,镇江一网推网络技术有限公司,建立网站有哪几种方式[国家集训队] Tree II
一道真板子题
就是练习LCT懒标记的题目
除了翻转标记以外还要维护乘法标记和加法标记
注意加法标记和乘法标记的维护#xff01;#xff01;#xff01;
加法标记
因为splay的区间大小不是固定的#xff0c;所以我们要维护size#xff0c;并且…[国家集训队] Tree II
一道·真·板子·题
就是练习LCT懒标记的题目
除了翻转标记以外还要维护乘法标记和加法标记
注意加法标记和乘法标记的维护
加法标记
因为splay的区间大小不是固定的所以我们要维护size并且子树的sum要加上size乘上标记
其他的就只用直接加上即可
void pushadd(ll x,ll c){t[x].sum(t[x].sumt[x].sz*c%P)%P;t[x].val(t[x].valc)%P;t[x].add(t[x].addc)%P;
}乘法标记
由于乘法的优先级要大于加法
所以我们的加法标记也要乘上乘法标记值
void pushmul(ll x,ll c){t[x].sumt[x].sum*c%P;t[x].valt[x].val*c%P;t[x].mult[x].mul*c%P;t[x].addt[x].add*c%P;
}注意int过不了
CODE
#includebits/stdc.h
#define ll long long
using namespace std;
const ll N1e52,P51061;
ll n,q,s[N];
struct node{ll ch[2],p,sum,tag,sz,val,mul,add;}t[N];
void pushtag(ll x){swap(t[x].ch[0],t[x].ch[1]);t[x].tag^1;
}
void pushmul(ll x,ll c){t[x].sumt[x].sum*c%P;t[x].valt[x].val*c%P;t[x].mult[x].mul*c%P;t[x].addt[x].add*c%P;
}
void pushadd(ll x,ll c){t[x].sum(t[x].sumt[x].sz*c%P)%P;t[x].val(t[x].valc)%P;t[x].add(t[x].addc)%P;
}
void pushup(ll x){t[x].sum(t[t[x].ch[0]].sumt[x].valt[t[x].ch[1]].sum)%P;t[x].szt[t[x].ch[0]].szt[t[x].ch[1]].sz1;
}void pushdown(ll x){if(t[x].mul!1){pushmul(t[x].ch[0],t[x].mul);pushmul(t[x].ch[1],t[x].mul);t[x].mul1;}if(t[x].add){pushadd(t[x].ch[0],t[x].add);pushadd(t[x].ch[1],t[x].add);t[x].add0;}if(t[x].tag){pushtag(t[x].ch[0]);pushtag(t[x].ch[1]);t[x].tag0;}
}
bool isrt(ll x){//判断节点x是否是当前实树的根return t[t[x].p].ch[0]!xt[t[x].p].ch[1]!x;
}
void rotate(ll x){//x上旋 ll yt[x].p,zt[y].p;ll k(t[y].ch[1]x);//x原来的位置 if(!isrt(y)) t[z].ch[(t[z].ch[1]y)]x;//x代替y位置 t[x].pz;t[y].ch[k]t[x].ch[k^1];t[t[x].ch[k^1]].py;t[x].ch[k^1]y;t[y].px;pushup(y);pushup(x);
}
void splay(ll x){//x上旋到根 ll top0,rx;s[top]r;while(!isrt(r)){s[top]rt[r].p;}while(top) pushdown(s[top--]);while(!isrt(x)){ll yt[x].p,zt[y].p;if(!isrt(y)){//y不为目标位置 if((t[y].ch[1]x)^(t[z].ch[1]y)) rotate(x);//不在同一直线上 else rotate(y);//在同一直线上 }rotate(x);}
}
void access(ll x){// 把根节点到x的路径上的边全部变为实边同时将x变成splay的根节点ll zx;for(ll y0;x;yx,xt[x].p){splay(x);t[x].ch[1]y;//右子树 pushup(x);}splay(z);
}
void makert(ll x){// 将x变成原树的根节点access(x);//打通一条从根到x的路径 然后将x旋到根 //首先 打通一条从根到x的路径 后 x 是 d最大的点 //因此 此时x必然是Splay中中序遍历最后得到的点 pushtag(x);//翻转Splay x成为 中序遍历 第一个点-即原树根节点
}
ll findrt(ll x) {// 找到x所在原树的根节点, 再将原树的根节点旋转到splay的根节点access(x);//x与原树根在同一splay内//由于每个Splay中维护的节点按中序遍历得到的顺序在原树中深度依次增加1//所以根节点必然是Splay中序遍历顺序为1的节点while(t[x].ch[0]){pushdown(x);xt[x].ch[0];}//路径深度最小 splay(x);return x;
}
void split(ll x,ll y){ // 给x和y之间的路径建1个splay其根节点是ymakert(x);access(y);
}
void link(ll x,ll y){//如果x和y不连通,加1条x和y之间的边makert(x);// 将x作为它所在树的根if(findrt(y)!x){//不连通 t[x].py;//更新x的父亲为y}
}
bool back(ll x,ll y){//y是否是x的后继 return t[x].ch[1]y!t[y].ch[0];
}
void cut(ll x,ll y){// 如果x和y之间存在边则删除该边split(x,y);//只剩下x-y,x是y的做儿子 if(t[x].ch[1]||t[x].p!y||t[y].ch[1])return ;t[t[y].ch[0]].p0;t[y].ch[0]0;
}
int main(){scanf(%lld%lld,n,q);for(ll i1;in;i){t[i].valt[i].szt[i].mul1;}for(ll i1,x,y;in;i){scanf(%lld%lld,x,y);link(x,y);}for(ll i1;iq;i){char op[10];ll x,y,k;scanf(%s,op);if(op[0]){scanf(%lld%lld%lld,x,y,k);split(x,y),pushadd(y,k);}else if(op[0]-){scanf(%lld%lld,x,y);cut(x,y);scanf(%lld%lld,x,y);link(x,y);}else if(op[0]*){scanf(%lld%lld%lld,x,y,k);split(x,y),pushmul(y,k);}else{scanf(%lld%lld,x,y);split(x,y);printf(%lld\n,t[y].sum);}}return 0;
} 完结撒花❀ ★,°:.☆(▽)/$:.°★ 。
