LeetCode5. 最长回文子串（Manacher 算法）
题意
求字符串的最长回文子串。
思路
使用 Manacher 算法来解决，时间复杂度 $\mathrm O(n)$。
首先，我们假设 $f_i$ 是以 $i$ 为中心的最长回文子串的半径，且最长回文子串的长度总是奇数（也就是说总是以某个字符为轴对称）。一个朴素的算法是枚举每个 $i$，然后向两边扩展，时间复杂度为 $\mathrm O(n^2)$。
注意到，如果以 $mid$ 为中心的回文子串范围内存在 $i$ 和 $j$ 关于 $mid$ 对称（即 $i + j = mid \times 2$），那么总是有 $f_j \ge f_i$，当然，这个性质成立的前提是以 $i$ 为中心、以 $f_i$ 为半径的回文子串在上述提到的以 $mid$ 为中心的回文子串的范围内。那么如果超出了范围呢？那么在范围内的部分至少是成立的，即 $f_j \ge \min(f_i, i - (mid - f_{mid}))$，可以注意到，其实 $i - (mid - f_{mid})$ 等价于 $(f_{mid} + mid) - j$，因此公式可以写成 $f_j \ge \min(f_i, (f_{mid} + mid) - j)$。
有了之前得到的公式，我们现在可以考虑利用这一性质加速最长回文子串的求解。让重新审视之前 $\mathrm O(n ^ 2)$ 的算法，当我们枚举每个 $i$ 时，先利用之前的性质求出 $j$，然后在 $f_j$ 的基础上继续向两边扩展，可以省略掉大量重复的计算。具体来说，为了使省略重复计算的部分尽可能多，我们便希望先前计算过的回文子串的右边界也就是 $mid + f_{mid} - 1$ 尽可能大，因此可以令 $maxRight$ 是当前已经找到的回文子串右边界的最大值，$maxMid$ 是这一最大值对应的回文子串的中心，这样先前的公式便可以重新修改为 $f_j \ge \min\left(f_{maxMid \times 2 - j}, (maxRight - j)\right)$。这样，我们便可以将 $f_j$ 的初始值先赋为 $\min\left(f_{maxMid \times 2 - j}, (maxRight - j)\right)$，在此基础上继续求解。
那么还有最后一个问题，如果最长回文子串长度不是奇数，而是偶数呢？这时候我们可以在每个字符之间插入一个特殊字符，比如 #，这样就可以保证最长回文子串长度为奇数。
自此，Manacher 算法便完成了，但 Manacher 算法的时间复杂度并不能显然得到。我们首先从 $\mathrm O(n ^ 2)$ 的朴素算法开始，每次枚举 $i$ 的迭代都会使 $maxRight$ 恒定增加 $1$，每次迭代的时间复杂度为 $\mathrm O(对应回文串长度)$。而在 Manacher算法中，每次枚举 $i$ 的迭代 $maxRight$ 的增量与在对称位置回文串长度的基础上新扩展的回文串长度增量相同（这里可以分类讨论一下，如果 $f_j$ 取到了 $f_{maxMid \times 2 - j}$，也就是没有超过 $maxRight$，那么以对称位置为中心的回文串还在 $(maxRight - f_{mid} \times 2 + 1,maxRight)$ 范围内，既然 $f_i$ 代表的回文串没能继续扩展，那么在对称位置的 $f_j$ 代表的回文串一样不能继续扩展，因此下一次比较一定会失败；如果 $f_j$ 取到了 $(maxRight - j)$，那么继续扩展如果成功，$maxRight$ 就会继续增大。因此可以证明 $maxRight$ 的增量与新扩展的回文串长度增量相同），因此所有迭代的复杂度之和为 $\mathrm O(n)$，且与外层枚举 $i$ 的循环独立，因此总复杂度为 $\mathrm O(n)$。
代码
提交记录：4 ms(99.72%) / 7 MB(80.82%)
const int maxn = 2005;
char ss[maxn];
class Solution {
public:
string longestPalindrome(string s) {
int n = s.length() << 1 | 1, f[maxn], maxRight = 0, maxMid = 0, ansf = 0, ans = 0;
memset(ss, '#', sizeof(ss)); // 字符之间填充 '#' 作为特殊字符
for (int i = 0; i < s.length(); ++i) ss[i << 1 | 1] = s[i]; // 隔字符填充，将回文串长度统一为奇数
for (int i = 1; i < n; ++i) { // 枚举 i 计算 f[i]
f[i] = maxRight > i ? min(f[(maxMid << 1) - i], maxRight - i) : 1; // 在对称位置结果的基础上继续计算
while (i - f[i] >= 0 && i + f[i] < n && ss[i - f[i]] == ss[i + f[i]]) ++f[i]; // 在不越界的情况下扩展以 ss[i] 为对称轴的回文串长度
if (i + f[i] >= maxRight) maxRight = i + f[i], maxMid = i; // 更新右边界的最大值
if (ansf < f[i]) ansf = f[i], ans = i; // 更新最长回文子串答案
}
s = ""; // 用答案覆盖输入字符串，减小内存开销
for (int i = ans - f[ans] + 1; i < ans + f[ans]; ++i) if (ss[i] != '#') s += ss[i]; // 构造答案
return s;
}
};
LeetCode68. 文本左右对齐
题意
将一些字符串进行宽度固定的排版，使空格尽量均匀分布。
思路
简单模拟即可。对于每行，首先贪心地放单词，并且从第二个单词开始先暂时放一个空格。接着通过剩余的空格与该行的单词数的商与余数确定每个单词之间放置空格的数量。最后根据计算构造输出。
需要注意的是最后一行和只有一个单词的行完全左对齐，单词之间插入一个空格，剩余的空格全放右边即可。
代码
提交记录：0 ms(100%) / 7.5 MB(17.65%)
class Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
int nowLength = words[0].length(), startIndex = 0;
vector<string> ans;
for (int i = 1; i < words.size(); ++i) {
if (nowLength + words[i].length() + 1 <= maxWidth) {
nowLength += words[i].length() + 1; //
} else {
ans.emplace_back("");
string& _ans = ans.back();
if (i - startIndex == 1) for(_ans = words[startIndex], nowLength = maxWidth - nowLength;nowLength--;) _ans += " "; // 如果只有一个单词，则直接放置单词，然后在右侧填充足够的空格
else {
for (int j = startIndex, spaceNum = (maxWidth - nowLength) / (i - startIndex - 1), spaceLeft = (maxWidth - nowLength) % (i - startIndex - 1), space; space = spaceNum + (spaceLeft > 0 ? 2 : 1), j < i; ++j, --spaceLeft) { //
_ans += words[j];
if (j + 1 < i) while (space--) _ans += " ";
}
}
nowLength = words[i].length(), startIndex = i;
// ans.emplace_back(_ans);
}
}
ans.emplace_back("");
string& _ans = ans.back();
for (int i = startIndex; i < words.size(); ++i) _ans = _ans + words[i] + (i + 1 < words.size() ? " ": "");
nowLength = maxWidth - nowLength;
while(nowLength--) _ans += " ";
// ans.emplace_back(_ans);
return ans;
}
};
class Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
int nowLength = words[0].length(), startIndex = 0;// 先默认将第一个单词放入行内，nowLength 为当前行内已经放置包含空格在内的字符的个数，startIndex 是指当前行第一个单词的编号
vector<string> ans;
auto placeWords = [&](int i, int spaceNum, int spaceLeft, int isLeft) {
ans.emplace_back(""); // spaceNum 为每个单词之间至少需要多填充的空格数，spaceLeft 为需要多填充一个空格的位置数，isLeft 表示是否需要左对齐（是否为最后一行或只有一个单词）
string& _ans = ans.back(); // 为了编码方便，将 _ans 作为 ans 中当前需要构造的行的别名
for (int j = startIndex, space; space = spaceNum + (spaceLeft > 0 ? 2 : 1), j < i; ++j, --spaceLeft) { // 构造 space 为当前单词后需要填充的空格数量
_ans += words[j]; // 填充单词
if (j + 1 < i) while(space--) _ans += " "; // 除最后一个单词外填充单词后的空格
}
nowLength = isLeft ? maxWidth - nowLength : 0; // 计算左对齐需要填充的空格数
while(nowLength--) _ans += " "; // 填充右侧行末的空格
if (i != words.size()) nowLength = words[i].length(), startIndex = i; // 不是最后一行则将下一个单词放入行内
};
for (int i = 1; i < words.size(); ++i)
if (nowLength + words[i].length() + 1 <= maxWidth) nowLength += words[i].length() + 1; // 若下一个单词加空格可以放至行内，则更新 nowLength
else placeWords(i, i - 1 - startIndex ? (maxWidth - nowLength) / (i - startIndex - 1) : 0, i - 1 - startIndex ?(maxWidth - nowLength) % (i - startIndex - 1) : 0, !(i - 1 - startIndex)); // 如果空位置不够，则开始构造当前行的答案
placeWords(words.size(), 0, 0, 1); // 左对齐填充最后一行
return ans;
}
};
LeetCode699. 掉落的方块
题意
将指定区间覆盖为区间最值与区间宽度的和，求每次区间覆盖后的全局最值。
思路
涉及的操作为区间最值与区间覆盖，且区间较大（$[0,10^8+10^6]$）传统的做法是离散化后使用线段树/分块算法来解决。但不管是线段树还是分块都难写难调，加上离散化后码量较大，因此我们此处使用一种基于 C++ STL 中 set 的数据结构珂朵莉树(Chtholly Tree)**（又称老司机树(Old Driver Tree, ODT)**）来解决此问题，由于基于 set，因此不需要进行离散化操作，且该数据结构在本题中只需要 split 和 assign 两种操作，代码极其简单好写，且对于随机数据复杂度为 $\mathrm O(n\log n)$，完全可以通过此题。
珂朵莉树的核心思想是把值相同的区间合并为一个节点保存在 set 内。具体来说，set 中存储的节点信息包含 $l,r,v$，代表区间 $[l,r]$ 的值为 $v$。
珂朵莉树最核心的操作是 split，用于将保存区间 $[l,r]$ 的节点分裂为 $[l, x)$ 和 $[x,r]$ 两个区间，具体来说，这一操作利用了 set 自带的二分查找 upper_bound 函数快速查找包含 $x$ 的区间对应的节点，然后将区间 $[l,r]$ 所在的节点删除，然后再重新插入区间 $[l,x)$ 和 $[x,r]$ 对应的新节点，并返回 $[x,r]$ 区间对应的节点迭代器。有了这一操作，对于任何 $[l,r]$ 区间上的操作，都可以变为 set 中元素区间 $\left[split(l), split(r + 1)\right)$ 上的操作。
在 split 的基础上，区间覆盖操作 assign 便可以简单完成。首先对区间左右端点所在的区间执行 split 分裂操作，然后删除元素区间 $\left[split(l), split(r + 1)\right)$，最后将需要覆盖区间以及新值重新插入 set 即可。在此题中比较特殊的是需要先遍历要删除元素区间求出区间最值，然后加上区间宽度再进行区间覆盖操作。
接下来计算珂朵莉树的复杂度：
- 令 $t$ 表示
set中的总段数，对于长度为 $n$ 的区间（在本题中对应于离散化后的值个数），则 $m$ 次split操作后，平均每个端点到最后仍然存在的概率为 $O(\frac 1 m)$，而每个操作会创建 $\mathrm O(1)$ 个端点，那么对于倒数第 $i$ 个操作创建的端点到最后仍然存在的概率为 $\mathrm O(\frac 1 i)$，根据随机变量之间相互独立求和可得 $\mathbb E[t] = \mathrm O(n\cdot \frac1m + \sum_{i = 1} ^ m \frac1i) = \mathrm O(\frac nm + \log m)$，因此 $t$ 的期望为 $\mathrm O(\frac n m + \log m)$。而当 $m = \mathrm \Theta(n)$ 时，$m$ 次操作过程中 $t$ 第的期望平均值为 $\mathrm O(\log n)$。此外，由于set内部实现方式为红黑树，因此split中lower_bound和erase的复杂度均为 $\mathrm O(\log t)$，因此split单次操作的总平均复杂度为 $\mathrm O(\log\log n)$。 - 而对于
assign区间覆盖操作，原数据结构只使用两次split操作、一次set的erase和insert操作，平均复杂度仍可以保证为 $\mathrm O(\log\log n)$，但由于本题增加了遍历求区间最值的操作复杂度为 $\mathrm O(t)$，因此复杂度为 $\mathrm O(\log n)$。
综上，代码（$n$ 次 assign 操作）的总复杂度为 $\mathrm O(n\log n)$。
代码
提交记录：24 ms(90.44%) / 14.9 MB(50.73%)
class Solution {
public:
struct Node_t
{
int l, r; // 表示区间 [l, r]
mutable int v; // 便于直接修改已经插入 set 的元素的值，本题没有用到此特性
Node_t(const int &il, const int &ir, const int &iv) : l(il), r(ir), v(iv) {}
bool operator<(const Node_t &o) const { return l < o.l; }
};
set<Node_t> odt;
int ans = 0;
const int n = 1e9; // 区间右端
auto split(int x) // 区间分裂
{
if (x > n) return odt.end(); // 若超出范围则返回 set 结尾的迭代器
auto it = --odt.upper_bound(Node_t{x, 0, 0}); // 红黑树上二分查找 x 所在的区间节点
if (it->l == x) return it; // 若 x 是区间左端点则无需分裂
int l = it->l, r = it->r, v = it->v;
odt.erase(it); // 删除原区间 [l, r]
odt.insert(Node_t(l, x - 1, v)); // 插入区间 [l, x)
return odt.insert(Node_t(x, r, v)).first; // 插入区间 [x, r] 并返回节点迭代器
}
void assign(int l, int r, int v) // 区间覆盖
{
auto itr = split(r + 1), itl = split(l); // 将 l 和 r 所在的区间的节点分裂
int h = 0;
for (auto it = itl; it != itr; ++it) h = max(h, it->v); // 求区间最值
odt.erase(itl, itr); // 删除 [l, r] 内的所有区间节点
odt.insert(Node_t(l, r, h + v)); // 插入区间 [l, r] 节点
if (ans < h + v) ans = h + v; // 更新答案
}
vector<int> fallingSquares(vector<vector<int>>& positions) {
odt.insert(Node_t(0, 0, 0)); // 插入初始元素，初始化珂朵莉树
vector<int> _ans;
for (auto& p : positions) assign(p[0], p[0] + p[1] - 1, p[1]), _ans.emplace_back(ans); // 执行区间覆盖操作，并记录答案
return _ans;
}
};
