#2040. 中奖率

中奖率

中奖率

题目描述

标题: 中奖率 - Problem - QOJ.ac

#4917. 中奖率

Statistics

The problem was used in the following contests:

小 T 在玩一款游戏,游戏中有彩票。彩票只有中奖与不中奖两种情况。

小 T 玩了一段时间后发现,如果将中奖看作 1,不中奖看作 0 的话,那么一直买彩票后生成的无限长的 01 序列 T 有一个长为 n 的循环节 S。具体来讲,T 满足 Ti=S((i−1)modn)+1。

定义 fi 为只考虑前 i 次买彩票时的中奖率,更具体地,若前 i 个数中有 ci 个1,那么 fi=cii。小T想知道中奖率何时比较高,于是他会有 q 次询问,具体形式如下:

  1. 给定整数 k,设 fw 为序列 f 中第 k 大的值,求 w 。
  2. 给定整数 k,求出 fk 的排名,若排名不存在,输出 inf。

注意:我们称 fa 比 fb 大当且仅当 fa>fb 或 fa=fb∧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 项为 11,12,13,12,25,13,37,38,13,25,411,13,513,可以发现后面的项不会对这几个询问的答案产生影响。

样例二

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≤n≤2×105,1≤k≤1010000,1≤q≤20,op∈{1,2},保证 S 为 01 序列。

子任务编号 n≤ k≤ 特殊性质 分值 1 105 1010000 S1=S2=⋯=Sn−1=0,Sn=1 1 2 10 1000 - 9 3 105 109 9 4 1010000 op=2 13 5 S1=1,S2=S3=⋯=Sn=0 20 6 200 - 18 7 105 30

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 6
100
1 1
2 3
1 2
1 3
2 7
2 8
1
inf
2
4
4
8

样例 2

10 7
1011001000
1 41
1 33
1 4348
1 1235467890
2 19260817
2 729384264
2 274892563
12
19
4968
1058972476
11235477
364692134
240530993