ordinarv
ordinarv
全部文章
分类
任务(1)
技能树(5)
归档
标签
去牛客网
登录
/
注册
2019 暑假集训
梦想有多大,所要付出的代价就要有多大
全部文章
(共6篇)
二分
二分 STL(Standard ) lower_bound() 返回第一个大于等于target的位置 upper_bound() 返回第一个大于target的位置 lower_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字,找到...
2020-09-20
0
456
BIT Interval MAX
首先,a[]数组仍然是保存原始数据。c[i]将会保存从a[1]到a[i]的最值。 单点修改时间复杂度log2(n)^2,区间查询时间复杂度log2(n) 1。单点更新: 直接更新a[i],然后再更新h[i]。若h[i]的值有可能改变的,则表示区间一定包含i结点。那么就两层lowbit更新所有...
BIT
2019-08-16
0
603
树状数组总结
目前遇到树状数组的应用有 维护区间和(单点修改、区间修改查询) 任意区间最大值 求区间第k大(比主席树占用内存小,湘潭某题)
2019-08-16
0
520
线段树
入门题 HDU 3974 Assign the task(简单线段树) HDU 1394 Minimum Inversion Number(求逆序数,线段树或者树状数组) ZOJ 1610 Count the Colors(线段树) POJ2777(区间染色) 区间第K大(二分) 矩形面积并 推...
2019-08-08
0
605
常用STL函数
lower_bound(l,r,tar) 返回区间内第一个大于等于tar的数位置upper_bound(l,r,tar) 返回区间内第一个大于tar的数位置 lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。在从小到大的排序数组中,lo...
2019-08-07
0
602
树状数组讲课
前言 首先来看一个问题:给定a数组 单点修改,询问区间和。显然我们有两种思路1.不维护任何东西,直接用a数组 O(1)修改 O(n)求和2.维护a的前缀和,O(n)修改 O(1)求和可是这两种方法都太极端了,我们想均衡一下这两种算法。观察可知 前缀和O(n)修改是因为sum[i]维护的是[1...
2019-07-26
0
632