yl-9/probench huggingface dataset:
# 好好好数

## 题目描述

> $\,\,\,\,\,\,\,\,\,$在上周的周赛 $\textsf {Round 57}$ 中，双好数的构造题非常有趣，于是，在这周的周赛中，好数又回来了！但是其实这两题并没有什么关系，还是重新看看题吧！ 

$\,\,\,\,\,\,\,\,\,$小苯有一个数字 $n$ ，他定义 $\texttt{k-}$ 好数为：可以表示为若干个不同的 $k$ 的整数次幂之和的数字。 

$\,\,\,\,\,\,\,\,\,$例如：$30 = 3^3+3^1$ ，因此 $30$ 是一个 $\texttt{3-}$ 好数，而 $2$ 不是一个 $\texttt{3-}$ 好数（虽然有：$2=3^0+3^0$，但好数要求次幂数字不同）。  
$\,\,\,\,\,\,\,\,\,$小苯有一个整数 $n$，他想知道 $n$ 最少可以被表示成几个 $\texttt{k-}$ 好数的和，请你帮帮他吧。

## 输入描述:
    
    
     $\,\,\,\,\,\,\,\,\,$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\le T\le 10^4\right)$ 代表数据组数，每组测试数据描述如下：  
    
    
      
    
    
    $\,\,\,\,\,\,\,\,\,$在一行上输入两个整数 $n, k\ (1 \leq n \leq 10^{18})\ ,\ (1 \leq k \leq 10^{18})$ ，表示小苯的数字 $n$ 、$\texttt{k-}$ 好数的 $k$ 。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，代表最少可以将 $n$ 分解成 $\texttt{k-}$ 好数的个数。

示例1 

## 输入
    
    
    2
    60 3
    114 514

## 输出
    
    
    2
    114

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,$对于第一组测试数据，$30$ 是 $\texttt{3-}$ 好数，而 $60=30+30$ ，因此可以分解为两个 $\texttt{3-}$ 好数，可以证明不存在更优的分解方式。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 数学
Difficulty: 1200
# 好好好数组

## 题目描述

$\,\,\,\,\,\,\,\,\,$对于数组 $\\{a_1,a_2,\dots,a_n\\}$ ，我们定义它是好的，当且仅当：对于全部的 $i \in [1,n)$ ，$a_i = a_{i+1} \bmod i$ 总是成立；  
  
$\,\,\,\,\,\,\,\,\,$现在，你可以选择 $n$ 个整数组成一个数组，使得这个数组是好的；同时，你还需要保证：  
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$数组中至少存在 $m$ 个不同的数字；  


$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$数组中的每一个数字都满足 $\in [0,n]$ 。 

  


$\,\,\,\,\,\,\,\,\,$在这里，$\bmod$ 代表取模。  


## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\le T\le 10^5\right)$ 代表数据组数，每组测试数据描述如下：  
      
    $\,\,\,\,\,\,\,\,\,$在一行上输入两个整数 $n,m \left( 1\le m \le n \le 10^7\right)$ 代表你需要挑选的数字数量、不相同数字个数的限制。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,$对于每一组测试数据，在一行上输出一个整数，代表满足条件的数组数量。

示例1 

## 输入
    
    
    3
    2 2
    3 2
    2 1

## 输出
    
    
    2
    3
    3

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,$在第一组测试数据中：  
    $~~~~~~~~~$$\bullet\ $数组 $\{0,1\}$ 满足条件，因为 $a_2 \bmod 1=1 \bmod 1 = 0$ ；  
    $~~~~~~~~~$$\bullet\ $数组 $\{0,2\}$ 满足条件，因为 $a_2 \bmod 1=2 \bmod 1 = 0$ ；  
    $\,\,\,\,\,\,\,\,\,$在第二组测试数据中，$m=2$ 时数组 $\{0,0,2\}$ 和 $\{0,1,1\}$ 均满足条件，$m=3$ 时数组 $\{0,1,3\}$ 满足条件。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 数学, 暴力
Difficulty: 1400
# 随机化游戏时间？

## 题目描述

> $\,\,\,\,\,\,\,\,\,$注：本题和 $\sf hard$ 版本的区别在于排列已知，询问概率。 

$\,\,\,\,\,\,\,\,\,\,$小 $\mathcal L$ 有一个 $1\sim n$ 的 _排列_ ，她从中选择了一个数字作为自己的幸运数。 

