poj 3415 Common Substrings (后缀自动机+parent树上的lazy标记)

http://poj.org/problem?id=3415

题意:

给出两个字符串,问公共长度大于等于k的子串个数(只要两个串的位置不同就认为是不同)

思路:

考虑SAM的性质。

SAM上的一个节点所能接受的本质不同的子串个数是st[v].len – st[st[v].link].len

而这些子串,都出现了right[v]次,因为不同子串的个数就是(st[v].len-st[st[v].link].len)*right[v]

现在有了限制条件,要求长度大于等于k.

没有限制的话,SAM上的一个节点所能接受的字符串的长度范围是在[st[st[v].link].len+1,st[v].len]

那么现在范围其实就变成了[MX,st[v].len],其中MX = max{st[st[v].link].len+1,k}

对于A串构建SAM,然后B串在SAM上运行

考虑对于SAM的某个状态,B串此时的最大匹配长度为len,那么len>=MX时,满足条件的字符串的范围就变成了[MX,len] 

len<MX时无贡献。

所以该状态(v)对答案的就是  (len-MX+1)*right[v]

然而这还不算完,和之前的LCS2一样,如果SAM上的一个节点能匹配字符串B的长度大于等于k,那么该节点的祖先节点(父亲节点,父亲的父亲的节点…)

能匹配的字符串B的长度也都大于等于k…

如果我们一边匹配一边沿着parent树自底向上传递的话…复杂度n^2,一首凉凉送给自己

但是正常人会这样?.jpg

我们先打个标记,最后沿parent树自底向上把标记传递上去就行了。。

需要注意的是,此题的字符集是大小写字母都会包含…RE了2发orz

 

BZOJ 1230: [Usaco2008 Nov]lites 开关灯 (线段树区间修改,区间查询)

 

1230: [Usaco2008 Nov]lites 开关灯

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1676  Solved: 874
[Submit][Status][Discuss]

Description

Farmer John尝试通过和奶牛们玩益智玩具来保持他的奶牛们思维敏捷. 其中一个大型玩具是牛栏中的灯. N (2 <= N <= 100,000) 头奶牛中的每一头被连续的编号为1..N, 站在一个彩色的灯下面.刚到傍晚的时候, 所有的灯都是关闭的. 奶牛们通过N个按钮来控制灯的开关; 按第i个按钮可以改变第i个灯的状态.奶牛们执行M (1 <= M <= 100,000)条指令, 每个指令都是两个整数中的一个(0 <= 指令号 <= 1). 第1种指令(用0表示)包含两个数字S_i和E_i (1 <= S_i <= E_i <= N), 它们表示起始开关和终止开关. 奶牛们只需要把从S_i到E_i之间的按钮都按一次, 就可以完成这个指令. 第2种指令(用1表示)同样包含两个数字S_i和E_i (1 <= S_i <= E_i <= N), 不过这种指令是询问从S_i到E_i之间的灯有多少是亮着的. 帮助FJ确保他的奶牛们可以得到正确的答案.

Input

* 第 1 行: 用空格隔开的两个整数N和M

* 第 2..M+1 行: 每行表示一个操作, 有三个用空格分开的整数: 指令号, S_i 和 E_i

Output

第 1..询问的次数 行: 对于每一次询问, 输出询问的结果.

Sample Input

4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4
输入解释:
一共有4盏灯; 5个指令. 下面是执行的情况:

1 2 3 4
Init: O O O O O = 关 * = 开
0 1 2 -> * * O O 改变灯 1 和 2 的状态
0 2 4 -> * O * *
1 2 3 -> 1 输出在2..3的范围内有多少灯是亮的
0 2 4 -> * * O O 改变灯 2 ,3 和 4 的状态
1 1 4 -> 2 输出在1..4的范围内有多少灯是亮的

Sample Output

1
2
考虑一次翻转对区间[L,R]的贡献
开着的灯数等于当前区间长度减去之前区间[L,R]内开着的灯数
也就是tree[rt].sum = r-l+1-tree[rt].sum;
对于lazy标记,无非是从0变到1,从1变到0.
手误写错了一个地方,2A

 

