你好！我的朋友们！

欢迎来到MicDZ的博客。

请使用IE，360极速浏览器访问的同学或使用较低操作系统版本的同学移步Chrome或Firefox。

部分素材来自互联网，如有侵权请与me@micdz.cn联系删除！

在NOIp来之前，赶快奶一口会出逆序对毒瘤数学题，RP++。

在面对超大数据的读入时，我们不得不面对快速的读入方式。

在上篇文章中，已经进行了详细的对线段树单点修改和区间查询的描述。

在这篇文章中将会更深入的了解线段树的区间修改。不过，在NOIp赛事中，几乎很少出现。

即将参加NOIp2018考试，在此做一个备忘录。

题目链接here

这是一道非常有思维难度和代码强度的宽搜好题。

几乎网上所有有关tarjan算法的介绍都会有下面这一段话：

Tarjan老爷子一生发明了许多算法下到 NOIP 上到 CTSC 难度的都有。

(Tarjan 算法，并查集，Splay 树，Tarjan 离线求 lca)

我们这里要介绍的是图论中的 Tarjan 算法，用来处理各种连通性相关的问题。

此题可以用动态规划求解。

以NOIp2018初赛第7题为例：

1
2
3
4
5

 7. 在一条长度为1 的线段上随机取两个点，则以这两个点为端点的线段的期望长度是（ ）。
A. 1 / 2
B. 1 / 3
C. 2 / 3
D. 3 / 5