书的边界 - 题目

正在使用等宽字体和一种简单的贪心算法对一本书进行排版。书的内容仅仅是一个单词序列，其中每个单词包含一个或多个字符。

在排版之前，我们选择一个最大行长，并用 $m$ 表示该值。每一行最多可以包含 $m$ 个字符，包括单词之间的空格。排版算法只是简单地逐个处理单词，并在同一行的两个连续单词之间恰好打印一个空格。如果将单词打印在当前行会超过最大行长 $m$，则会另起一行。

最大行长分别为 13 和 14 时的示例输入文本排版效果

给定一段需要排版的文本，你正在尝试不同的最大行长 $m$。对于固定的 $m$，首句是由从上到下每一行的第一个单词组成的句子（由单个空格分隔的单词序列）。在上面的例子中，当示例文本以最大行长 14 排版时，首句是 “its to you n”。

给定一段文本和两个整数 $a$ 和 $b$，求最大行长在 $a$ 到 $b$（包含 $a$ 和 $b$）之间时，每一个候选最大行长对应的首句长度。句子的长度是它包含的字符总数，包括空格。

第一行包含需要排版的文本——一个由单个空格分隔的单词序列。每个单词都是由一个或多个小写英文字母组成的字符串。

第二行包含两个整数 $a$ 和 $b$——我们感兴趣的区间的边界，如上所述。

保证 $1 \le w \le a \le b \le z \le 500\,000$，其中 $w$ 是文本中最长单词的长度，$z$ 是文本的总字符数（包括空格）。

输出 $b - a + 1$ 行——第 $k$ 行应包含一个整数，即当最大行长等于 $a - 1 + k$ 时的首句总长度。

its a long way to the top if you wanna rock n roll
13 16

QOJ.ac