夢に僕らで帆を張って
来るべき日のために夜を超え

标签 线段树 下的文章

November 5, 2019

洛谷P1505/国家集训队 旅游

题意给出一颗有边权的树,有$5$种操作:覆盖一条边的边权将$u$到$v$路径上的边权变为相反数询问$u$到$v$路径上的边权和询问$u$到$v$路径上的边权最大值询问$u$到$v$路径上的边权最小值数据范围:$n,m \le 20000$题解考虑将边权下放,随后此问题可用树链剖分解决线段树维护和,最大值,最小值及相反数标记区间处理的时候注意是否处理到$\text{LCA}$代码:#inclu...
November 4, 2019

洛谷P3313/SDOI2014 旅行

题意略数据范围:$n,q,c \le 10^5$题解由于要对每个宗教开一个线段树维护,空间过大,考虑动态开点线段树每颗线段树维护最大值以及区间和,对于修改操作,直接删除并新建节点之后在树剖上进行即可代码:#include<iostream> #include<cstdio> #include<algorithm> using namespace std; ...
November 3, 2019

洛谷P4979 矿洞:坍塌

题意给出一个字符串,$2$种操作区间覆盖询问是否区间内相同,两端不同数据范围:$n,k \le 500000$题解容易想到用线段树维护每个区间的颜色,相同则为原值,不同则为此外的值(如'0')注意询问的判断条件代码:#include<iostream> #include<cstdio> using namespace std; #define ls rt<<...
October 31, 2019

CF786B Legacy

题意有$3$种连边方式$u \rightarrow v$ 点向点$u \rightarrow [l,r]$ 点向区间$[l,r] \rightarrow u$ 区间向点求从$s$出发的最短路数据范围:$1 \le n,q \le 10^5$题解显然对于向区间建边不能一个一个建,那么能不能直接向整个区间建边呢?联想到线段树的一个节点维护一个区间的信息,那么可以向这个节点建边;这便是线段树优化建...
October 29, 2019

洛谷P4243/JSOI2009 等差数列

题意给出一个数列,有$2$种操作$A \ s \ t \ a \ b$ 在区间$[s,t]$上加上初值为$a$,公差为$b$的等差数列$B \ s \ t$ 询问区间$[s,t]$最少分成几段,使得每一段都是等差数列对于每个询问,输出答案数据范围:$1 \le n,m \le 100000,-100000 \le a,b \le 100000$题解由于维护的是等差数列,首先转化成差分$$d[...
October 29, 2019

洛谷P4315 月下“毛景树”

题意给出一颗有边权的树,有$4$种操作覆盖一条边的边权覆盖$u$到$v$路径上的边权增加$u$到$v$路径上的边权询问$u$到$v$路径上的边权最大值对于每个询问,输出答案数据范围:$1 \le n \le 100000$题解考虑将边权下放,随后此问题可用树链剖分解决注:由于边权下放,树上处理的最后一次(即在同一条链的情况下)需要将处理的左端点$+1$以避免处理到其$\mathrm{LCA}...
October 29, 2019

洛谷P5142 区间方差

题意给出一个数列,$2$种操作单点修改询问区间方差以上操作在$\bmod \ 10^9+7$意义下数据范围:$n,m \le 100000$题解首先方差$$\sigma^2 =\frac{1}{n} \sum_{i=1}^n (x_i-\bar{x})^2$$其中$$\bar{x}=\frac{1}{n} \sum_{i=1}^n x_i$$不满足区间和性质,将其拆开$$ \begin{al...
October 28, 2019

洛谷P1937/USACO10MAR 仓配置Barn Allocation

题意有$n$个点,$m$条线段,每个点最多被覆盖$c_i$次,求最多选择几条线段数据范围:$1 \le n,m,c_i \le 100000$题解先按右端点为第一关键字升序,左端点为第二关键字降序排序随后按顺序选择区间,能选则选正确性证明:在右端点相同时,显然左端点越大区间长度越短,结果越优在右端点不同时,对于先选择的区间$i$与和$i$发生冲突的区间$j$,需要讨论的情况为$$l_i &l...