Luogu5310 [Ynoi2011] 遥远的过去

题意：定义两个序列匹配当且仅当它们离散化后相同。

给出两个序列 ，支持对 进行单点修改，保证 中的数字两两不同。

每次修改后，询问 在 中匹配的次数。

允许离线，，时限 。

---

简单题。

先将数字离散化。

使用 ，先求出 的每个长度为 的子串的 值，然后动态维护 的 值，容易得到答案。

• 处理 的子串 Hash 值

滑动窗口。我们需要支持：

• 在前端删除一个数

• 在后端插入一个数

使用权值线段树维护。

每个数有两个权值，排名和位权。整个串的 值是 “排名 位权” 的和。

当在前端删除一个数 时，去掉它的贡献，然后将大于 的所有数排名减 。

当在后端插入一个数 时，他的位权为 。将所有其他数的位权乘以 ，并将大于 的所有数排名加 。

• 处理

只需支持单点修改。

每个数的位权不会变，但是排名可能会变，同样容易使用线段树维护。

复杂度 。