首页 > 其他分享 >线段树 2

线段树 2

时间:2023-12-23 14:55:06浏览次数:39  
标签:lazy lazy2 cdot 线段 初始值 先乘 节点

由于有两个操作,我们要对乘法和加法设置一个优先级

我们来看看先乘后加,lazy2表示乘数,lazy1表示加数(前者初始值为\(1\),后者初始值为\(0\))

根据我们对lazy的理解,一个节点的和的真实值,为这个节点到根节点的路径中,对每一个节点依次先乘lazy2再加lazy1得到的最终结果

假设某一步时,和的中间结果为\(x\)

那么接下来,他就会变成\(y=x \cdot lazy_2+lazy_1\),再走一步就会变成\(z=y \cdot lazy_2^{'}+lazy_1^{'}=x \cdot lazy_2 \cdot lazy_2^{'}+lazy_1 \cdot lazy_2^{'}+lazy_1^{'}\)

所以在下传的时候,我们有\(lazy_2 \times = lazy_2^{'}\),\(lazy_1=lazy_1 \times lazy_2^{'}+lazy_1^{'}\)

具体可见洛谷提交代码

为什么先加后乘不行呢?

可以尝试一下按照上面的方法列式子,最终会列出来一个分数

标签:lazy,lazy2,cdot,线段,初始值,先乘,节点
From: https://www.cnblogs.com/dingxingdi/p/17923120.html

相关文章

  • 线段上离p最近的点 - 投影方式
    点到线段的最近距离判断依据1)投影结果<0,则线段端点a离p最近2)投影结果>线段ab的长度,则线段端点b离p最近3)否则p在线段上的垂点为最近点 p与ab不共线时1)p在线段两侧2-a)p在线段内侧2-b)p在线段内侧2 p与ab共线时1) p在线段两侧 2-a)p在线段内侧2-b......
  • 吉司机线段树
    \(mxb\)为历史最大值,\(tg1,tg2,tg3,tg4\)分别对应最大值真实\(tag\),其他值真实\(tag\),最大值最大\(tag\),其它值最大\(tag\)#include<bits/stdc++.h>usingnamespacestd;#defineN500005#defineintlonglongintn,m;inta[N];structTREE{ intsum[N*4],mxb[N......
  • 线段树与历史最值和区间最值问题
    线段树与历史最值问题P4314CPU监控Description给定数组\(\{a_i\}\),维护以下操作。定义一个辅助数组\(\{b_i\}\),每次操作完后令\(b_i=\max(a_i,b_i)\)。查询\(\max_{i=l}^{r}a_i\)(区间最值)查询\(\max_{i=l}^{r}b_i\)(历史最值)\(\foralli\in[l,r]\),\(a_i\gets......
  • syoj.1827. 线段传送带题解
    前情提要-三分1827.线段传送带P2571[SCOI2010]传送带省流:三分套三分。在二维平面上有两个传送带,一个从A点到B点,一个从C点到D点,速度分别是p和q,在平面内其他点的速度为r。求A点到D点的最小速度。考虑从A到D的路程一定是\(AE+EF+FD\),即通过这两个点连......
  • 线段树详解
    定义什么是线段树线段树是一种二叉搜索树,每个节点都存储了一个区间的问题。能够解决的问题序列维护修改以及查询区间上的最值、求和等,修改和查询的时间复杂度为\(O\)(\(log\)\(n\))。与其他RMQ算法的区别算法适用范围优点缺点线段树动态可执行的操作......
  • 简单线段树
    一、什么是线段树?线段树是怎样的树形结构?线段树是一种二叉搜索树,每个结点都存储了一个区间,也可以理解成一个线段,你要从这些线段上进行搜索操作得到你想要的答案。线段树能够解决什么样的问题?线段树的适用范围很广,可以在线维护修改以及查询区间上的最值,求和。......
  • CF1784C Monsters (hard version) 题解 线段树
    题目链接:https://codeforces.com/problemset/problem/1784/C题目大意:你面前有\(n\)只怪兽,每只怪兽都有一个初始血量,你可以进行两类操作:操作1:选择任意一个血量大于\(0\)的怪兽,并将它的血量降低\(1\);操作2:将所有存活的怪物的血量各自减去\(1\),如果存在怪物的血量恰好降为......
  • 线段树
    线段树什么是线段树线段树(英语:Segmenttree)是一种二叉树形数据结构,1977年由JonLouisBentley发明[1],用以存储区间或线段,并且允许快速查询结构内包含某一点的所有区间。一个包含n个区间的线段树,空间复杂度为O(n),查询的时间复杂度则为O(logn+k)},其中k是匹配条件的区间数量。此......
  • 【UVCAD】- 多段线教程,及与线段的区别
    【UVCAD】手机二维CAD建模,不止是看图UVCAD专注于二维(2D)的移动计算机辅助绘图(CAD)。UVCAD具有触摸优化的直观界面和工具。使用UVCAD,您可以在触摸屏上用手指或铅笔进行真正的2D绘图、2D建模和2D设计。对于需要易于使用的工具来更快、更精确地创建图纸的设计师和绘图员来说,UVC......
  • 刷题 ST表、单调栈、线段树->区间最值
    2023.12.13cf1904D2解题思路首先,a[i]大于b[i]时肯定不行,等于就满足了,直接过掉其次,要想使得a[i]等于b[i],就要在a[i]左右找最近的j使得a[j]=b[i](最近的最优,可证)k是i和j中间的一个数,想要满足题意,要满足以下两个条件(a[j]=b[i])1.ak<aj,即max(区间[i,j]中的ak)2.bk>bi,即min(区间......