$\,\,\,\,\,\,\,\,\,\,$小 $\mathcal H$ 每次会询问小 $\mathcal L$ 一个区间 $[l,r]$ ，随后小 $\mathcal L$ 会告诉他这个区间里有多少个数**小于等于** 她的幸运数。  


$\,\,\,\,\,\,\,\,\,\,$直到 $m$ 次询问全部完成，如果小 $\mathcal H$ 依旧无法唯一确定幸运数是什么，他会在全部可能的数字里等概率随机挑选一个。 

$\,\,\,\,\,\,\,\,\,\,$你需要直接输出 $m$ 次询问后他猜对数字的概率，保证数据有解。 

  


$\,\,\,\,\,\,\,\,\,\,$长度为 $n$ 的 _排列_ 是由 $1 \sim n$ 这 $n$ 个整数、按任意顺序组成的数组，每个整数恰好出现一次。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是一个排列（数组中的 $2$ 出现了两次），$[1,3,4]$ 也不是一个排列（长度为 $3$ 但数组中有 $4$）。  


## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\le T\le 200\right)$ 代表数据组数，每组测试数据描述如下：
    
      
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入两个整数 $n,m\left( 1\le n,m \le 10^5\right)$ 代表小 $\mathcal L$ 的排列长度和最多询问次数。  
    $\,\,\,\,\,\,\,\,\,\,$第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n \left( 1\le a_i \le n\right)$ 代表排列元素，保证数字两两不同。  
    
    
    $\,\,\,\,\,\,\,\,\,\,$随后 $m$ 行，每行输入三个整数 $l,r,k\left(1\le l \le r \le n;\ 0 \le k \le r - l + 1 \right)$ 代表询问区间、区间内小于等于幸运数的数字个数。
    
      
    
    
    $\,\,\,\,\,\,\,\,\,\,$除此之外，保证所有的 $n$ 之和不超过 $2\times 10^5$ ，所有的 $m$ 之和不超过 $2\times 10^5$ 。
    
    $\,\,\,\,\,\,\,\,\,\,$本题数据保证有解。  
    

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$对于每一组测试数据，在一行上输出一个整数，代表小 $\mathcal H$ 猜中幸运数的概率。特别的，如果概率为 $100\%$ ，则需要在同一行上额外输出一个整数，代表小 $\mathcal L$ 的幸运数。
    
      
    
    
    $\,\,\,\,\,\,\,\,\,\,$可以证明答案可以表示为一个不可约分数 $\frac{p}{q}$ ，为了避免精度问题，请直接输出整数 $\left(p \cdot q^{-1} \bmod M\right)$ 作为答案，其中 $M = (10^9+7)$ ，$q^{-1}$ 是满足 $q\times q^{-1}  \equiv 1 \pmod{M}$ 的整数。

示例1 

## 输入
    
    
    2
    6 2
    5 6 4 3 2 1
    5 6 2
    1 2 0
    5 3
    5 4 2 1 3
    1 3 1
    5 5 1
    3 5 3

## 输出
    
    
    333333336
    1 3

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$对于第一组测试数据，初始时，幸运数的范围为 $[1,6]$ 。  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● $[5,6]$ 区间有两个数字小于等于幸运数，可以将范围缩小至 $[2,6]$ ；  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● $[1,2]$ 区间中没有数字小于等幸运数，可以将范围缩小至 $[2,4]$ ；  
    $\,\,\,\,\,\,\,\,\,\,$综上，幸运数只有可能是 $2$ 、$3$ 或者 $4$ ，小 $\mathcal H$ 会从这三个数字中随机挑选一个猜测，猜中的概率即为 $\frac{1}{3} \bmod M$ 。  
      
    $\,\,\,\,\,\,\,\,\,\,$对于第二组测试数据，初始时，幸运数的范围为 $[1,5]$ 。  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● $[1,3]$ 区间有一个数字小于等于幸运数，可以将范围缩小至 $[2,3]$ ；  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● $[5,5]$ 区间有一个数字小于等于幸运数，可以唯一确定幸运数为 $3$ 。


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

Tags: 数据结构, 二分, 分治
Difficulty: 1600
# 随机化游戏时间！

## 题目描述

> $\,\,\,\,\,\,\,\,\,$注：本题和 $\sf easy$ 版本的区别在于排列未知，输出全部可能的数字。 

$\,\,\,\,\,\,\,\,\,\,$小 $\mathcal L$ 有一个 $1\sim n$ 的 _排列_ ，她从中选择了一个数字作为自己的幸运数。 

