无    2018-07-11 17:24:24    165    0    0

由于博主们(?)都很良心没有扯杂七杂八的东西,所以我也不啰嗦了。

标注[1]:后缀数组图片支持来自于[这位大佬]

标注[2]:基数排序图片支持来自于[这位大佬]

基数排序

大佬请跳过。
是一种稳定的、Θ(n)级别的排序方式,这年头极好用的。
现有一组数据:73,14,81,22,55,65,43,28,39,93
我们首先只按照个位数进行桶排序,并相应记录下标,仍然得到一个无序数列。

图片标题

然后在此次的基础上只考虑十位数进行排序。我们发现这成了一个有序数列!

图片标题

依次类推,如果有百位数、千位数,同样排序至最高位。

  • 显然也可以从高位排起。

实现

所谓SA

有必要在开头就阐明的东西:

  • SA(Suffix Array)数组:排名为i的后缀是[SA[i],n)
  • Rank数组:[i,n)后缀的排名为i(求的过程中直接离散化)

所谓后缀数组就是指SA,由于SARank的反函数,所以任意得到一个都可以在Θ(n)的时间内得到第二个。

先展示代码如下:

  1. inline int cmp(int *f,int x,int y,int w) {return f[x]==f[y]&&f[x+w]
无    2018-07-11 17:24:23    58    0    0
一朝为叶,终生为叶。

标注[1]:文中图片与行文思路主要来自于[这位大佬]
标注[2]:文中有部分(一点点)参考[这位大佬]

起源

后缀树的概念是在1973P.Winter的一篇叫做"Liner  Pattern  Matching  Algorithm"的文章中第一次被提出,当时这篇文章把这种数据结构叫做"Position Tree"
该算法能够在线性时间内构建后缀树,这个算法还被Donald Knuth称为“1973年度算法”,足以见其重要性。几年之后,Edward M.McCreight介绍了另外一种不同的线性算法,这种新算法更加节省空间,可以说是对原来算法的大幅优化。1995年,E. Ukkonen在此基础上提出了第一个能在线

无    2018-07-11 17:24:20    125    0    0

Suffix Automation

随便放了几道题上来,诸君请笑纳。如有失误,欢迎指正。


Spoj Substrings

求长度为x的字符串的最大出现次数。

Problem Solution

每个状态(节点)s代表的字符串出现次数即为|Right|,长度的范围为[Min(s),Max(s)]排序、统计。代码见下。


bzoj2555 Substring

两个操作:1.在当前字符串后加上一个字符串;2.询问子串s的出现次数。

Problem Solution

LCT维护SAM中每个节点表示的子串数量。代码见下。


POJ Musical Theme

求不可重叠最长公共子串。

Problem Solution

状态s表示的子串长度区间为[Min(s),Max(s)],Right集合表示的子串长度区间是[l,r],如果lr>=Max(s),就有满足条件的长度为

无    2018-07-11 17:24:19    293    0    0

为什么是浅谈呢,因为我也不是很会。

等以后我觉得我会了就重新写一篇吧。

发现我至今仍感到比较懵逼的原因是看了太多什么离散型傅里叶变换傅里叶分析处理信息频域时域正弦余弦相位差及其物理意义的“感性理解”......果然还是oier的博客实用亲切啊。

傅里叶变换其实就是这个式子:

F^(ξ)=F(x)e2πixξdx

它是对DFT的一种实现。类似的把DFT写出来就是:

SF^[k]=n=0N1SF[n]e2πinkN


多项式

快速傅里叶变换在信息学中的主要运用就是加速向量卷积,及多项式乘法。

假如我们有两个多项式:

无    2018-07-11 17:24:17    213    0    0
为什么是浅谈呢,还是因为我也不是很会
主要是数学什么的太高深了,所以等以后我觉得自己会了再写一遍吧......

写在前面

利用FFT可以加快卷积的速度。再离散正交变换的理论中,已经证明在复数域内,具有循环卷积特性的唯一变换是DFT(Discerte Fourier Tansform),所以,FFT是更简单、最高效的离散正交变换。但是众所周知,由于涉及到复数即大量浮点数的运算,FFT(Fast Fourier Transform)无论是速度还是精度都是一个问题。

在需要很准确的精度或者需要支持取模的时候就得用到数论来代替它了,名字叫做NTT(Fast Number-Thearetic Transform)。

其中关于原根的解释以及证明我也不是很能搞得懂......不过鉴于是信息学奥林匹克竞赛选手,可以先不了解其证明,知道运用就OK了。


Fast Fourier Transform实现原理

学过了Fast Fourier Transform之后我们可以发现,FFT实现的主要依据就是ωn的三个性质

  • ωnn=1
  • ωn0,ωn1......ωnn1互不相同
  • ωn2=ωn/2,ωdndk=ωnk,
无    2018-07-11 17:24:16    124    1    2
这个是连浅谈都不敢直接讲了......
真$\cdot$剧毒

写在前面

关于置换群和$P\acute{o}lya$定理,曾今第一次翻的时候除了懵逼还是懵逼,然后发现现在一看居然懂了一点......所以随便写一写吧,以后应该是会改的。
相比于直接给出定理,私下更喜欢证明和推导过程,如果您不感兴趣,自然也可以跳过,只知道定理是不影响解题的。


概念性的东西总是要放在最前面。请至少对概念有个印象,以便于提到时如果想不起来至少知道到哪里翻。


群的定义

给定一个集合$G=\{a,b,c...\}$和集合$G$上的二元运算,并满足:

  • 封闭性:$\forall a,b\in G,\exists c\in G,a\cdot b=c$
  • 结合律:$\forall a,b,c\in G,(a\cdot b)\cdot c=a\cdot (b\cdot c)$
  • 单位元:$\exists e\in G,\forall a\in G,a\cdot e=e\cdot a=a$
  • 逆元:$\forall a\in G,\exists b\in G,ab=ba=e,$记$b=a^{-1}$

则称集合$G$在运算$\cdot$下是一个群,简称$G$是群。一般$a\cdot b$简写为$ab$。


$G$中所含元素的个数称为$G$的阶,记为$|G|$。于是$G$可以根据阶的数量分为有限群和无限群。
$G$中的元素也是有阶的:$\forall a\in G,$使得$a^k=e$成立的最小正整数$k$。如果不存在,则$a$的阶即为正无穷。


消去律

在群$S$中,消去律指:$\forall x,y,a \in S,x=y$与$x\cdot a=y\cdot a$互为充要条件。
在群中,逆元存在$\Longleftrightarrow$消去律存在。

逆元存在$\Longrightarrow$消去律存在

只要把$x\cdot a=y\cdot a$两边同乘$a^{-1}$。

消去律存在$\Longrightarrow$逆元存在

对于$a\in S,$构造$S'=\{x\cdot a\mid x\in S\}$,根据封闭性有$S' \subs

无    2018-07-11 17:24:14    215    0    0

CDQ分治习题


CQOI2011动态逆序对

对于序列A,它的逆序对数定义为满足i<j,且Ai>Aj的数对(i,j)的个数。给1n的一个排列,按照某种顺序依次删除m个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。


Problem Solution

既然可以离线那便不用树套树。

考虑CDQ分治求逆序对:每次插入一个数,计算前面有多少个比它大的和后面有多少个比它小的。(后来发现这就相当于归并排序)这本来就是一个插入的动态过程。我们无法解决删除操作,那么离散之后变为一个个插入即可。

容易发现,这样就成为一个三维逆序对的题目。(第一维坐标,第二维数值,第三维时间)由于坐标已经排好序,对时间二分即可。


Code

  1. #include<algorithm>
  2. #include<cstring>
  3. #include<cstdio>
  4. using namespace std;
  5. typedef long long LL;
  6. const int N=1000100;
  7. struct qes {int x,y,z;} q[N],t[N];
  8. int n,m,tim,pos[N];LL c[N],ans[N];
  9. inline void add(int o,int v) {for(;o<=n;o+=o&-o) c[o]+=v;}
  10. inline LL query(int o) {LL ret=0;for(;o;o-=o&-o) ret+=c[o];return ret;}
  11. inline void in(int &x) {
  12. x=0;int f=1;char ch=getchar();
  13. for(;ch<'0'||ch>'9';) {if(ch=='-') f=-1;ch=getchar();}
无    2018-07-11 17:24:13    110    0    1

仅适用yu允许离线的题目(但是存心想考数据结构的出题人怎么会给你这个机会)

CDQ分治

陈丹琪在论文中讲述的关于cash这一类的问题的解法。

当然其实我没有从她的论文里面看出什么就是了(并没有找到论文原文)


当你树套树打烦了搞基数据结构码得快要死了,如果题目允许如果出题人不那么如xcc一般的jay,设计这造化的神犇还稍有仅使留下的以淡红的血色换来的微末的良心给你以苟且偷生,你就可以试着以CDQ(或是整体二分)来为这世界写一点东西——你觉着早有写它的必要了。


一般遇到的分治是对静态区间或是静态具有相似结构且互不影响的问题所做的分开处理然后拼起来。这里就有三个限制条件:静态,相似子结构,以及互不影响。

但是一般的数据结构题都有三个特征:动态,不相似的子结构,以及互相影响。


那么CDQ分治是如何做到代替一些数据结构的呢?

我们一般进行的分治都是对一个序列、一段区间或是一个数分治,这些都可以形象地称为“对空间所做的分治”,因为对于代码来说这些就是具体的空间里的东西。

对于数据结构题来说,空间(即序列或是一棵树上维护的东西)显然是不对称的。但是我们注意到,操作显然是相似的。(废话)

这也正是CDQ分治不同于其它分治的地方——一般所用分治的对象是区间或者答案,基于空间。而CDQ分治是基于时间的对象是操作的分治。这也就是它必须做为离线算法的缘故。

当然CDQ之前(或者CDQ之时)有必要按照某一维关键字排序,使这一维关键字的影响常数化,不然这就跟暴力没什么区别了。


由于时间显然单调,所以可以每次将时间(也就是操作)分为[l,mid]和[mid+1,r],但是这样就面临了一个问题:[mid+1,r]对[l,mid]是不会有影响的,所以[l,mid]可以单独计算,但是[l,mid]对[mid+1,r]也许是有贡献的,所以不能单独处理。

于是采取一个亦可赛艇的措施:暴力统计[l,mid]对[mid+1,r]的贡献,然后为了避免影响到后续的分治,再暴力修改回来。

这里需要注明一下,就是我们所求的答案其实就是原序列原本的答案+操作对答案的贡献,也就是影响。

2/2