fsy's blog

拖了一周才说的通知

电脑出现致命问题，短期内难以修理。在电脑修理完成前，本博客无限期停更。这段时间内的文章将用 CSDN 发布。

个人向吐槽：怎么这么多图论题啊

CSP-S 2019，T1：使用 unsigned long long

CSP-S 2020，T2：需特判 $2^{64}$

NOIP 2020，T1：需要使用简单高精度

NOIP 2021：？？？？

注：本文翻译自 Поиск всех тандемных повторов в строке. Алгоритм Мейна-Лоренца 及其英文翻译版 Finding repetitions，转载时请标注出原文与本文的出处。

给定一个长度为 $n$ 的字符串 $s$。

我们将一个字符串连续写两遍所产生的新字符串称为 **重串 (repetition)**。下文中，为了表述精准，我们将被重复的这个字符串称为原串。

换言之，一个重串等价于一对下标 $(i, j)$，其使得 $s[i \dots j]$ 是两个相同字符串拼接而成的。

你的目标是找出给定的字符串 $s$ 中所有的重串。或者，解决一个较为简单的问题：找到字符串 $s$ 中任意重串或者最长的一个重串。

最近颓废的一批，逼自己翻译点东西。

翻译自 BIJECTIVE PROOF PROBLEMS，部分表述有修改。

进度：28 / 249 (upd on 2021.2.27)

给定长度为 $n$ 的序列 $a$。

定义一轮排序为：从前往后比较相邻的两个数，若前面的数大于后面的数，则交换这两个数。

进行 $q$ 次单点修改，每次修改后，回答当前序列需要几轮排序才能变成一个不下降序列。

$n, q \leq 500000$。

题解

修锅时遇到的坑

• 用 npm-check-updates 更新时，使用 ncu 指令显示：

1

Hmm... (后面一长串东西)

解决方法：使用指令

1
2

ncu --loglevel verbose --packageFile package.json
ncu -u --packageFile package.json

高次剩余问题：

给定正整数 $a, y, p$，其中 $p$ 是质数，求 $x \in [0, p)$ 满足：
$$
x^a \equiv y \pmod p
$$
此处的 $x$ 被称为一个高次剩余，有时也译作离散根（discrete root）。

简要题意

• 一开始有 $k$ 种生物，每种生物有 $n$ 个属性 $a_{k,1}, a_{k,2}, \cdots, a_{k,n}$。现有以下 $3$ 种操作：
• (1). 给定两个正整数 $x$，$y$。创建一个新生物，此生物的第 $i$ 项属性为 $\max(a_{x,i}, a_{y,i})$。
• (2). 给定两个正整数 $x$，$y$。创建一个新生物，此生物的第 $i$ 项属性为 $\min(a_{x,i}, a_{y,i})$。
• (3). 给定两个正整数 $x$，$y$。输出第 $x$ 个生物的第 $y$ 项属性。
• 新生物的编号获得最小的未使用数字。
• 操作数 $q \leq 10^5$，属性数 $n \leq 10^5$，$k \leq 12$。

重链剖分，可以将树上的任意一条路径划分成不超过 $\mathcal{O}(\log n)$ 条连续的链，每条链上的点深度互不相同（即是自底向上的一条链，链上所有点的 LCA 为链的一个端点）。——OI wiki