$\,\,\,\,\,\,\,\,\,\,$小 $\mathcal H$ 每次会询问小 $\mathcal L$ 一个区间 $[l,r]$ ，随后小 $\mathcal L$ 会告诉他这个区间里有多少个数**小于等于** 她的幸运数。  


$\,\,\,\,\,\,\,\,\,\,$直到 $m$ 次询问全部完成，直接从小到大输出全部可能的幸运数。保证数据有解。 

  


$\,\,\,\,\,\,\,\,\,\,$长度为 $n$ 的 _排列_ 是由 $1 \sim n$ 这 $n$ 个整数、按任意顺序组成的数组，每个整数恰好出现一次。 

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\le T\le 200\right)$ 代表数据组数，每组测试数据描述如下：
    
      
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入两个整数 $n,m\left( 1\le n,m \le 10^5\right)$ 代表小 $\mathcal L$ 的排列长度和最多询问次数。  
    
    
    $\,\,\,\,\,\,\,\,\,\,$随后 $m$ 行，每行输入三个整数 $l,r,k\left(1\le l \le r \le n;\ 0 \le k \le r - l + 1 \right)$ 代表询问区间、区间内小于等于幸运数的数字个数。
    
      
    
    
    $\,\,\,\,\,\,\,\,\,\,$除此之外，保证所有的 $n$ 之和不超过 $2\times 10^5$ ，所有的 $m$ 之和不超过 $2\times 10^5$ 。
    
    $\,\,\,\,\,\,\,\,\,\,$本题数据**随机生成** ，但保证存在解。  
    

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$对于每一组测试数据，在一行上从小到大输出若干个整数，代表全部符合条件的幸运数。

示例1 

## 输入
    
    
    3
    6 2
    5 6 2
    1 2 0
    6 2
    5 6 1
    1 4 3
    7 4
    3 4 1
    1 3 2
    3 7 1
    4 6 0

## 输出
    
    
    2 3 4
    4
    2

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,$对于第一组测试数据，  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$$[5,6]$ 区间中有两个数字小于等于幸运数，所以幸运数不可能是 $1$ ；  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$$[1,2]$ 区间中没有数字小于等幸运数，所以幸运数不可能是 $5$ 或者 $6$ ；  
    
    
    $\,\,\,\,\,\,\,\,\,$综上，幸运数只有可能是 $2$ 、$3$ 或者 $4$ 。
    
      
    
    
    $\,\,\,\,\,\,\,\,\,$对于第二组测试数据，  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$$[5,6]$ 有一个数字大于幸运数，所以幸运数不可能是 $6$ ；  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$$[1,4]$ 区间中有三个数字小于等于幸运数，联系上一步还有一个数字小于等于幸运数，可以知道幸运数 $\ge 4$ ；  
    $\,\,\,\,\,\,\,\,\,$综上，幸运数只有可能是 $4$ 。  
    


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

Tags: 图论
Difficulty: 2200
# 小红喜欢1

## 题目描述

$\,\,\,\,\,\,\,\,\,$小红拿到了一个长度为 $5$ 的、仅由 $0$ 和 $1$ 组成的数组 $\\{a_1,a_2,a_3,a_4,a_5\\}$ ，其中恰好有一个 $1$ ，其余元素都是 $0$ 。请你直接输出 $1$ 所在的位置。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,$在一行上输入五个整数 $a_1,a_2,a_3,a_4,a_5 \left(0\leq a_i \leq 1 \right)$ ，代表小红拿到的数组。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，代表 $1$ 所在的位置。

示例1 

## 输入
    
    
    0 0 1 0 0

## 输出
    
    
    3


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 模拟
Difficulty: 400
# 小红的树切割

## 题目描述

$\,\,\,\,\,\,\,\,\,$小红定义一棵树是“好树”，当且仅当任意相邻的两个节点的颜色不同（特殊的，一个节点组成的树一定是好树）。  
$\,\,\,\,\,\,\,\,\,$现在小红拿到了一棵树，一些节点被染成红色，其余节点为白色。小红希望切割若干条边形成森林，使得森林的每棵树都是“好树”。小红想知道，最少需要切割多少条边？

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,$第一行输入一个整数 $n \left( 2\leq n \leq 10^5 \right)$ 代表树的节点数量。  
    $\,\,\,\,\,\,\,\,\,$第二行输入一个长度为 $n$ 、且仅由 $\tt R$ 和 $\tt W$ 组成的字符串 $s$ ，第 $i$ 个字符代表第 $i$ 个节点的颜色，其中 $\tt R$ 代表红色、$\tt W$ 代表白色。。  
    $\,\,\,\,\,\,\,\,\,$此后 $n-1$ 行，第 $i$ 行输入两个整数 $u_i$ 和 $v_i\ (1 \leq u_i, v_i \leq n;\ u_i \neq v_i)$ 表示树上第 $i$ 条边连接节点 $u_i$ 和 $v_i$ 。保证树联通，没有重边。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，代表最少需要切割的边数。