codeforces #381 div2 E. Alyona and towers (线段树 区间合并)

e:题意:那个数,定义hill为一段连续的区间,满足该区间为严格单峰。现在有若干操作,每个操作是对某段区间的数同时增加一个数,问每次操作后,所有的hill中,宽度最大的(区间长度最大)的是多少。

思路:同时增加一个数很线段树。。。但是要维护什么呢。。。?

猜测:肯定要维护一个区间中hill的最大宽度…

但是合并的时候要怎么办呢。。。

考虑两个方向的合并。。。

所以还要维护一个区间中,包含右端点的向左单调减延伸的长度,以及左端点的值。

同理,要维护一个区间中,包含左端点的向右单调增延伸的长度,以及右端点的值。

那么每次pushup的时候,就是两个区间hill的最大值,以及两个方向合并的最大值中取最大。。。

。。。上面是我口胡的。。。

upd:

口胡的还是有点靠谱的(并没有2333,还是漏了情况)

具体题解见代码注释

以及,为了过这道题先过了在岛老师空间题解中提到的两道题目:

hdu 3308 题目链接

hdu 5367题目链接

 

 

 

hdu 4747 Mex (线段树lazy标记)

题目连接

题意:给出n(n<=200000)个数,问所有区间[l,r]中mex的和。 (一个区间mex的定义为,这个区间中没有出现的最小的非负数)

思路:我们观察到mex(1,i)随着i增大,是不减的。(单调是线段树查询区间的时候非常好用的东西,这也是次题的突破口)

mex(1,i)可以O(n)维护出

现在我们考虑左端点向右移动对答案的影响。

当i移动到i+1时,此时序列中少了a[i],设r为最小的x,满足a[x]=a[i],那么当右断点在区间[r+1,n],mex值是没有改变的。

当右端点属于[i+1,r-1]时,mex大于a[i]的会变成a[i]。

由于我们知道从1到某区间的mex值是单调的,那么mex大于a[i]的点必然是连续的一段。

我们可以知道最左边的q,满足mex(1,q)大于a[i],然后将区间[q,r-1]成段更新为a[i]

因此整理思路,我们需要做两件事。

一个是每次区间求和,一个是找到最左边的q满足mex(1,q)大于a[i].

线段树维护三个域,max域,表示该区间中mex(1,i)的最大值;

sum域,表示该区间中mex(1,i)的和

lazy域,表示延迟标记。

可以预处理出nxt数组,表示位置i上的数下次出现最近是在nxt[i]

 

 

 

 

 

 

codeforces 145 E. Lucky Queries (线段树lazy标记)

题目链接

题意:给出一串只由数字’4’和’7’组成的串。两种操作,一种是询问整个串中最长非下降子序列的长度,另一种给出区间[l,r],将区间中的没个数反转,反转的定义为,4变成7,7变成4.

思路:线段树lazy标记。

线段树的域记录5个信息,c4,c7,c47,c74,flip,a分别表示4的个数,7的个数,非下降子序列的个数,非上升的子序列的个数,以及该区间是否被翻转。

纠结了很久PushUp操作。。。。

c4和c7倒是没什么疑问。。。。

一开始觉得c47是由三部分的最大值更新得到的。。。

left.c4+right.c47,left.c4+right.c7,left.c47+right.c7…

但是样例过不了。。。

纠结了半天发现。。。

比如4774,4444是左右两个区间的时候。。。。

c47最大是5.。。但是left.c4 + right.c7=6,比正确答案大。

原因是。。一个区间中4的位置可能是分散的。。。这样只有某段连续出现的4对答案的贡献是正确的。。。

所以只有区间长度为1的时候c4+c7的更新方式才是合法的。。。

我们不妨在初始化的时候。。。。在线段树的叶子节点直接设置c47为1(当然相应地c74也要为1)

另外一个收获是。。。线段树对于区间的操作(对于点的操作也是同样)

不一定是某种常见的定义过的操作(求和啊,最大值最小值啊之类的)

也可能是某种自定义的操作。。。

比如这道题中的flip操作。。。

就是对区间的一个自定义的操作。。。

 

 

 

 

 

 

