6 岩之痕

尚未进行身份认证

暂无相关简介

等级
TA的排名 2w+

Codeforces 739C.Alyona and towers (线段树/非递归线段树)

题目链接:http://codeforces.com/contest/739/problem/C题意:给定30万个正整数,和30万个操作,每次操作后输出查询结果。操作:每次把从L到R的数都加上D查询:最宽的Hill的宽度。定义:先递增后递减的连续n个数称作宽度为n的Hill。

2016-12-07 12:24:38

线段树从零开始

从零开始讲线段树,适合有一定C/C++编程基础,想学习线段树的读者。

2016-08-22 22:26:41

动态规划求小于等于n的质数个数

动态规划求小于等于n的质数个数

2016-05-10 20:25:58

Codeforces 665E. Beautiful Subarrays (trie树)

题意: 给定n个数A[1..n](1<=n<=10^6,0<=A[i]<=10^9),和k (1<=k<=10^9) 求有多少个区间[L,R]使得A[L] xor A[L+1] xor ... xor A[R-1] xor A[R] >= k。

2016-04-27 10:22:21

WOJ 1618 - Magic Array (线段树+单调栈)

题意:给定n(n<=500000)个数,A[1],A[2],...,A[n]。求所有子区间的 (最大值*最小值*长度)之和

2016-04-20 10:33:21

WOJ 1608 Calculation (暴力搜索/动态规划)