示例1 

## 输入
    
    
    4
    RWWR
    1 2
    2 3
    3 4

## 输出
    
    
    1

## 说明
    
    
    将第二条边切割即可。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 思维
Difficulty: 500
# 小红的双好数（easy）

## 题目描述

$\,\,\,\,\,\,\,\,\,$注：本题和 $\sf hard$ 版本仅背景相同，实际所求并不同，请认真读题！  
  
$\,\,\,\,\,\,\,\,\,$小红定义 $n$ 是 $k$ - 好数，当且仅当 $n$ 在 $k$ 进制表示下，每一位都不大于 $1$ 。例如，$30$ 是 3-好数，因为 $30$ 在三进制表示下是 $(1010)_3$ 。  
$\,\,\,\,\,\,\,\,\,$现在输入了一个正整数 $n$ ，小红希望你找到两个不同的正整数 $k_1$ 和 $k_2 \left( 2\leq k_1 < k_2 \leq 10^{18}\right)$ ，满足 $n$ 既是 $k_1$ -好数，也是 $k_2$ -好数，你能帮帮她吗？

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,$在一行上输入一个整数 $n \left( 1 \le n \le 10^{18}\right)$ 代表待求解的数字。  
    

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,$如果在 $[2,10^{18}]$ 范围内无解，直接在一行上输出 $\rm NO$ ；否则，先在第一行上输出 $\rm YES$ ，随后，在第二行上输出两个正整数 $k_1,k_2 \left( 2\leq k_1 < k_2 \leq 10^{18}\right)$ ，代表一组合法解。
    
    $\,\,\,\,\,\,\,\,\,$如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。  
    

示例1 

## 输入
    
    
    5

## 输出
    
    
    YES
    2 4

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,$$5$ 的二进制是 $(101)_2$ ，四进制是 $(11)_4$ ，都符合要求。

示例2 

## 输入
    
    
    2

## 输出
    
    
    NO

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,$$2$ 只有在二进制时是 $(10)_2$ ，其余任意进制都是 $(2)_x$ ，不符合要求。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

Tags: 进制转换, 数学, 枚举, 位运算, 数论
Difficulty: 700
# 小红的线段

## 题目描述

$\,\,\,\,\,\,\,\,\,$在平面直角坐标系中有 $2\times n$ 个点和一条直线 $y = kx + b$。 

$\,\,\,\,\,\,\,\,\,$小红准备在这 $2\times n$ 个点中连 $n$ 条线段（每个点只能连接一次），她希望 **和直线有交点的线段** 的数量尽可能多。 

$\,\,\,\,\,\,\,\,\,$请你给出一个连接方案。 

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,$第一行输入三个整数 $n, k, b(1 \leq n \leq 10^3; -10^5 \leq k, b \leq 10^5)$，表示有 $2\times n$ 个点和直线 $y = kx + b$。  
      
    $\,\,\,\,\,\,\,\,\,$接下来 $2\times n$ 行，每行两个整数 $x, y(-10^5 \leq x, y \leq 10^5)$，表示一个点的坐标。保证没有两个点的坐标相同。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,$先输出一个整数 $m$，表示有 $m$ 条线段和直线有交点。  
    $\,\,\,\,\,\,\,\,\,$接下来$n$行，第$i$行输出两个正整数 $u_i,v_i(1 \leq u_i, v_i \leq 2 \times n; u_i \neq v_i)$ 和一个字符 $\tt Y$ 或者 $\tt N$，代表连接第$u_i$个点和第$v_i$个点，以及是否和直线有交点。  
    $\,\,\,\,\,\,\,\,\,$如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

示例1 

## 输入
    
    
    2 -1 2
    0 0
    0 1
    1 0
    1 1

## 输出
    
    
    1
    1 2 N
    3 4 Y

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,$连接第一个点和第二个点，和直线没有交点。连接第三个点和第四个点，和直线有交点。
    
      
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

Tags: 数学, 数据结构, STL, 贪心, 思维
Difficulty: 1100
# 小红的双好数（hard）

