Leven_

数据结构---...

2019寒假集训系列(6) 2019春季假集训系列(9) 2019暑期集训系列(12) BZOJ——来自hzwer的千题计划(19) DP------区间DP(5) DP------悬线法(2) DP------树形DP(1) DP------概率期望(2) DP------线性DP(5) 【专题系列】(4) 搜索------剪枝(4) 数据结构------分块(1) 数据结构------树剖(2) 数论、数学(5) 未归档(1) 模拟(3) 游记(2) 牛客网(1) 算法------TARJAN(1) 算法------二分答案(1) 算法------并查集(1) 算法------最短路(1) 算法------贪心(2) 算法------高斯消元(3) 题解(2)

/ 注册

全部文章 / 数据结构------线段树（共8篇）

【LOJ#10115,tyvj1473】校门外的树（第3次升级）

PS：思路来源于Clove_unique的博客，在此万分感谢这道题可以用树状数组轻松过，然而...树状数组不太熟悉，还是用线段树比较好（虽然代码比较长）【思路分析】【一开始的思路】最开始的错误想法：当作一般的区间覆盖题来做（顺便吐槽了一波这题太睿（ruo）智了），但写到一半突然发现，...

线段树

2018-08-24

0 515

【NOI2016】区间

这道题作为NOI的题目还算是比较水的（虽然是第一题）这道题是区间操作，不难看出可以用线段树做【思路分析】由于数据很大，我们先进行离散化，然后按区间长度排序并建一棵空树(维护当前区间重合部分最大值) 根据该线段树维护的结果，我们可以知道t[1].sum记录的是当前各条线段重合的最大值，只要...

线段树

2018-08-22

0 688

归并排序及拓展—逆序对

归并排序时间复杂度归并排序时间复杂度为O(NlogN) 似乎和快速排序差不多，但在有些特定的场合下，归并排序却能起到快速排序达不到的效果（如一年的联赛题，瑞士轮）思路及实现归并排序分为两个步骤，分、合；分的过程我们用二分的思路实现；合的过程时间复杂度可达到O(n); 分： ...

归并排序线段树

2018-08-20

0 555

【转载】线段树题目2

1.hdu1166 敌兵布阵更新节点,区间求和。 2.hdu1754 I Hate It 更新节点,区间最值. . 3.hdu1698 Just a Hook 成段更新,总区间求和. . 4.hdu1394 Minimum Inversion Number 更新节点,区间求和 . 5.hd...

线段树

2018-08-20

1 564

【转载】线段树区间合并小结

原地址：https://blog.csdn.net/sunyutian1998/article/details/79618316 个人感觉区间合并是线段树各种应用中变形最多也是比较难琢磨的一种 (以下以求01序列中最长连续1为例) tree[cur].left代表以区间左端点为起点的连续段的...

线段树线段树的区间合并

2018-08-20

0 656

【HDU1698】 Just a Hook 【线段树入门】

原题：原题链接题意：（机器翻译的...）让我们将钩子的连续金属棒从1到N编号。对于每次操作，Pudge可以将连续的金属棒（从X到Y编号）改为铜棒，银棒或金棒。钩的总值计算为N个金属棒的值的总和。更确切地说，每种棒的值计算如下：对于每个铜棒，值为1. 对于每个银棒，值为2. 对于每个金棒，值...

线段树

2018-08-20

0 483

【权值线段树】离散化介绍（+利用线段树求逆序对）

先介绍一下离散化桶排大家应该知道，就是开一个数组（下标为数值，记录了该数值的出现次数）然后遍历过去如果出现次数不为零，那就输出这些数字，理论时间复杂度可以达到O(N)但是由于内存限制，不能开很大的数组。然而如果某个数列中的数字不要求大小确定，只要求这些数字有相对的大小就够了的话，离散化就有了...

线段树离散化

2018-08-20

0 550

题解 UVA10587 【Mayor's posters】

先讲一下：dalao @lisuier 发布的前一篇题解严格来讲是有错误的比如下一组数据： 1 3 1 10 1 4 7 10 显然答案是3，然而用lisuier dalao的程序做出来的答案是2（后面会讲错误原因）简单看出这道题用线段树可解 so 我们用离散化+权值线段树（戳这里详解...

线段树

2018-08-20

0 417