hdu 4819 2013 Asia Regional Changchun G (四叉树|| 二维线段树单点更新 模板题)

http://acm.hdu.edu.cn/showproblem.php?pid=4819

题意:

给你一个n*n的矩阵, 每个点是一个数字, Q个操作,每次选择一个子矩阵, 把中心元素替换成子矩阵中最大值和最小值之和的二分之一。

 

思路:

显然是一个二维线段树…..

然而菜鸡如我,并没有写过二维线段树啊?

那怎么办呢

一首《凉凉》送给自己

 

 

然而我们还有四叉树2333

2A,写错一个地方。第一次写四叉树,orz

 

然后又写了一个二维线段树的版本,借鉴了kuangbin的写法,改成了自己习惯的代码风格。

果然常数差好多。。。(据说是因为四叉树退化得厉害QAQ

第三个是四叉树的做法,第二个是kuangbin 的 树套树版本的二维线段树

第一个是我改写kuangbin代码之后的代码。

可以看出,四叉树虽然好写好理解一点,但是时间上不太优秀啊….

 

spoj nsubstr Substrings (后缀自动机 模板题)

http://www.spoj.com/problems/NSUBSTR/en/

题意:

f[i]指长度为i的串出现次数的最大值。这里的不同出现指,可以有重复串,只要起始位置不同就视为不同的出现。

求f[1]..f[lenth]。

思路:

我们知道,SAM上的节点是right集合的等价类。

一个子串的right集合是指在一个母串中,某个子串所有出现位置的右端点的集合。

如果两个子串的right集合完全相同,那么就可以归结为同一个节点,也就是说这两个子串对于SAM是等价的。

因为在SAM上,这两个子串后,添加若干字符得到的后缀都是一样的。

所以一个SAM节点的个数,就是right集合等价类的个数(如果不考虑初始状态)

对于SAM某一个节点,其能表示的子串有一个范围,设为[MIN,MAX]

SAM的一个节点能表示的子串的含义是说,这些子串的right集合相同。

而一个子串出现的次数就是其right集合的大小。

考虑SAM上的某个节点,其表示的长度区间在[MIN,MAX]的子串都出现了|right|次

如果我们直接从MIN更新到MAX有点太暴力了,实际上这里我们可以只更新f[MAX]

由于长度i-1的子串出现的次数一定大于等于长度为i的子串出现的次数,所以最后长度从大到小更新f即可。

现在的问题就变成了如何求right集合。

实际上我们不需要知道right集合的具体组成,只需要知道right集合的大小。

考虑一棵parent树,树上某个节点的right集合就是该节点的所有儿子节点的right集合的并集

因此我们只需要在parent上自低向上更新right集合的大小就可以了。

如何保证在parent树上是自底向上更新呢?

我们只需要按照len,也就是SAM中所有节点能表示的子串的MAX值从大到小的顺序更新right集合。

原因是parent树上,儿子的len一定比父亲的len长。

注意到,对于parent树上的叶子节点,其right集合是1,这也是我们的初始状态。

部分实现细节见代码注释。

关于SAM的详细学习笔记日后补

20171109Update:

注释写错了一处,a[1]应该是len最短的状态的标号,之前写成了最长的。

 

 

 

 

【施工中】SAM学习笔记

*在学习后缀自动机之前需要熟练掌握WA自动机、RE自动机与TLE自动机*

怕是老年人的最后一篇算法学习笔记了

心情不好,此文无限期tj

概述

主要讲解在我学习的过程中比较难理解的地方..并不保证全面

首先,后缀自动机是一个能且只能接受一个字符串的所有后缀的确定性有限状态自动机,也就是DFA

SAM同时具有自动机和树的性质。

节点(状态)

SAM中的节点,也叫状态。

明确一个说法:“一个节点所表示的字符串”。

由于一个字符串的子串一定是某个后缀的前缀。

因此一个字符串的子串一定可以在SAM上运行。

因此“一个节点Q所表示的字符串”的含义是说,从初始状态开始,运行该字符串后,到达的状态是Q.

一个节点所表示的字符串长度属于范围[MIN,MAX],并且区间中每个长度的字符串都出现一次

能表示的字符串长度范围有最大值很好理解,有最小值是因为:长度越小的字符串出现的位置越多,因此当长度小于MIN之后,其出现的位置增加。

由于后文见到,SAM中状态是终点位置集合的等价类,因此一个节点所表示的字符串长度存在一个最小值。

后文还问见到,一个节点的MIN恰好是其父亲节点的MAX+1

终点集合 (endpos / Right)

终点集合一般国内的资料叫right集合,国外好像更常见的叫法是endpos集合。

其实就是对于一个子串a,其在母串S中出现的位置的右端点的集合。

那么这个right集合有什么作用呢?

考虑naive的做法,一个串S有O(n^2)的后缀,凉凉

那么我们发现,对于right集合相同的两个子串,代表其子串的状态(意思是说,从初始状态到该状态所表示的字符串)是可以合并的。

为什么?因为这两个子串的所有出现位置的右端点相同,那么在其后面添加若干字符得到的后缀也一定完全相同。

那么我们可以根据right集合,将字符串的子串分成若干个等价类

对于一个等价类,我们在SAM中用一个状态表示就行了。

接下来考虑right集合的性质。

right[v]表示状态v所表示的子串出现的次数。

 

后缀链/parent树

对于不为初始状态的所有状态,一个状态对应着一个等价类,令w作为其中最长的子串,其余的子串都是w的后缀。

w的所有后缀中,一部分在w所在的等价类中,另外一部分位于其他的等价类中。于是定义后缀链link(v)连接w所有后缀中位于其他等价类并且长度最长的那个后缀所在的等价类。

 

那么根据后缀链的定义,以及后缀的长度是连续的(“后缀的长度是连续的”的含义是说,一个长度为k的字符串,一定有长度为k,为k-1,一直到长度为1的后缀)

因此一个节点的MIN恰好是其父亲节点的MAX+1  (MIN,MAX分别表示一个节点所能表示的字符串的最小值和最大值)

 

复杂度

后缀自动机·张的知乎专栏_震惊!SAM复杂度竟如此显然!

%%%qc大爷

 

构造方法

这个算法是在线的,每次在构造好的自动机的基础上增加一个字符。

对于每个状态,需要保存lenlink以及转移状态信息。

初始条件下,自动机只包含一个起始状态t0len=0并且link指向-1。所有算法要做的就是给后缀自动机增加一个新的字符c。

  • 我们用last来表示当前需要增加一个字符的状态,初始情况下last=0,之后每次增加字符后都会修改。
  • 创建一个新的状态cur,要求len(cur)=len(last)+1link先留着。
  • 接下来进行这样的循环:从last状态开始,如果不存在字符c的转移,那么增加一个到达cur的字符c的转移,然后沿着后缀链继续检查——如果不存在字符串c的转移,那么增加一个转移;如果字符串c的转移已经存在,那么停止循环,将停止时检查的状态记为p。这个时候,会出现两种情况:
    • 如果一直没有遇到存在转移的状态,那么最终我们会到达伪状态-1,只需要让link(cur)=0后退出。
    • 如果遇到存在字符c转移的状态,另q为转移到的状态,那么又有了两种情况:
      • 如果len(p)+1=len(q),只需要令link(cur)=q后退出。
      • 否则,创建一个新的状态clone,将q的转移也拷贝给clone,令len(clone)=len(p)+1。然后,将状态cur和状态q的后缀链指向clone。最后需要完成的事情就是,遍历p的后缀链上的状态,如果存在指向状态q的字符c转移,那么将这个转移重定向到clone(如果不存在,遍历停止)
  • 在任何一种情况下,最后都需要将last设置为cur。

根据后缀链的定义,last开始的后缀链上的状态就是自动机的所有终止状态。

 

 

我的模板

出于太懒的原因,没有封装

需要注意的是,状态数要开到字符串长度的2倍,以及预处理之前先拓扑

需要注意的是,状态数要开到字符串长度的2倍,以及预处理之前先拓扑

需要注意的是,状态数要开到字符串长度的2倍,以及预处理之前先拓扑

 

 

 

 

 

 

 

 

SA&&SAM论文

 SAM学习指南

 

fanhq666_后缀自动机与线性构造后缀树

后缀自动机(SAM)

 

 

 

广义Fibonacci数列找循环节 (二次剩余)

问题:给定,满足,求的循

环节长度。

原理见广义Fibonacci数列找循环节

这里只说做法

我们先写出递推式的特征式子   x^2 =ax + b,整理得到 x^2-ax-b=0求出 delta = a^2+4b

对于质因数小于等于delta的部分,我们选择暴力求循环节。

暴力求循环节的代码如下:

通常做法是先暴力求出来之后,写进一个表里。

通常不会有很多项。

对于质因数大于delta的部分,我们判断每个质因数是否是delta的二次剩余,如果是,枚举(prime-1)的因子,否则枚举2*(prime+1)的因子。

贴一个板子,需要注意如果是多个函数嵌套的形式,我们只需要从外向里,依次求循环节即可。

 

再补一个,更为常用的,求斐波那契循环节的板子:

 

可持久化线段树学习笔记

起因是16长春CCPC遇到了一个全场万人过的主席树题目,然而我不会orz,哭哭

可持久化线段树的本质是很多棵形态完全相同的线段树。

也可以理解成是,保存了不同时刻版本的线段树的数据结构。

如果没有可持久化线段树,那么我们如果需要不同时刻的线段树,无脑的做法可能是,需要多少个时刻的线段树,就建多少棵线段树。

但是空间绝对gg,我们考虑每次修改,其实对于一次修改,线段树上只有很少一部分被修改了,其他部分都一样。

因此,我们很容易想到,我们何不只考虑修改的部分,其他部分共用,以减少时间和空间消耗呢?

  • 可持久化线段树是利用函数式编程的思想,对记录的数据只赋值不修改,每次插入一个数据后保存一个历史版本,然后利用线段树的结构完全相同,可以直接相减的特性进行区间询问。

 

可持久化线段树有几个经典应用,比如求区间第k大  静态区间第k大   动态区间第k大 

静态区间第k大的思想:

  • 首先,给你一颗值为横坐标的线段树,每个节点上存着该值出现了多少次,这样的一颗线段树你会求区间k大值吧.二分即可.
  • 然后,假设区间是数组arr[n],区间长度是n,那么给你n颗线段树,第i颗线段树是第i-1颗线段树插入arr[i]得到.
  • 如果你有了这n颗线段树,想求区间[l,r]中的第k大值,那么你需要在第r颗和第l-1颗线段树的差线段树上作二分,就可以求得区间第k大值.
  • 差线段树很好理解,比如你有一个部分和数组sum,sum[r]-sum[l-1]就是部分和的差,代表区间[l,r]的和,差线段树同理.
  • 现在,可持久化线段树出现为你解决最后一个问题,空间问题.内存很小,不能够存下n颗线段树,但是,第2条中提到,由于第i颗线段是是第i-1颗线段是插入仅一个值得到的,两颗线段树的区别不大,仅有log(n)个节点发生了改变,我们仅仅需要记录这log(n)的数据就可以记录这个增量,这就是可持久化线段树.

以及求区间中不同数的个数   spoj-dquery 求区间中不同数的个数

思想其实和离线线段树是一样的。

在学习可持久化线段树的时候,遇到过一个叫”权值线段树“的概念

其实并不是什么新东西,只不过是把值作为节点来考虑,参考逆序对的线段树|树状数组 求法…(由于是在值域上建立线段树,所以常常需要离散化)

这思想不是很常见么….感觉完全没必要安个名字…以及,怎么不给BIT也起个叫权值BIT啊orz

 

 

参考资料:

知乎-主席树是如何求区间k大的?

可持久化数据结构之主席树

 

 

spoj CIRU – The area of the union of circles (多个圆面积并,模板题)

题目链接

题意:

多n个圆的面积并。

思路:

发现和求2个圆的完全不一样,具体请参考

SPOJ 8073 The area of the union of circles(计算几何の圆并)(CIRU)

圆的面积并 

格林公式在面积并问题中的应用

(用格林公式搞真是跪烂了。。。。

没有仔细看细节,当成板子好了(我最菜.jpg

将代码写成了自己熟悉的风格。

以及双倍经验题:SPOJ VCIRCLES

 

 

 

cdq分治学习笔记

起因是队里的大佬们都会这东西,而我一个老年选手竟然还不会,实在说不过去。

cdq分治显然是分治的一种,cdq的意思就是超短裙啦(

这东西网上资料很多(然而还是学不会

先放一波资料:

资料1

【教程】简易CDQ分治教程&学习笔记

[偏序关系与CDQ分治]【学习笔记】

学习笔记——cdq分治

[学习笔记] CDQ分治 从感性理解到彻底晕菜

lwt菊苣的博客

下面转自lwt菊苣的博客,豁然开朗。

  • 与普通分治的区别
    普通分治中,每一个子问题只解决它本身(可以说是封闭的)
    CDQ分治中,对于划分出来的两个子问题,前一个子问题用来解决后一个子问题而不是它本身
  • 适用的情况
    在很多问题中(比如大多数数据结构题),经常需要处理一些动态问题
    然而对动态问题的处理总是不如静态问题来的方便,于是就有了CDQ分治
    但使用CDQ分治的前提是问题必须具有以下两个性质:

    • 修改操作对询问的贡献独立,修改操作互不影响效果
    • 题目允许使用离线算法。
  • 一般步骤
    • 将整个操作序列分为两个长度相等的部分(分)
    • 递归处理前一部分的子问题(治1)
    • 计算前一部分的子问题中的修改操作对后一部分子问题的影响(治2)
    • 递归处理后一部分子问题(治3)

    特别说明:
    在整个过程中,最核心的就是步骤3
    此时前一部分子问题中的修改操作相对后一部分子问题来说是静态处理,因此可以更加方便地计算后一部分子问题

 

cdq分治求三维偏序美滋滋

一般是,第一维排序,第二维cdq,第三维套一层数据结构(不然的话就要数据结构套数据结构啦差评

cdq的复杂度和分治的复杂度一样也是O(nlgn),所以可以理解成cdq可以一层数据结构?因为比树套树之类好写,所以有广泛应用(?

 

 

 

 

 

 

 

辛普森积分学习笔记

16沈阳的阴影还在orz,来学习一下辛普森积分。

参考资料:梯形多步法和辛普森积分

辛普森计算定积分

辛普森积分是一种数值积分方法(然后现在只记得教计算方法的是一个小姐姐,并不记得当时学了什么orz

大概就是用梯形近似计算曲边梯形面积,辛普森积分公式如下:

下面放代码:

切了个练手题,慢慢补充总结。

需要注意的是,simpson对精度要求比较高。。。eps开到1E-10才过。。

hdu1724题目链接

hdu1724解题报告

所以问题就在于写出积分公式(如果是多重积分要变成累次积分?orz)

 

 

 

 

 

 

 

 

kd tree 学习笔记

老规矩,资料先行。

好久没学新算法了,有点忘记怎么学了orz

K-D tree 数据结构

hdu 2966 In case of failure (k-d树 最近邻近点)

 

首先来看算法的提出。

现在二维平面上有n个点,知道这n个点的坐标,然后再添加一个点,问n个点中,距离新添加的点距离最近的点。

如果不做任何预处理,那么就是暴力枚举每个点,与该定点的距离。

如何优化呢? 我们可以考虑把点域均等划分成若干个方块。

这样每次询问的时候只需要查询定点所在方格,以及定点相邻的8个方格中的点与该定点的距离即可。(除非这九个方格中没有点)

这种划分方法,对于随机数据大概是美滋滋,但是数据不会那么随机,因此划分也不能均等划 分。

这个时候, kd-tree 登场。k-d树( k-维的缩写)是在k欧几里德空间组织的数据结构

对于二维平面,kd-tree的思想是,提供一种平面的划分方法,使得对于任意输入数据,划分尽可能均匀。

划分方法其实不唯一,常用的划分方法是,对于k维中的每一维,按照方差最大的那一维划分。

(看到有些题解中,用该维度的极差(就是最大值-最小值)来作为度量,也就是按照极差最大的那一维度划分。)

(用方差的度量往往比较慢,看到根据二叉树的深度,交替维度也是一种常用做法 比如2016青岛 onsite)

下面是具体的划分过程。

 假设现在我们有平面上的点集 E ,其中有 5 个二维平面上的点 : (1,4)(5,8) (4,2) (7,9) (10,11)

        它们在平面上的分布如图:

                                                                

        首先,我们对区间 [ 1 , 5 ] 建树:

        先计算区间中所有点在第一维(也就是 x 坐标)上的方差:

                平均值 : ave_1 =5.4

                方差 : varance_1 =9.04

        再计算区间中所有点在第二维(也就是 y 坐标)上的方差:

                平均值:ave_2 =6.8

                方差:varance_2 =10.96

        明显看见,varance_2 > varance_1 ,那么我们在本次建树中,分裂方式 :split_method =2 , 再将所有的点按照 第 2 维 的大小从小到大排序,得到了新的点的一个排列:

                (4,2) (1,4)(5,8) (7,9) (10,11)

        取中间的点作为分裂点 sorted_mid =(5,8)作为根节点,再把区间 [ 1 , 2] 建成左子树 , [ 4 , 5] 建成右子树,此时,直线 : y = 8 将平面分裂成了两半,前面一半给左儿子,后面一半给了右儿子,如图:

                                                                

        建左子树 [1 , 3 ] 的时候可以发现,这时候是 第一维 的方差大 ,分裂方式就是1 ,把区间 [ 1, 2 ] 中的点按照 第一维 的大小,从小到大排序 ,取中间点(1,4) 根节点,再以区间 [ 2, 2] 建立右子树 得到节点 (4,2)

                                                                

         建右子树 [4 , 5 ] 的时候可以发现,这时还是 第一维 的方差大, 于是,我们便得到了这样的一颗二叉树 也就是 K-D tree,它把平面分成了如下的小平面,使得每个小平面中最多有一个点:

                                                                 

        可以看见,我们实际上在建树的过程中,把整个平面分成了 4 个部分

        树是建了,那么查询呢?

        查询过程:

                查询,其实相当于我们要将一个点“添加”到已经建好的 K-D tree 中,但并不是真的添加进去,只是找到他应该处于的子空间即可,所以查询就显得简单的毒攻了

                每次在一个区间中查询的时候,先看这个区间的分裂方式是什么,也就是说,先看这个区间是按照哪一维来分裂的,这样如果这个点对应的那一维上面的值比根节点的小,就在根节点的左子树上进行查询操作,如果是大的话,就在右子树上进查询操作

                每次回溯到了根节点(也就是说,对他的一个子树的查找已经完成了)的时候,判断一下,以该点为圆心,目前找到的最小距离为半径,看是否和分裂区间的那一维所构成的平面相交,要是相交的话,最近点可能还在另一个子树上,所以还要再查询另一个子树,同时,还要看能否用根节点到该点的距离来更新我们的最近距离。为什么是这样的,我们可以用一幅图来说明:

                                                                

         在查询到左儿子的时候,我们发现,现在最小的距离是 r = 10 ,当回溯到父亲节点的时候,我们发现,以目标点(10,1)为圆心,现在的最小距离 r = 10 为半径做圆,与分割平面 y = 8 相交,这时候,如果我们不在父亲节点的右儿子进行一次查找的话,就会漏掉 (10,9) 这个点,实际上,这个点才是距离目标点 (10,1) 最近的点

由于每次查询的时候可能会把左右两边的子树都查询完,所以,查询并不是简单的 log(n) 的,最坏的时候能够达到 sqrt(n)

 

放一份kd-tree的代码,按照上面讲解的过程(不是作为模板)

 

然后放一道例题:hdu2966  

 

 

 

 

uva 10870 – Recurrences (矩阵加速线性递推式)

uva10870题目链接

题意:

f(n) = a1f(n − 1) + a2f(n − 2) + a3f(n − 3) + . . . + adf(n − d), for n > d

给出f[1]..f[d],a[1]..a[d],问 f[n]%m是多少。

思路:

构造矩阵,加速递推式。

趁着这道题说一下一般的构造法。

转移矩阵M(d*d)的构造方法是,最后一行倒序写a[1]..a[d], 除去第一列和最后一行外,用1填充对角线,其余的为0.

初始矩阵M1(d*1)的构造方法是从上到下,f[1]..f[d]即可。

需要注意的是

最后答案是 (M^(n-d))*M1.mat[d-1][0] (由于经常出现的是d=2的递推式,因此注意不要把此式子的d,写成不够一般化的错误的2