## 题目描述

$\,\,\,\,\,\,\,\,\,$注：本题和 $\sf easy$ 版本仅背景相同，实际所求并不同，请认真读题！  


  


$\,\,\,\,\,\,\,\,\,$小红定义 $n$ 是 $k$ \- 好数，当且仅当 $n$ 在 $k$ 进制表示下，每一位都不大于 $1$ 。例如，$30$ 是 3-好数，因为 $30$ 在三进制表示下是 $(1010)_3$ 。

$\,\,\,\,\,\,\,\,\,$现在输入两个正整数 $k_1$ 和 $k_2$ ，小红希望你找到一个正整数 $n \left(2\leq n \leq 10^{18} \right)$ 满足 $n$ 既是 $k_1$ -好数，也是 $k_2$ -好数，你能帮帮她吗？

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,$在一行上输入两个整数$k_1,k_2 \left( 2\leq k_1<k_2 \leq 10^{18} \right)$ 代表小红给定的初始数字。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,$如果在 $[2,10^{18}]$ 范围内无解，直接在一行上输出 $\rm NO$ ；否则，先在第一行上输出 $\rm YES$ ，随后，在第二行上输出一个正整数 $n \left( 2 \le n \le 10^{18}\right)$ ，代表一个合法解。
    
    $\,\,\,\,\,\,\,\,\,$如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。  
    

示例1 

## 输入
    
    
    4 8

## 输出
    
    
    YES
    65

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,$注意，本题答案不唯一，$64$ 也是一个可行解。

示例2 

## 输入
    
    
    3 5

## 输出
    
    
    YES
    30

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,$$30$ 在三进制表示为 $(1010)_3$ ，在五进制表示为 $(110)_5$ ，均为好数。

示例3 

## 输入
    
    
    998244353 1000000007

## 输出
    
    
    NO


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

Tags: 状压枚举, 枚举, 数论, 暴力
Difficulty: 1800
# 小红的数组操作

## 题目描述

$\,\,\,\,\,\,\,\,\,$小红拿到了$n$个数组，她有以下两种操作：  
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$输入$1\ i\ j\ x$ 将第$i$个数组的第$j$个元素修改为$x$；  
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$输入$2\ i$ 查询前$i$个数组的最小值。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,$第一行输入一个正整数$n(1 \leq n \leq 10^5)$，代表数组的个数。  
    $\,\,\,\,\,\,\,\,\,$接下来 $n$ 行，每行先输入一个正整数$m_i(1 \leq m_i \leq 10^5)$，代表数组的长度，接下来输入$m_i$个整数$a_{ij}(1 \leq a_{ij} \leq 10^9)$，表示数组的元素。  
    $\,\,\,\,\,\,\,\,\,$接下来输入一个正整数$q(1 \leq q \leq 10^5)$，代表操作的次数。  
    $\,\,\,\,\,\,\,\,\,$接下来 $q$ 行，每行先输入一个正整数$t(1 \leq t \leq 2)$，表示操作的类型。  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$如果$t=1$，则接下来输入三个正整数$i,j,x(1 \leq i \leq n; 1 \leq j \leq m_i; 1 \leq x \leq 10^9)$，表示将第$i$个数组的第$j$个元素修改为$x$；  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$如果$t=2$，则接下来输入一个正整数$i(1 \leq i \leq n)$，表示查询前$i$个数组的最小值。  
    $\,\,\,\,\,\,\,\,\,$保证至少有一个查询操作，且 $\sum_{i=1}^{n}m_i \leq 10^5$。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,$对于每个查询操作，输出一个整数，表示查询的结果。

示例1 

## 输入
    
    
    4
    3 1 2 3
    3 4 5 6
    4 7 8 9 10
    2 1 2
    5
    2 2
    1 1 1 10
    2 3
    1 1 2 11
    2 2

## 输出
    
    
    1
    2
    3


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 数据结构, 平衡树, 树套树, 线段树
Difficulty: 1300
# 小红的双排列构造

## 题目描述

$\,\,\,\,\,\,\,\,\,$小红希望你构造一个长度为 $2\times n$ 的 _双排列_ ，满足：恰好有 $k$ 个长度为 $n$ 的区间为 _排列_ 。你能帮帮她吗？  
  
$\,\,\,\,\,\,\,\,\,$长度为 $n$ 的 _排列_ 是由 $1$ 到 $n$ 中的 $n$ 个不同整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是一个排列（数组中的 $2$ 出现了两次），$[1,3,4]$ 也不是一个排列（长度为 $3$ 但数组中有 $4$）。  