题意:n个整数(n输入:第一行是T,代表测试数量。接下来有T组数据,每组的第一行是n,第二行是n个数(0输出:对于每一组数据,输出最多可以分成多少个可以计算出S的部分。样例:Sample Input25 51 2 3 4 55 51 2 3 8 8Sample Output32

2016-04-13 19:43:13

SQLite分析之WAL机制

对SQLite的WAL机制的分析

2016-04-02 18:02:39

Codeforces 650D. Zip-line (动态LIS) (可持久化线段树 或 离线+树状数组)

题意: 给定一个长度为n的数列,和m个询问,每个询问的格式是:将原数组的第a个数改成b之后,数组的最长上升子序列(LIS)的长度。做法:可持久化线段树令 h[ ] 为原数组,LIS_L[ i ] 表示以 i 结尾的LIS长度,LIS_R[ i ] 表示以 i 开头的LIS长度。这俩数组用普通LIS算法O(nlog2(n))求出。然后来分析一下询问怎么处理:在 h[a

2016-03-11 17:38:45

Codeforces 633H. Fibonacci-ish II (Mo's Algorithm(莫队算法) + 线段树 + 离散化)

题意: 给定一个长度最大为3万的序列,和最多3万个询问,每个询问问某区间[L,R]里的数,去掉重复然后排序之后,依次乘上斐波那契数列然后求和,结果对m取余的值。区间优化用Mo's Algorithm(莫队算法),莫队算法的Add和Remove中使用线段树,所以整体复杂度是O(n*sqrt(n)*log2(n)).这题一路TLE,从TLE26到TLE27到TLE29到TLE35都快绝

2016-03-10 23:55:40

Codeforces 86D. Powerful array (MO's Algorithm(区间查询的离线优化))

题意:给一个长度为n的数组,有 t 个区间询问,求一个特定的值。这个值 = 对区间内出现的每个值v,累加 V 乘上(V的出现次数的平方)。刚刚学了MO's Algorithm,看文章说这题比较经典,就来做做看了。MO's Algorithm:就是对于一个区间的询问来说,如果该询问支持Add和Remove(即,区间信息的维护支持加和减),就可以考虑使用这个算法。假设有N个数,M个

2016-03-09 15:04:27

Codeforces 633E. Startup Funding (概率+非递归线段树/Sparse Table +二分)

题意: 题目有一点点复杂。  有n(1 现在,对于每个L值,都有一个可以最大化p(L,R)值的R,假设当左端点为L时,最大的p(L,R)的值为Q[L]。题目问,在这些L值中,随机选择k个作为L值,对于每个L值计算可能达到的最大p(L,R),然后求平均数,问这个结果的数学期望是多少。简略思路:第一步:求出上面定义的Q[L]数组第二步:将Q数组进行排序,从小到大排序。第

2016-03-08 11:56:58

Codeforces 633 G. Yash And Trees (dfs序+线段树+位图)

一道化树为链+线段树+位图的题目。

2016-03-07 22:52:40

Codeforces 612 D. The Union of k-Segments (非递归线段树+离散化)

题意:给定一堆线段,求最后重叠了k次或以上的线段和点。先操作,最后一次下推标记,所以尽管是区间修改,非递归写起来还是很简单。维护两个线段树,一个维护线段的覆盖,一个维护点的覆盖。对于线段[L,R],点修改的区间是[L,R],区间修改中,用线段的左端点代表这条线段,所以区间修改的区间是[L,R-1]在所有操作都结束之后下推标记,然后从左到右扫描线段输出答案即可。输出答

2015-12-28 23:13:56

Codeforces 605D. Board Game (BFS+线段树套SBT+离散化)

题意: 给定十万个卡片,卡片上写着起点(a,b) 终点(c,d)当前坐标(x,y), 开始时是(0,0)如果 x >= a 且 y >= b  则,下一步可以选择使用这个卡片,使用过后,当前坐标变成(c,d) 给定卡片信息之后,问最少使用多少张卡,可以使用最后一张卡。本质上就是一个BFS(广度优先搜索),因为最优序列中,每张卡最多被使用一次不过,这个BFS在

2015-12-21 13:05:17

无题

由于在Codefights 上出题需要图片,Codefights上是用markdown来编辑的,要放图片的话,需要先把图片保存到网上,于是就先把图片放在这里了。用1*2的矩形去填充4*n的矩形,下图为n=1,2,3时的所有可能的填充方式。

2015-10-30 09:03:27

数据结构分析之线性哈希表(Linear Hash Tables)

在看Hector Garcia-Molina,Jeffrey D.Ullman,Jennifer Widom等人写的《数据库系统实现》的时候,第14.3节介绍了两种可以动态扩充容量的哈希算法。1.Extensible Hash Tables2.Linear Hash Tables(以下简称LHT)第一种方法有其局限性,具体可以去看书,本文主要介绍第二种方法。哈希

2015-09-24 18:47:16

线段树详解 (原理,实现与应用)

线段树详解By岩之痕一:综述线段树是一种可以快速进行区间修改和区间查询的数据结构。点修改,区间修改和区间查询的复杂度都是O(log2(n))并且,线段树可以维护很多种类的信息。说到线段树就不得不提一下树状数组,树状数组维护的信息必须满足区间减法,因为树状数组只是维护1到X的信息,通过相减来得到区间信息,代码简单而且速度快,占用空间又少于线段树,所以一般情况下可以用树状数组的地方就

2015-09-09 01:58:46

Codeforces 45C. Dancing Lessons (SBT)

题意:n个人站成一行,从左到右编号1到n,每人一个技巧值。若相邻的两个人性别不同,则这两人有可能一起跳舞。每次操作,从所有可能一起跳舞的两人中,选出技巧最接近的两人,若有多种方案,则选择最靠左边的(编号最小的)。然后其余的人合并在一起,不留空(编号不变)。继续操作,直到最后结束,问所有的出来跳舞的人的编号以及顺序。首先,用 next 数组表示每个人的右边的第一个人的编号,-1表

2015-09-06 20:37:14

Codeforces 35E. Parade (非递归线段树 离散化)

题意:给定若干矩形,下端挨着地面,求最后的轮廓形成的折线,要求输出每一点的坐标。先将横坐标离散化,然后用线段树维护最大值,支持区间修改。在所有操作结束后,下推所有标记,然后从左到右扫描一遍高度,在高度有变化的时候输出点的坐标。更新最大值比较快的写法是用非递归线段树,在更新过程中不需要下推标记,最后一次下推所有标记。代码如下:#include #include

2015-09-06 19:02:07

Codeforces 12D.Ball (非递归线段树+离散化)

题意:给N (N对于某点(x,y,z),若存在一点(x1,y1,z1)使得x1 > x && y1 > y && z1 > z 则点(x,y,z)是特殊点。问N个点中,有多少个特殊点。思路:大概就是,先记下所有点,从大到小排序,先按z的降序,再按y的降序,再按x的降序排序。将x离散化,然后,按z分层,一层一层扫描。Z表示当前层的z值。线段树中,存的是所有 z

2015-09-03 08:31:10

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!