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] 那么现在范围其实就变成 …

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 <= …

e:题意：那个数，定义hill为一段连续的区间，满足该区间为严格单峰。现在有若干操作，每个操作是对某段区间的数同时增加一个数，问每次操作后，所有的hill中，宽度最大的（区间长度最大）的是多少。 思路：同时增加一个数很线段树。。。但是要维护什么呢。。。？ _猜测：肯定要维护一个区间中hill的最大宽度..._ 但是合并的时候要怎么办呢。。。 考虑两个方向的合并。。。 所以还要维护一个区间中，包含右端点的向左单调减延伸的长度，以及左端点的值。 同理，要维护一个区间中，包含左端点的向右单调增延伸的长度，以及右端点的值。 那么每次pushup的时候，就是两个区间hill的最大值，以及两个方向合并的最大值中取最大。。。 。。。上面是我口胡 …

题目连接 题意：给出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]的点必然 …

题目链接 题意：给出一串只由数字'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... 但是样例过不了。。。 纠结了 …

题目链接 题意：一个循环数列，两种操作，一种是把某段区间中加上v，另一种是询问某区间的最小值。对于每个询问，输出答案。 思路：区间更新+区间询问的模板题.... 注意体会pushdown以及update的时候。。。 要同时更新tree数组和lazy数组。。。 读入的时候可以用sscanf判断操作类型。。。 /* *********************************************** Author :111qqz Created Time :Mon 26 Sep 2016 05:30:21 AM CST File Name :code/cf/problem/52C.cpp …

题目链接 题意：给出一个长度为n的数列，每个位置是0或者1，给出q个操作，操作有两种类型，分别是将一段区间中反转，和询问当前某位置是0还是1 思路：lazy标记。lazy[i]记录以i节点为根节点的子树对应的区间中被翻转的次数，初始为0.然后查询的时候，根据被翻转次数的奇偶性确定答案。 wa了好多发。。。比较致命的是。。PushDown函数忘记改了。。。还按照染色的方法直接赋值的。。。然而这里是统计次数。。。所以是累加。。。。 /* *********************************************** Author :111qqz Created Time :Wed 14 Sep 2016 12:59:07 …

[题目链接](http://codeforces.com/problemset/problem/356/A) 题意：现在有N个骑士进行M轮PK...现在告诉这M轮是谁站在台上...其将l~r所存在的骑士都打败..而若一个骑士被打败..就出局了..也就是不存在了...请输出每个骑士是被哪个骑士打败的(最后的胜利者输出0)...保证有解.. 思路：由于先前被打败的骑士直接就退场了。。。所以如果不做判断。。那么之后胜利的骑士会干扰之前的结果。。。 可以在pushdown的时候加判断。。。 不过我觉得比较好的做法是。。。倒序处理。。。。 倒序处理。。。后处理的直接覆盖先处理的结果。。。因为后处理的在之前。。优先级更高。。。被覆盖掉的骑士其实 …

x题目链接 题意：给出两个数组，每个数组n个数，分别为a和b,给出m个操作，操作有两种类型，第一种是给出x,y,k,表示从a数组的x坐标开始复制k个数到b数组的y到y+k-1。 第二种操作是给出x，询问当前b[x]是多少。 对于每个第二种操作，输出结果。 思路：第一次写lazy标记的线段树。 今天突然就顿悟了。。。其实lazy标记的思想大概就是。。 对于某段区间的更新，如果没有查询到这段区间中任何一个数的时候。。。那么这个更新其实是无所谓的。。。 （让我想到了那个脑洞，就是整个世界都是一段程序，为了让你不察觉异常并且耗费尽量少的资源，所有场景只有在有人观测的时候才会被加载，不观测就用很少的资源随便处理一下233） 所以lazy标记， …