QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100

# 4917. 中奖率

统计

小 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$ 次询问,具体形式如下:

  1. 给定整数 $k$,设 $f_w$ 为序列 $f$ 中第 $k$ 大的值,求 $w$ 。
  2. 给定整数 $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$