题目背景
A 教练负责一所学校的竞赛训练。学生按照到场顺序进入机房,A 教练为每名学生记录了一个能力值区间。
为了便于统一安排训练,A 教练希望把已经到场的学生分成若干个连续小组。如果分组到最后剩下不足一个正式训练组的学生,他们仍要参加训练,但需要由教练单独指导。学生们一个接一个到场,每来一名学生,A 教练都需要重新评估当前在场学生的分组方案。不过,每次重新评估都很费时。A 教练想到了擅长解决 CSP-S 题的你,希望你编写一个程序,自动完成这项工作。
题目描述
给定四个整数 n,k,B,\mathit{type},其中 n,k 为正整数,n 为学生总数,k 为正式训练组的人数下限,B 为非负整数,表示教练辅导组额外增加的管理难度,\mathit{type}\in{0,1} 表示输入数据的生成方式。学生按到场顺序编号为 1,2,\ldots,n;每名学生的能力值区间 [L_i,R_i] 按“强制在线”一节中的规则确定。
对于每个 i\ge k,考虑前 i 名学生。将前 i 名学生划分为若干个连续小组的分组方案满足:
G_1=[l_1,r_1],\ G_2=[l_2,r_2],\ \ldots,\ G_m=[l_m,r_m],
其中
j+1=l{j+1}\quad(1\le j<m). $$
也就是说,每名学生恰好属于一个小组,所有小组互不重叠,并且覆盖第 1 名至第 i 名学生。
除最后一组外,每个小组至少包含 k 名学生。最后一组有两种情况:
- 若最后一组至少包含 k 名学生,则它是正式训练组;
- 若最后一组包含少于 k 名学生,则它是教练辅导组。教练辅导组仍然属于分组方案,但教练需要对其中的学生逐一检查训练进度并答疑,因此该组的管理难度需要额外加上 B。
例如,当 i=10、k=3 时:
- [1,3],[4,7],[8,10] 的人数为 3,4,3,合法;
- [1,4],[5,9],[10,10] 的人数为 4,5,1,合法,最后一组是教练辅导组;
- [1,5],[6,10] 的人数为 5,5,合法;
- [1,3],[4,5],[6,10] 不合法,因为中间一组只有 2 名学生,少于 k。
对于前 i 名学生的分组方案,小组 [l,r] 的管理难度定义为
$$
\operatorname{cost}_i(l,r)
\begin{cases} \displaystyle\max_{l\le t\le r}Rt-\min{l\le t\le r}Lt+(r-l+1)+B, & r=i\ \text{且}\ r-l+1<k,\[8pt] \displaystyle\max{l\le t\le r}Rt-\min{l\le t\le r}L_t+(r-l+1), & \text{其他情况}. \end{cases} $$
其中,第一项 $\max_{l\le t\le r}Rt-\min{l\le t\le r}L_t 是两个极值之差,第二项 r-l+1 是小组人数;如果该小组是最后一组且人数少于 k,还需额外加上 B$。
一个分组方案的难度定义为其中所有小组管理难度的最大值。记前 i 名学生能够达到的最小分组方案难度为 c_i,即
$$
c_i
\min{\mathcal P} \ \max{[l,r]\in\mathcal P} \operatorname{cost}_i(l,r), $$
其中 \mathcal P 遍历前 i 名学生的所有合法分组方案。
题目要求输出最终的最小分组方案难度 c_n,以及用于校验的滚动哈希值。
令 h_0=0。按 i=1,2,\ldots,n 的顺序计算
$$ hi=(10007h{i-1}+c_i)\bmod 2^{64}. $$
其中 c_i 是前文定义的前 i 名学生的最小分组方案难度;当 i
强制在线
本题强制在线。每一步得到第 i 名学生的能力值区间时,都必须使用已经确定的 c_{i-1}。
规定 $c0=0。按 i=1,2,\ldots,n 的顺序读入数据,并使用已经确定的 c{i-1} 解码第 i$ 名学生的能力区间:
当 \mathit{type}=0 时,输入中的两个编码值为 u_i,v_i,并规定
$$ L_i=ui\mathbin{\operatorname{xor}}(c{i-1}+i), \qquad R_i=vi\mathbin{\operatorname{xor}}(c{i-1}+i). $$
其中,c_{i-1}+i 先进行普通整数加法,再与 u_i 或 v_i 进行按位异或。保证解码后始终有 L_i\le R_i。
当 \mathit{type}=1 时,输入给出五个整数 x,y,z,b_1,b_2。令
$$ bt=(x b{t-1}+y b_{t-2}+z)\bmod 2^{30}\quad(t\ge3). $$
对每个 i,令
$$ di=c{i-1}+i, $$
$$ pi=(b{2i-1}\mathbin{\operatorname{xor}}d_i)\bmod 10^9,\qquad qi=(b{2i}\mathbin{\operatorname{xor}}d_i)\bmod 10^9, $$
并规定
L_i=1+\min(p_i,q_i),\qquad R_i=1+\max(p_i,q_i).
当 i