codeforces 52 C. Circular RMQ (线段树区间更新,区间询问)

题目链接

题意:一个循环数列,两种操作,一种是把某段区间中加上v,另一种是询问某区间的最小值。对于每个询问,输出答案。

思路:区间更新+区间询问的模板题….

注意体会pushdown以及update的时候。。。

要同时更新tree数组和lazy数组。。。

读入的时候可以用sscanf判断操作类型。。。

 

 

light oj 1080 Binary Simulation (线段树lazy标记,区间更新,单点查询)

题目链接

题意:给出一个长度为n的数列,每个位置是0或者1,给出q个操作,操作有两种类型,分别是将一段区间中反转,和询问当前某位置是0还是1

思路:lazy标记。lazy[i]记录以i节点为根节点的子树对应的区间中被翻转的次数,初始为0.然后查询的时候,根据被翻转次数的奇偶性确定答案。

wa了好多发。。。比较致命的是。。PushDown函数忘记改了。。。还按照染色的方法直接赋值的。。。然而这里是统计次数。。。所以是累加。。。。

 

codeforces 356 A. Knight Tournament (线段树lazy标记,倒序处理)

题目链接
题意:现在有N个骑士进行M轮PK…现在告诉这M轮是谁站在台上…其将l~r所存在的骑士都打败..而若一个骑士被打败..就出局了..也就是不存在了…请输出每个骑士是被哪个骑士打败的(最后的胜利者输出0)…保证有解..

思路:由于先前被打败的骑士直接就退场了。。。所以如果不做判断。。那么之后胜利的骑士会干扰之前的结果。。。

可以在pushdown的时候加判断。。。

不过我觉得比较好的做法是。。。倒序处理。。。。

倒序处理。。。后处理的直接覆盖先处理的结果。。。因为后处理的在之前。。优先级更高。。。被覆盖掉的骑士其实应该是退场的。。。

倒序处理就避免了判断的问题。。。完美。。。

 

 

 

codeforces 292 E. Copying Data (染色问题,线段树lazy标记模板题)

x题目链接

题意:给出两个数组,每个数组n个数,分别为a和b,给出m个操作,操作有两种类型,第一种是给出x,y,k,表示从a数组的x坐标开始复制k个数到b数组的y到y+k-1。

第二种操作是给出x,询问当前b[x]是多少。

对于每个第二种操作,输出结果。

 

思路:第一次写lazy标记的线段树。

今天突然就顿悟了。。。其实lazy标记的思想大概就是。。

对于某段区间的更新,如果没有查询到这段区间中任何一个数的时候。。。那么这个更新其实是无所谓的。。。

(让我想到了那个脑洞,就是整个世界都是一段程序,为了让你不察觉异常并且耗费尽量少的资源,所有场景只有在有人观测的时候才会被加载,不观测就用很少的资源随便处理一下233)

所以lazy标记,也叫延迟标记,就是只有当查询到某个节点的时候,才去把之前的修改更新,不然不更新(就好像有人观测的时候,上帝才把某个场景的代码写出来)

这道题除了延迟标记这个点外,还用到了染色问题的经典做法。

所谓染色问题,这里说的是一种区间覆盖问题,每次用一个颜色覆盖某段区间,最后询问某一点是什么颜色(大概是这样…?

回到这道题,具体做法是,记录每次覆盖操作的位移差,然后用线段树维护某个点最后被覆盖的时间(也可以形象得说被染成了什么颜色,染的颜色种类和时间对应)

这样,每次询问b[x]的时候,我们可以查询x位置最后是被染成了什么颜色,然后根据之前记录的位移差信息,就可以得到相应的答案。

这是一种经典做法,这类问题具有一定普遍性,注意体会。

 

以及,之前对lazy标记有一个错误得认识,以为lazy是基于线段树本身数组的一个辅助数组。。。但是做完这道题后感觉。。。

之前写的单点更新的线段树数组tree和现在的lazy标记的数组应该是同等地位。。。。PushDown和PushUp大概也是同等地位。。。就是说。。。可以只出现PushDown和lazy数组不出现PushUp和tree.

还有一些写法上的注意,见代码注释。