#P4701. 采样

采样

题目背景

“看着我的眼睛。”——优祖列罕

题目描述

VOID 抽取的每个基因是由大写英文字母组成的环状字符串。第 ii 个环状基因的长度为 lil_i。从第 xx 个位置顺着环读完一圈,可以得到最初编号为 xx 的链状基因。链状基因的内容可以相同,但它们的编号各不相同。例如,环状基因 ABCAB 的 55 个链状基因依次为 ABCAB、BCABA、CABAB、ABABC、BABCA。

第 ii 个环状基因还有两个参数 pi,tip_i,t_i。先给各个编号 xx 设定权重

$$f_i(x)=x-\frac{p_i+t_i+l_i}{2}\ln(x^2+1) +(p_i l_i+p_i t_i-1)(\arctan x+1).$$

这里 ln⁡\ln 是自然对数,arctan⁡\arctan 的结果以弧度计。只要有两个编号 x,yx,y 满足 fi(x)<fi(y)f_i(x)<f_i(y),且当前编号 xx 的链状基因字典序小于当前编号 yy 的链状基因,就可以交换这两个链状基因的编号。权重始终与编号绑定。持续交换,直到没有符合条件的编号对。最终采样与合法交换的顺序无关。

取最后编号为 pip_i 的链状基因作为第 ii 个环状基因的采样 gig_i。若 a≠ba\ne b,且 gag_a 是 gbg_b 的前缀,则称第 aa 个环状基因是第 bb 个环状基因的亲和体。两个完全相同的采样也满足前缀条件。求每个环状基因拥有的亲和体数量。

输入格式

第一行包含一个整数 nn,表示环状基因的数量。

接下来 nn 行,每行包含一个由大写英文字母组成的非空字符串,以及两个整数 pi,tip_i,t_i。该字符串的长度为 lil_i,且 1≤pi≤li1\le p_i\le l_i,1≤ti≤1041\le t_i\le10^4。

输出格式

输出 nn 行,每行一个整数。第 ii 行表示第 ii 个环状基因的亲和体数量。

4
CDEAB 3 2
ABC 2 4
D 1 6
EDEE 2 6
1
0
0
1

样例解释

第 11 个环状基因各编号的初始链状基因与权重如下。

编号 xx 初始链状基因 f1(x)f_1(x) 的近似值
1 CDEAB 33.24222736533.242227365
2 DEABC 36.09578479436.095784794
3 EABCD 36.46798998336.467989983
4 ABCDE 36.35028655336.350286553
5 BCDEA 36.17753264936.177532649

依次交换编号 (1,3)(1,3)、(3,5)(3,5)、(3,4)(3,4),编号 33 最终对应 ABCDE。四个采样依次是 ABCDE、ABC、D、DEEE,所以第 22 个基因是第 11 个的亲和体,第 33 个基因是第 44 个的亲和体。