`
444878909
  • 浏览: 631552 次
文章分类
社区版块
存档分类
最新评论

线段树专题【陆续更新中】

 
阅读更多


【单点更新】

第一题 hdu 1166 敌兵布阵

点击打开链接hdu 1166

思路: 线段树单点更新

分析:

1 题目给定n个兵营的人数,现在有三种操作

(1) Add i j,i和j为正整数,表示第i个营地增加j个人(j不超过30)
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人(j不超过30);
(3)Query i j ,i和j为正整数,i<=j,表示询问第i到第j个营地的总人数;

2 最简单的线段树单点更新的题目

点击查看代码


第二题 hdu 1754I Hate It

点击打开链接hdu 1754

思路: 线段树+单点更新

分析:

1 线段树的水题

点击查看代码


第三题 hdu 1394 Minimum Inversion Number

点击打开hdu 1394

思路: 线段树+单点更新

分析:

1 题目要求的是n个数的n个序列中找到的最小逆序数对

2 首先我们都知道所谓的逆序数对就是给一个序列,如果前面的数比当前的数大,那么这两个数就是逆序数对。比如4 1 3 2中逆序数有 4 1, 4 3, 4 2, 3 2

3 那么我们可以很快的利用线段树求出起始数组的逆序数对,那么我们接下来考虑把第一个数换到最后一个位置的情况

假设现在起始的序列的逆序数对有sum,那么第一个数num[1]换到最后一个位置的后果就是使得所有比num[i]小的数度不能和num[i]构成逆序数了,那么直接减少的个数就是n-1-num[i],但是那么比num[i]大的数可以和num[i]构成逆序数,因此增加了n-num[i]个。因此换完之后的序列的逆序数对为sum-(n-1-num[i])+n-num[i];

4 因此我们只要去做n次的比较,求出的最小值即为ans

点击查看代码


第四题 hdu 2795Billboard

点击打开hdu 2795

思路: 线段树+单点更新

分析:

1 题目的意思是给定一个h*w的广告牌h为高,w为宽,现在有n个高为1宽为wi的小广告要放上去,原则是最先放最上面和最左边的位置

2 题目的h和w的最大值为10^9,但是n最大为200000。所以我们可以知道最多用掉的广告牌就是x = min(n , h),而这个值就是200000,所以我们可以把每一行作为一个点来利用线段树,线段树的区间[i , j]存储的是第i行到第j行的最大的剩余空间,那么我们只要每一次去查找整个区间[1 , x] ,然后我们要优先的考虑左子树,这样就能够满足要求的条件了

点击查看代码


第五题 poj 2481Cows

点击打开链接poj2481

思路:线段树+单点更新
分析:
1 题目给定n头牛所在的区间,然后问每头牛都有几头牛比它强壮
2 根据题目如果牛i的区间是[Si , Ei],牛j的区间是[Sj , Ej]那么牛i要比牛j强壮的话那么就有Si <= Sj && Ei >= Ej && Si-Ei != Sj-Ej;
3 那么根据上面的条件,我们应该要先对n头牛的区间排序”按照S从小到大,相同S按照E从大到小排序“,然后就可以利用线段树求了。
4 有一个地方需要注意的是当排完序后相邻的两个相等,那么只须更新不用求和。
点击查看代码


第六题 poj 2828Buy Tickets

点击打开poj 2828

思路: 树状数组/线段树单点更新

分析:

1 题目给定n个人的位置pos和id,要我们求出最后n个人的位置

2 我们先来考虑朴素的算法,假设现在进来一个人那么我们把它放到pos的位置,那么pos之后的所有的人都要向后移动一位,那么n个人的话最坏的情况是O(n^2),很显然时间效率上面是不行的

3 由于正向的插入不行,那么我们考虑反向插入的情况(就像逆向的并查集),那么我们可以马上知道第n个人的位置,那么第n-1个人的位置是基于第n个人的。假设第i个人的要插入pos的位置,那么这个时候我们只要把第i个放到第pos个空的位置即可(可以自己手动模拟一遍),那么我们维护空位置可以利用树状数组和线段树来维护

点击查看代码


第七题codeforces 19D Points

点击打开cf 19D

思路: 线段树+单点更新

分析:

1 题目的意思是给定一些点和n个操作,这些点都是在原点(0 , 0)的右边,现在给定三种操作

add x y 是把(x , y)这个点加入

remove x y 是把(x , y)这个点删除

find x y是查找(x , y)点的右边的点满足x' > x && y' > y 并且有x'和y‘尽量的小

2 题目给定的数据是n是2*10^5,但是点的最大值为10^9,所以我们应该要进行点的离散化。但是我们只要对x进行离散化即可

3 我们利用set来保存每一个x对应的y的集合,然后我们利用线段树来维护一个x区间的最大的y。

为什么要用线段树呢?因为我们知道我们只要只要当前区间的最大值就能够判断是否有没有存在这样的点,然后我们利用二分逼近的思想去求出这个x。只要我们求出了x,那么我们就可以利用之前的set来找比y大的y',这一步可以利用set的内置的lower_bound

4 有一点很重要的就是,由于set和map的存储结构不是线性的,因此它们内置了lower_bound和upper_bound,所以我们利用内置,如果使用通用的时间效率及其底下

点击打开查看代码


第八题 poj 2886Who Gets the Most Candies?

点击打开poj 2886

思路: 求因子数+单点更新

分析:

1 题目的意思是有n个人构成一个环,刚开始是第k个人先出来。每个人有一个名字和数值A,如果A为正数,那么下一个出去的人是他左边的第A个人,如果是负数那么出去的将是右边的第A个人


2 这么我们要注意一下,因为n个人是围城一圈,那么左边就是顺时针方向,右边就是逆时针方向


3 那么我们就可以来推没一次出去的人的在剩下中是第几个。

假设当前是第k个人出去,并且这个人的值为A,并且剩下有sum个人


A > 0 , 因为这个人出去了,那么后面的人的编号会先减一,那么下一个出去的人就是剩下中的 (k+A-1)%sum,因为我们知道%sum的结果是0~sum-1,但是我们要得到1~sum的结果,因此我们可以这样 ((k+A-1)%sum-1+sum)%sum+1。怎么理解呢,比如x%3,那么结果就是0~2,为了得到结果为1~3,那么我们可以这样(x-1+3)%3+1,括号里面加3怕负数的情况


A < 0 , 因为这个人出去,对前面的人是没有影响的,因此编号就是 ((k+A)%sum+sum-1+sum)%sum+1,根据上面的解释以及怕出现负数的情况,我们多加了sum来抵消


4 我们现在求出了每一次出去的人是剩下人中的第几个,但是我们怎么去求出具体的是哪一个人呢?

这个时候我们就可以利用线段树来维护,线段树的区间维护的是当前这个区间还有多少个孩子,那么我们只要查找前面求出的第几个孩子就可以得到编号

点击打开查看代码



【成段更新】



【区间合并】



【扫描线】



分享到:
评论

相关推荐

    线段树区间更新code

    线段树区间更新代码线段树区间更新代码线段树区间更新代码线段树区间更新代码

    线段树的一种实现

    一种简单的线段树的实现 ,基础功能比较完善

    pascal区间线段树

    一个讲述线段树的好资料,这里主要是程序部分,希望对广大成员能够有所帮助

    acm程序设计竞赛_培训_线段树

    浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计...

    几道经典线段树题目及代码

    线段树、线段树啊、线段树,线段树啊、线段树

    线段树模板

    线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。 使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的...

    线段树与树状数组专题讲解

    线段树与树状数组的数据结构、算法、例题,非常详细和有条理

    线段树ppt的好东东

    线段树ppt,线段树ppt,线段树ppt,树ppt,线段树ppt,线段树ppt,

    权值线段树和主席树入门

    权值线段树和主席树入门PPT,权值线段树,顾名思义就是记录权值的线段树,普通的线段树直接以坐标为l,r建树,而权值线段树是以大小来建树,树上寸的信息是该权值的数量,而通过建树时二分从小到大的性质,可以用这...

    线段树高级数据结构实现

    线段树点更新

    线段树完整版

    ACM学习中 涉及到线段树的代码分析模板

    线段树学习ppt

    线段树学习ppt

    线段树初步(C++)

    讲解线段树基本应用,适合初学者下载使用!

    点节点更新线段树

    可移植代码,用于单点更新,内有代码移植及运用的详解

    线段树.pdf

    线段树完全版,涉及到线段树的所有用法。 包括单点更新(增减,替换),区间求和,区间最值。 区间求最大值的位置。 成段更新(延迟标记,增减)。 离散化 扫描线

    线段树六题

    著名的线段树六题 囊括线段树整个知识点, 十分实用 当年凭借此六题, NOIP+NOI秒杀线段树题

    线段树模板 zoj1128

    本资源是对线段树操作比较完整的操作,包括线段树的动态插入,动态删除和维护,可以查询区段的最大值,最小值,完成线段树的基本操作。

    线段树中文教程【信息技术竞赛】

    线段树结构英文介绍,by failedbamboo

    线段树PPT两个,所有常规用法

    线段树PPT,所有常规用法线段树PPT,所有常规用法线段树PPT,所有常规用法线段树PPT,所有常规用法

    线段树——在ACM中制胜的法宝

    主要介绍线段树,并介绍其数据结构,还有相关的例题分析

Global site tag (gtag.js) - Google Analytics