P14470 [COCI 2025/2026 #1] 松鼠 / Zagi

题目背景

本题满分 $110$。

Zagi 是 1987 年萨格勒布夏季世界大学生运动会的吉祥物。

Zagi 一只松鼠，它在当时非常受欢迎，成为了萨格勒布的一个标志性形象。

题目描述

Jakov 和 Toni 在玩游戏。

最初有一个正整数序列。Toni 先手，两人轮流进行以下的操作：

操作

选定一个序列和在这个序列中出现的一个整数 $x$。在选定序列中将所有 $x$ 全部删去，在删去的位置将选定序列劈成若干个小序列。

无法操作者判负。

给定长度为 $n$ 的正整数序列 $a_1\sim a_n$。$q$ 次询问，每次询问给定 $l,r$，若以 $[a_l,\ldots,a_r]$ 作为初始序列，Toni 先手，在双方都最优操作的前提下，求出获胜者。

输入格式

第一行，两个正整数 $n,q$（$1\le n,q\le 10^5$）。

第二行，$n$ 个正整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le 32$）。

接下来 $q$ 行，第 $i$ 行两个正整数 $l_i,r_i$（$1\le l_i\le r_i\le n$），描述一次询问。

输出格式

对于每个询问，若 Toni 胜利，输出 $\texttt{Toni}$；否则输出 $\texttt{Jakov}$。

输入输出样例 #1

输入 #1

6 4
1 3 2 3 1 2
1 1
2 3
2 4
1 3

输出 #1

Toni
Jakov
Toni
Toni

输入输出样例 #2

输入 #2

10 5
3 3 3 1 2 2 1 2 2 1
2 3
9 10
5 6
5 8
3 7

输出 #2

Toni
Jakov
Toni
Toni
Toni

说明/提示

样例解释

样例一解释：第三次询问中，初始序列为 $[3,2,3]$。Toni 选定 $x=2$，劈成两个长为 $1$ 的序列。无论 Jakov 选哪个序列，Toni 都会选择剩下那个序列操作，Jakov 无法操作而负。

子任务

• $\text{Subtask 1 (15 pts)}$：$n,q\le 10$。
• $\text{Subtask 2 (11 pts)}$：$n,q\le 1000,a_i\le 2$。
• $\text{Subtask 3 (18 pts)}$：$n,q\le 1000$。
• $\text{Subtask 4 (14 pts)}$：$a_i\le 2$。
• $\text{Subtask 5 (23 pts)}$：$a_{l_i}=a_{r_i}$。
• $\text{Subtask 6 (29 pts)}$：无额外限制。