题解：P17704 [ICPC 2019 Nanjing R] Paper Grading

· · 题解

思维难度黄题左右吧。

看到最长公共前缀长度，要么后缀数组要么字典树，显然多串不适合后缀数组于是字典树。

考虑字典树后，发现没有字符串的字符修改，于是字典树形态不变，考虑一个询问的形式 p,l,r,k 观察到，答案就是用 p 在字典树上走 k 步到的点假设是 u 则答案就是其子树中在下标在 [l,r] 的串的个数，由于字典树形态不变，于是直接转成 dfn 区间数点，观察到就是一个二维数点的形式。

更具体的 dfn_{u} \le x \le dfn_{u}+siz_{u}-1,l \le idx_{x} \le r 显然的二维数点形式，由于有修改，由于是单点修改，于是树套树或分治解决。

提供赛时代码。

/*
啥子题，交一个记录一下，懒得写了。

考虑字典树，然后转成二维数点，然后树套树或者cdq随便做做就行了。
*/