主要思路
先差分，然后再来做这个不相交子串匹配的问题。
我们可以考虑用线段树来维护 endpos 集合，然后用启发式合并的方式来计算一个后缀点与当前点集之间产生的贡献。有两种情况：
- 当前为 endpos 的最长长度、与当前位置 \(x\) 不相交的子串。这个可以直接暴力线段树上查个数。
- 长度小于 \(maxdep\)，以 \(endpos\) 在左边的情况为例：答案的贡献就是 \(x – endpos – 1\)。
P5327:「ZJOI2019」语言 – 题解
主要思路
好题！好题！
这个题首先需要了解到一个性质：每个点所能到达的、进行贸易的国家的集合可以形成一个连通的生成子图。所以，我们最后需要求的就是每个国家对应的集合的大小。
如何去快速求这个东西呢？我们需要把 \(m\) 个路径中每个跨过当前点 \(u\) 的路径给拿出来，然后算这些路径的交集。这样是一种计算的方法，但是确实不快速。
Continue reading →P4577:「FJOI2018」领导集团问题 – 题解
树上 LIS 的套路之一
因为是从 yyb 博客上抓的题，所以知道可以用线段树做。大概想了想，初步的想法就是用线段树来维护不同高度(?)的最长子序列长度。其实这样是可以的，输入高度时就先塞到每个点的动态开点线段树里，然后就可以把儿子的进行合并。合并儿子的时候，维护至少为 \(x\) 时能得到的最长子序列长度，所以我们可以用差分的方式来做一做（当然也可以做标记永久化的区间加）：从 \(w_u\) 的位置开始加上一个一，然后把上一次的 \(1\) 给删掉。
后缀自动机 | SAM
概述
后缀自动机是处理字符串信息的有力工具。后缀自动机存储在 Trie 树上，配合 Link 指针就可以被认为是一张 DAG。任意一条从原点出发的路径都可以被认为是这个字符串的一个子串，且在后缀自动机上不会存在重复的子串信息（然而，我们可以进行一些扩展来维护子串位置信息）。
P4556:「Vani有约会」雨天的尾巴题解
主要思路
这道题可以离线回答，很大概率是什么树上差分之类的东西。但是树上差分无法维护区间信息，然后想到用权值线段树来维护。如果暴力开\(1e5\)个线段树来维护会 GG，但是我们可以动态开点，然后每个点对应的线段树大小差不多为\(O(\log n)\)级别的，这样空间就可以接受的了。
既然有了很好用的动态开点线段树，我们就可以用树上差分那一套路，在端点和\(LCA\)处打标记，然后考虑从下往上合并答案。合并可以用线段树合并，复杂度为重合部分，差不多就是\(O(\log n)\)。然后就没了，很傻逼的一道题。
「APIO2012」派遣题解
思路
可并堆思路：自顶向上做大根堆，然后弹出堆顶直到整个堆的和小于 m。（性质：父亲节点不会选择子树不包含的忍者）。
线段树合并思路：没看懂，不写了。
代码
// P1552.cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;
const int MAX_N = 100100;
struct node
{
int lson, rson;
ll dist;
} nodes[MAX_N];
ll n, m, li[MAX_N], ci[MAX_N], master, ans = -2e9;
ll sum[MAX_N], siz[MAX_N], pt[MAX_N];
vector<int> G[MAX_N];
int merge(int x, int y)
{
if (!x || !y)
return x + y;
if (ci[x] < ci[y])
swap(x, y);
nodes[x].rson = merge(nodes[x].rson, y);
if (nodes[nodes[x].lson].dist < nodes[nodes[x].rson].dist)
swap(nodes[x].lson, nodes[x].rson);
nodes[x].dist = nodes[nodes[x].rson].dist + 1;
return x;
}
void dfs(int u)
{
sum[u] = ci[u], siz[u] = 1, pt[u] = u;
int siz_ = G[u].size();
for (int i = 0; i < siz_; i++)
{
int to = G[u][i];
dfs(to);
sum[u] += sum[to], siz[u] += siz[to];
pt[u] = merge(pt[u], pt[to]);
}
while (sum[u] > m && siz[u])
{
sum[u] -= ci[pt[u]];
pt[u] = merge(nodes[pt[u]].rson, nodes[pt[u]].lson);
siz[u]--;
}
ans = max(ans, li[u] * siz[u]);
}
int main()
{
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; i++)
{
ll fa;
scanf("%lld%lld%lld", &fa, &ci[i], &li[i]);
if (fa == 0)
master = i;
else
G[fa].push_back(i);
}
dfs(master);
printf("%lld", ans);
return 0;
}
我之前把数据结构搞复杂了，看了题解发现好简洁。还是要做减法啊。