wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共5篇）

【题解】 NC5157C 牛牛的等差数列

solution 用线段树维护即可。考虑线段树的懒标记如何维护。我们维护两个懒标记，添加到当前位置的数列在该区间开始位置的首项之和，表示这些添加的数列公差之和。因为如果往一个位置添加了一个等差数列。其中某个位置可以看作，那么再添加一个等差数列，那么该位置就可以看作，相当于添加了一个首项为公差为的等...

线段树

2020-04-19

4 1107

[hdu6183][Color it]

题目链接题目大意有一个矩阵，总共有4种操作 0:清空这个矩阵 1 x y c:将\((x,y)(1 \leq x ,y\leq 10^6)\)这个点加上一种颜色c\((0\leq c \leq 50)\)(注意是加上，也就是之前的颜色不会被覆盖) 2 x y1 y2:查询左上角为\((1,y...

动态开点线段树

2018-12-10

0 514

noi.ac89A 电梯

题目思路首先按照\(t\)排序！！！！首先考虑一个暴力\(dp\) 用\(f[i]\)表示前\(i\)个人到达地点所需要的时间。那么就有如下的转移 \[f_i = min_{1 \le j \le i}(max(f_j,t_i) + max\{w_{j + 1} ... w_...

线段树动态规划dp

2019-03-24

0 501

[hdu6183][Color it]

题目链接题目大意有一个矩阵，总共有4种操作 0:清空这个矩阵 1 x y c:将\((x,y)(1 \leq x ,y\leq 10^6)\)这个点加上一种颜色c\((0\leq c \leq 50)\)(注意是加上，也就是之前的颜色不会被覆盖) 2 x y1 y2:查询左上角为\((1,y...

动态开点线段树

2018-12-10

0 479

luogu4211 LCA

题目链接思路我们换一种求\(dep[lca(i,j)]\)的方法。将从根到\(i\)的路径上所有点的权值加\(1\)，然后求从根节点到j路径上点的权值和。就是\(i\)和\(j\)的\(lca\)的深度。以此类推，对于求\(\sum\limits_{i=l}^rdep[lca(i,z)]...

最近公共祖先线段树树链剖分

2019-01-29

0 522