$\,\,\,\,\,\,\,\,\,$定义 _双排列_ 为两个长度为 $n$ 的排列打乱顺序后得到的数组，或者说是由 $1$ 到 $n$ 中的 $n$ 个不同整数、按任意顺序组成的数组，其中每个整数恰好出现两次。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,$在一行上输入两个整数$n,k \left( 1\leq n \leq 10^5;\ 0\leq k \leq n+1 \right)$ 代表要求构造的双排列长度及限制。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,$如果无法构造出符合要求的双排列，直接在一行上输出 $-1$ ；否则，在一行上输出 $2\times n$ 个整数，代表构造的双排列。
    
    $\,\,\,\,\,\,\,\,\,$如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。  
    

示例1 

## 输入
    
    
    3 4

## 输出
    
    
    1 2 3 1 2 3

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,$以下区间为排列：$[1,3]$ 、$[2,4]$ 、$[3,5]$ 和 $[4,6]$ 。

示例2 

## 输入
    
    
    4 1

## 输出
    
    
    3 4 3 1 2 2 4 1

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,$以下区间为排列：$[2,5]$ 。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

Tags: 构造, 模拟
Difficulty: 1500
# 面包店故事

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$小镇上有一家面包店，面包以 $x$ 元的价格出售，加 $y$ 元可以多加几块培根。小歪带着 $n$ 元来到了面包店，他想知道自己能不能买到加培根的面包？

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输入三个整数 $x,y,n\left( 1 \le x,y,n\le 100\right)$ 代表面包的价格、培根的价格和小歪带的钱。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$如果小歪能加到培根，在一行上输出 $\sf YES$ ；否则，直接输出 $\sf NO$ 。

示例1 

## 输入
    
    
    3 1 5

## 输出
    
    
    YES

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$面包加培根一共 $4$ 元，小歪带了 $5$ 元，他可以吃到培根！

示例2 

## 输入
    
    
    10 1 10

## 输出
    
    
    NO

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$面包加培根一共 $11$ 元，小歪带了 $10$ 元，他吃不到培根 $\sf (⋟﹏⋞)$ 。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 数学
Difficulty: 400
# 放课后故事

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$小 $\mathcal S$ 想要举办一个纸飞机大赛，他最新研制出的纸飞机需要 $k$ 张纸才能折成。  
$\,\,\,\,\,\,\,\,\,\,$为了制作纸飞机，他向班里的 $n$ 个人要了一些纸，第 $i$ 个人提供了 $a_i$ 张纸给小 $\mathcal S$ 研究纸飞机。  
$\,\,\,\,\,\,\,\,\,\,$放学了，小 $\mathcal S$ 终于折好了全部的纸飞机，现在有 $m$ 个人留下来和小 $\mathcal S$ **一起** 飞纸飞机。  
$\,\,\,\,\,\,\,\,\,\,$最多有多少个人能分到纸飞机。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入三个整数 $n,m,k\left(1\le n \le 10^5;\ 0\le m \le 10^5;\ 1\le k\le 10^9 \right)$ 代表班级同学数量、留下来的同学数量和叠一只纸飞机需要的纸的数量。  
    $\,\,\,\,\,\,\,\,\,\,$第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n \left( 1 \le a_i \le 10^9 \right)$ 代表每一个同学提供的纸的数量。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，代表最多有多少个人能分到纸飞机。

示例1 

## 输入
    
    
    3 2 5
    1 2 4

## 输出
    
    
    1

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$小 $\mathcal S$ 一共收集到 $7$ 张纸，只可以叠一架纸飞机。

示例2 

## 输入
    
    
    6 3 4
    1 1 4 5 1 4

## 输出
    
    
    4

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$小 $\mathcal S$ 一共收集到 $16$ 张纸，可以叠 $4$ 架纸飞机，每个人都能分到纸飞机。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 数学
Difficulty: 400
# 异或故事

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$给定 $t$ 组询问，$\mathit {76}$ 每次询问都会给出一个正整数 $a$ ，你需要在区间 $[1,10^9]$ 中找到两个正整数 $b$ 和 $c$ ，使得 $b \oplus c = a$ 。  
$\,\,\,\,\,\,\,\,\,\,$$\oplus$ 代表按位异或。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\ (1\le T\le 10^5)$ 代表数据组数，每组测试数据描述如下：  
    $\,\,\,\,\,\,\,\,\,\,$在一行上输入一个整数 $a\ (\ 1 \leq a \leq 10^9\ )$ 代表$\mathit {76}$ 给出的初始数字。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$对于每一组测试数据，在一行上输出两个正整数，代表你找到的两个值。
    
    $\,\,\,\,\,\,\,\,\,\,$如果存在多个解决方案，您可以输出任意一个。  
    

