题目分析

我们有一个无限长的01序列$T$，它由长度为$n$的循环节$S$重复构成。定义$f_i = \frac{c_i}{i}$，其中$c_i$是前$i$个位置中1的个数。

我们需要处理两种查询：

1. 找到序列$f$中第$k$大的值所在的位置$w$
2. 查询$f_k$在序列$f$中的排名（如果不存在则输出inf)

比较规则：$f_a > f_b$ 或 ($f_a = f_b$ 且 $a < b$)

关键观察

1. 分数表示与比较

对于位置$i$，有：

$$f_i = \frac{c_i}{i} = \frac{\lfloor \frac{i-1}{n} \rfloor \cdot c_n + c_{((i-1) \bmod n) + 1}}{i} $$

定义$r_i = c_i \cdot n - i \cdot c_n$，则比较$f_a$和$f_b$的大小等价于比较：

$$\frac{c_a}{a} \leq \frac{c_b}{b} \iff c_a \cdot b \leq c_b \cdot a \iff r_a \cdot b \leq r_b \cdot a $$

2. 特殊性质

代码中的flag变量标记了特殊情况：当所有$r_i \leq 0$时，即$c_n = 0$或序列具有特殊结构时，可以采用简化的计算方法。

算法思路

高精度处理

由于$k$可能达到$10^{10000}$，需要实现高精度整数类Int：

• 采用基数为$10^{18}$的表示法
• 支持加、乘、除、取模等运算

查询类型1：找第k大的位置

特殊情况处理 (flag = true)

当所有$r_i \leq 0$时：

1. 统计$r_i = 0$的位置数量$cnt$
2. 将大数$k$分解为：$k = q \cdot cnt + r$
3. 答案位置为$q \cdot n + \text{第}r\text{个满足}r_i=0\text{的位置}$

一般情况处理

1. 统计所有$r_i > 0$的位置的$r_i$之和$sum$
2. 将$k$分解为：$k = q \cdot sum + r$
3. 使用二分法找到满足条件的分数边界
4. 在候选位置中找到第$r$个位置

查询类型2：查询排名

特殊情况处理 (flag = true)

当$r_k \leq 0$时直接返回inf，否则：

1. 统计$r_i \geq 0$的位置数量$cnt$
2. 计算位置$k$在循环节中的排名
3. 结合循环次数计算总排名

一般情况处理

1. 如果$r_k \leq 0$，返回inf
2. 将位置$k$分解为在循环节中的信息
3. 统计所有比$f_k$大的分数个数
4. 使用数学公式计算总排名

复杂度分析

• 预处理：$O(n)$计算前缀和和$r_i$数组
• 每次查询：
  • 高精度运算：与数字位数相关
  • 二分查找：$O(\log(n^3)) = O(\log n)$
  • 候选位置排序：最坏$O(n \log n)$
• 总体：由于$q \leq 20$，算法可以接受

代码实现要点

1. 高精度类Int：使用vector<ll>以$10^{18}$为基数存储大整数
2. 分数比较：通过交叉相乘避免浮点数精度问题
3. 循环节处理：利用模运算将无限序列问题转化为有限问题
4. 边界情况：特别注意$r_i = 0$和$r_i < 0$的情况

样例验证

对于样例1：

• 序列100，$n=3$，$c_n=1$
• $r_1 = 1\times3 - 1\times1 = 2$
• $r_2 = 1\times3 - 2\times1 = 1$
• $r_3 = 1\times3 - 3\times1 = 0$

查询结果与题目输出一致。

该算法通过数学分析和高效的高精度运算，成功解决了大规模数据下的排名查询问题。