java - 如何降低装桶程序的时间复杂度？

Question

我正在解决以下问题:

连续有n个桶。一位园丁正在给水桶浇水。每天他都会在位置 i 和 j(含)之间的水桶中浇水。他为不同的 i 和 j 做了 t 天。

输出桶中水的体积，假设初始体积为零，每次浇水都会使体积增加 1。

输入:第一行包含 t 和 n，用空格分隔。接下来的 t 行包含用空格分隔的 i 和 j。

输出:一行显示由空格分隔的 n 个桶中的体积。

示例:

输入:

2 2
1 1
1 2

输出:

2 1

约束:

0 <= t <= 10⁴; 1 <= n <= 10⁵

我试过这个问题。但是我使用 O(n*t) 算法。我每次在每一步将桶从 i 增加到 j。但这显示时间限制错误。有没有什么有效的算法可以解决这个问题。一个小提示就足够了。

P.S:我使用了 C++ 和 Java 作为标签，因为程序可以用这两种语言编写。

Answer 1

与其记住每个桶中的水量，不如记住每个桶与前一个桶之间的差异。