示例1 

## 输入
    
    
    3
    1
    5
    4

## 输出
    
    
    2 3
    3 6
    74 78

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$对于第一组测试数据，$(10)_2 \operatorname{xor} (11)_2=(01)_2$ ；
    
    $\,\,\,\,\,\,\,\,\,\,$对于第二组测试数据，$(011)_2 \operatorname{xor} (110)_2=(101)_2$ 。  
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

Tags: 构造, 枚举, 位运算, 思维
Difficulty: 800
# 构造故事

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$小 $\mathcal S$ 今天在数学课上学习了三角形，他回家立马拿出了自己的 $n$ 根火柴，想知道从这 $n$ 根火柴中任选 $3$ 根，能否组成一个周长最大的三角形。  
$\,\,\,\,\,\,\,\,\,\,$由于小 $\mathcal S$ 只会暴力枚举，所以他把这个问题交给了你，你能帮他解决这个问题吗？

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\le T\le 20\right)$ 代表数据组数，每组测试数据描述如下：  
    $\,\,\,\,\,\,\,\,\,\,$第一行输入一个整数 $n\left( 3\le n\le 10^4\right)$ 代表小 $\mathcal S$ 的火柴数量。  
    $\,\,\,\,\,\,\,\,\,\,$第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n \left( 1\le a_i \le 10^9\right)$ 代表每根火柴的长度。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$对于每一组测试数据，在一行上输出一个整数，代表能组成周长最大三角形的周长；如果无论如何都无法组成三角形，直接输出 $-1$ 。

示例1 

## 输入
    
    
    3
    6
    2 2 10 4 10 6
    5
    6 1 5 3 3
    5
    2 2 4 10 6

## 输出
    
    
    26
    14
    -1

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$对于第一组测试数据，有两个合法的三角形 $(4,10,10)$ 和 $(6,10,10)$ 。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 数学, 排序, 思维
Difficulty: 600
# 不是烤串故事

## 题目描述

$\,\,\,\,\,\,\,\,\,$小红有两个长度为 $n$ 的字符串 $s$ 和 $t$ ，我们定义下标从 $1$ 开始，现在你可以选取字符串 $s$ 的前 $i$ 个字符 $s_1 s_2\cdots s_i$，然后将这一部分 _反转_ 后与剩余部分拼接，得到 $s_i'$。 

