小 T 在玩一款游戏,游戏中有彩票。彩票只有中奖与不中奖两种情况。
小 T 玩了一段时间后发现,如果将中奖看作 1,不中奖看作 0 的话,那么一直买彩票后生成的无限长的 01 序列 $T$ 有一个长为 $n$ 的循环节 $S$。具体来讲,$T$ 满足 $T_i=S_{((i-1)\bmod n)+1}$。
定义 $f_i$ 为只考虑前 $i$ 次买彩票时的中奖率,更具体地,若前 $i$ 个数中有 $c_i$ 个1,那么 $f_i=\frac{c_i}{i}$。小T想知道中奖率何时比较高,于是他会有 $q$ 次询问,具体形式如下:
- 给定整数 $k$,设 $f_w$ 为序列 $f$ 中第 $k$ 大的值,求 $w$ 。
- 给定整数 $k$,求出 $f_k$ 的排名,若排名不存在,输出
inf
。
注意:我们称 $f_a$ 比 $f_b$ 大当且仅当 $f_a>f_b$ 或 $f_a=f_b \wedge a < b$ 。可以证明在这样的定义下,序列 $f$ 中第 $k$ 大的值是存在且唯一的。
输入格式
第一行两个整数 $n,q$,表示循环节长度与询问次数。
第二行一个 01 序列 $S$,表示循环节。
接下来 $q$ 行,每行两个整数 $op,k$,分别表示询问类型和询问参数。$op=1$ 表示第一种询问,即查询第 $k$ 大所在位置,$op=2$ 表示第二种询问,即查询排名。
输出格式
共 $q$ 行,每行一个整数表示答案。
样例一
input
3 6 100 1 1 2 3 1 2 1 3 2 7 2 8
output
1 inf 2 4 4 8
explanation
01序列 $T$ 为 100100100100100100...
序列 $f$ 的前 $13$ 项为 $\frac{1}{1},\frac{1}{2},\frac{1}{3},\frac{1}{2},\frac{2}{5},\frac{1}{3},\frac{3}{7},\frac{3}{8},\frac{1}{3},\frac{2}{5},\frac{4}{11},\frac{1}{3},\frac{5}{13}$,可以发现后面的项不会对这几个询问的答案产生影响。
样例二
input
10 7 1011001000 1 41 1 33 1 4348 1 1235467890 2 19260817 2 729384264 2 274892563
output
12 19 4968 1058972476 11235477 364692134 240530993
数据范围
对于所有测试数据, $1\leq n\leq 2\times 10^5,1 \leq k \leq 10^{10000},1\leq q\leq 20,op\in \{1,2\}$,保证 $S$ 为 01 序列。
子任务编号 | $n\le$ | $k\le$ | 特殊性质 | 分值 |
---|---|---|---|---|
$1$ | $10^5$ | $10^{10000}$ | $S_1=S_2=\dots=S_{n-1}=0,S_n=1$ | $1$ |
$2$ | $10$ | $1000$ | - | $9$ |
$3$ | $10^5$ | $10^9$ | $9 $ | |
$4$ | $10^{10000}$ | $op=2$ | $13$ | |
$5$ | $S_1=1,S_2=S_3=\dots=S_n=0$ | $20$ | ||
$6$ | $200$ | - | $18$ | |
$7$ | $10^5$ | $30$ |