系统设计笔记，自用。

拖了这么久，想想还是写一下游记吧，也算写下自己2年ACM生涯的一个句号。

思路

对于无修改的LCP，常用的算法是后缀数组/二分+Hash。但当场景转换为带修改的LCP查询时，后缀数组就无能为力了，因为这样每次都要重建一次后缀数组才能知道LCP的值。但对于二分+Hash来说，我们只要能够知道一段字符串的hash即可，而Hash值显然是可以用Splay维护的，同时Splay也同时支持插入和修改操作。对于题目要求的三种操作，我们这样实现：

1. 查询操作：二分长度，令两个位置为x,y。我们查找排行为x-1和x+len的两个节点，令其为pre和nxt。将pre splay到根(pre->splay())，nxt splay到pre的儿子(nxt->splay(pre))。那么nxt的左儿子就是我们需要的区间。由于旋转操作时维护了Hash值，所以我们直接取该节点上维护的Hash值就是这段区间的Hash值。对于y的Hash值同理，然后比较Hash值就能判断两个字符串是否相等。
2. 插入操作：查找排行为x和x+1的两个节点，x splay到根，x+1 splay到x的儿子，对x+1的左儿子直接插入即可
3. 修改操作：找到排行为x的节点直接修改

需要注意的是由于使用Splay时我们通常会插入头尾两个辅助节点，我们maintain Hash值的时候不能把这两个值算上。

感想

CF Rank: 60/273
emmmm这比赛的题非常友好啊？我们队5个小时没法摸鱼有题可做，A题好像是个树形dp，L是个枚举时间最短路？算了有空再补吧。。

思路

参考了Claris老师的博客。该题最精髓的操作就是将形如A[i]B[i]的式子做一个反转，形成A[n-i]B[i]的卷积形式，这样就能够往FFT上靠。似乎BZOJ一道权限题“快速傅里叶变换”也是使用了这样一个思路，所以这应该算一个比较经典的技巧，在知道这一步后这道题就是FFT的模板题了。

思路

与poj 3690的处理方法非常相似，先利用单调队列处理行长度为n的段的最大最小值，储存在一个数组里，然后在对处理完的数列纵向再跑一次长度为n的单调队列。

思路

我们可以首先取最后一个字符串字典序最小的后缀，然后把它接到前一个串的后面，再求这个串字典序最小的后缀，不断重复以上操作我们就能得到题目需要的字符串。其正确性可以用反证法证明：假设我们最后一个字符串不取字典序最小的后缀，那么我们一定能通过替换最小的后缀来得到一个更小的字符串，与原串是字典序最小的字符串矛盾。但这样的时间复杂度是O(n^2)的(字符串比较O(n))，我们期望的是一个O(nlogn)的算法。注意到我们取的过程是从最后一个字符慢慢往前走，如果我们保存每个位置的hash值（这里hash的方法需要是Hash=Hash*seed+letter），然后通过现在的hash值减之前的hash值乘以偏移量，那么我们就能得到一段前缀的hash值，也就是可以O(1)的比较一段前缀是否相等。因此我们可以想到二分前缀的长度（显然具有单调性），通过上述hash的方法来得到两个字符串最长的LCP。知道了两个字符串最长的公共前缀后，我们只要比较最长公共前缀后面的第一个字符即可比较两个字符串的大小。

思路

题意是给你n个多米诺骨牌，骨牌的两面都有数字，要求你找出一个放置序列使得相邻两个骨牌相对的两面数字相同。注意到如果我们以数字为点（0-7），同时以骨牌建边的话，那么这个问题就是一个欧拉路径问题。欧拉路径是否存在可以用是否所有点度数都是偶数或者图中是否仅有两个奇数度的点这种方法来判定，注意本题的No solution还有图不连通的可能性，要特别判断。在完成欧拉路径是否存在的判定后，我们考虑如何输出路径。我们不能dfs暴力尝试，这样的复杂度显然是不能接受的。看了题解后学习到了一个全新的fleury算法，时间复杂度O(m)，即将所有边遍历一次。
hihocoder上的伪代码，如果有奇数度的点，我们从奇数度的点开始dfs，否则任取一个出现过的点。

1
2
3
4
5
6
7

DFS(u):
	While (u存在未被删除的边e(u,v))
		删除边e(u,v)
		DFS(v)
	End
	PathSize ← PathSize + 1
	Path[ PathSize ] ← u

参考

hihocoder-欧拉路·二

Dilworth定理学习笔记

思路

根据题意，我们需要对一个序列执行区间加和计算最长的递增/递减/先增后减序列。对于区间加法，很自然想到线段树，我们考虑线段树维护序列。我们这样考虑，维护一个区间最左端符合条件序列的长度，维护一个区间最右端符合条件序列的长度。push_up的时候用跨过中点的合法序列，左儿子最大值，右儿子最大值一起考虑来更新最大值。在常规序列处理线段树的情况下，我们会发现我们合并时需要左儿子最右端序列的值和右儿子最左端序列的值（合并左右儿子需要比较大小）。注意在这里我们如果用常规的线段树维护序列，这个时候我们要把lazy的值推到最深的儿子，显然这样lazy操作失去了他的意义，在合并时会导致时间复杂度爆炸。因而我们考虑线段树维护差分序列，这样我们每次只要单点更新两个端点。现在我们可以放心合并不需要担心单点查询复杂度的问题。在合并时，我们要考虑这样几种情况：

1. 不合法情况，无法用跨过中点的左右两个序列合并来更新节点最大值：右端序列和左/右差分序列有一个为0（左右有一段常数列），左边为-1（递减）右边为1（递增），此时节点的左连续序列就是左儿子的左连续序列，右连续序列就是右儿子的右连续序列，直接上传，最大值继承左右儿子的最大值。
2. 合法情况：我们更新在继承左右儿子的最大值的基础上再用跨过中点的序列来更新节点的最大值。注意此时的左右连续序列不能想都不想像刚刚那样直接继承，我们考虑这样一个例子，如果左儿子的整个覆盖的区间都是连续递增的，就比如为1，2，3，而此时右儿子是4，5，6。我们显然能发现这个时候区间的左连续序列长度是6而不是3。所以我们需要在左右连续序列的计算上分类讨论。具体细节见代码。