$\,\,\,\,\,\,\,\,\,$请你找到每一个翻转前缀 $s_i'$ 与字符串 $t$ 的 $\displaystyle \max_{i=1}^n{\rm\\_len} \\{{\rm lcp}(s_i',t) \\}$ ，即长度最长的 ${\rm lcp}(s_i',t)$ 。在这里，$\rm lcp$ 代表 _最长公共前缀_ 。 

$\,\,\,\,\,\,\,\,\,$好吧，这其实并不难，作为神秘的 $\mathcal F$ 题，你同时需要输出满足上述条件的最小的 $i$ 。 

  


$\,\,\,\,\,\,\,\,\,$在本题中， _反转_ 即为将字符串绕中心字符前后反转，具体地说，设字符串为 $s_1s_2\cdots s_{n-1} s_n$ ，反转后得到 $s_n s_{n-1}\cdots s_2s_1$。  


## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\ (1\le T\le 100)$ 代表数据组数，每组测试数据描述如下：  
    $\,\,\,\,\,\,\,\,\,$第一行输入一个整数 $n\left(1\leq n\leq 10^6\right)$ 代表字符串长度。  
    $\,\,\,\,\,\,\,\,\,$第二行输入一个长度为 $n$ ，且仅由小写字母构成的字符串 $s$。  
    $\,\,\,\,\,\,\,\,\,$第三行输入一个长度为 $n$ ，且仅由小写字母构成的字符串 $t$。  
      
    $\,\,\,\,\,\,\,\,\,$除此之外，保证所有的 $n$ 之和不超过 $10^6$ 。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,$对于每一组测试数据，在一行上输出两个整数，代表最长 $\rm lcp$ 长度和在此条件下最小的 $i$ 。

示例1 

## 输入
    
    
    3
    6
    baabaa
    aabbbb
    3
    abc
    bac
    2
    ab
    cd

## 输出
    
    
    4 3
    3 2
    0 1

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,$对于第一组测试数据，我们这样描述整个过程：  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$选择前缀长度为 $1$ 翻转 $s_1'={\tt"baabaa"}$ ，$\operatorname{lcp}=0$ ；  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$选择前缀长度为 $2$ 翻转 $s_2'={\tt "ababaa"}$ ，$\operatorname{lcp}=1$ ；  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$选择前缀长度为 $3$ 翻转 $s_3'={\tt"aabbaa"}$ ，$\operatorname{lcp}=4$ ；  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$选择前缀长度为 $4$ 翻转 $s_4'= {\tt "baabaa"}$ ，$\operatorname{lcp}=0$ ；  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$选择前缀长度为 $5$ 翻转 $s_5'={\tt"abaaba"}$ ，$\operatorname{lcp}=1$ ；  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$选择前缀长度为 $6$ 翻转 $s_6'={\tt"aabaab"}$ ，$\operatorname{lcp}=3$ ；  
    $\,\,\,\,\,\,\,\,\,$所以最长的公共前缀为 $4$ ，与此同时最小的翻转下标为 $3$ 。


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

Tags: kmp与扩展kmp, 字符串, 后缀数组(SA), 字符串hash, 二分, 分治
Difficulty: 1900
# 小红的字符串

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$小红拿到了一个长度为 $3$ 且仅由小写字母组成的字符串，她每次操作可以修改任意一个字符，小红希望最终所有字符都相同。 

$\,\,\,\,\,\,\,\,\,\,$你能帮小红求出最小的操作次数吗？ 

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入一个长度为 $3$ 且仅由小写字母组成的字符串 $s$。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，表示最小的操作次数。

示例1 

## 输入
    
    
    aba

## 输出
    
    
    1

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$操作 $1$ 次，将第二个字符修改为 '$\tt a$' 即可。

示例2 

## 输入
    
    
    uuu

## 输出
    
    
    0


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

Tags: 模拟
Difficulty: 400
# 小红的序列乘积

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$小红有一个长度为 $n$ 的整数序列 $\\{a_1,a_2,\dots,a_n\\}$，定义 $f_i = a_1 \times a_2 \times \cdots \times a_i$ ，即前 $i$ 项的乘积。现在小红想知道 $f_1, f_2, \dots, f_n$ 中，有多少个数的个位数是 $6$ 。 

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入一个整数 $n \left(1 \leq n \leq 10^5\right)$ 代表序列中元素的数量。  
    $\,\,\,\,\,\,\,\,\,\,$第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n \left(1 \leq a_i \leq 10^9\right)$ 代表序列元素。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，代表 $f_1, f_2, \cdots, f_n$ 中，个位数是 $6$ 的数的个数。

示例1 

## 输入
    
    
    5
    1 2 3 4 4

## 输出
    
    
    2

## 说明
    
    
    $f = [1, 2, 6, 24, 96]$，有 2 个数的个位数是 6。

示例2 

## 输入
    
    
    6
    1 1 4 5 1 4

## 输出
    
    
    0


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 数学
Difficulty: 400
# 小红的数组重排

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$给出一个数字 $n$ 和一个长度为 $n$ 的数组 $[a_1,a_2,\dots,a_n]$ 。现在你可以以任意方式重新排列数组 $a$，问是否存在重排后的数组 $a$ 满足：$a_1 \times a_2 < a_2 \times a_3 < \cdots < a_{n-1} \times a_n$。 

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入一个整数 $n\left( 3 \leq n \leq 5 \times 10^5\right)$ 代表数组中的元素数量。  
    $\,\,\,\,\,\,\,\,\,\,$第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n\left(0 \leq a_i \leq 10^9 \right)$ 代表数组元素。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$若存在符合题意的排列后的数组 $a$，在一行上输出 $\rm YES$ ，随后在第二行上输出这个数组；否则，直接输出 $\rm NO$ 。
    
    $\,\,\,\,\,\,\,\,\,\,$如果存在多个解决方案，您可以输出任意一个。  
    

示例1 

## 输入
    
    
    4
    7 2 5 1

## 输出
    
    
    YES
    1 5 2 7

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$重排后满足： $1 \times 5 < 5 \times 2 < 2 \times 7$ 。

示例2 

## 输入
    
    
    6
    1 1 4 5 1 4

## 输出
    
    
    NO


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

Tags: 数学, 排序, 贪心
Difficulty: 600