小编Ank*_*thD的帖子

我正在使用像C++这样的C++阅读它

#define max(a,b) (a > b ? a : b)

可以导致"双重评估".有人能给我一个例子,说明何时进行双重评估以及为什么它会变坏？

PS:令人惊讶的是,除了在Clojure中的一个例子(我无法理解)之外,我在google搜索时找不到任何详细的解释.

这是2017年Google APAC提出的问题.问题D:总和

爱丽丝给她的朋友鲍勃提供了一个N正整数数组,索引从1到N.她向Bob提出了许多疑问,其形式是"这两个索引之间的数字总和是多少？" 但鲍勃能够轻松解决问题.爱丽丝拿走了她的阵列,发现了所有N*(N + 1)/ 2个非空子阵列.她找到了每个子数组的总和,然后对这些值进行排序(以非递减顺序)以创建一个新数组,索引范围为1到N*(N + 1)/ 2.例如,对于初始数组[2,3,2],Alice将生成子数组[2],[3],[2],[2,3],[3,2]和[2,3], 2](注意,[2,2],例如,不是一个子阵列).然后她拿出总和 - 2,3,2,5,5,7 - 然后对它们进行排序以获得[2,2,3,5,5,7]的新数组.Alice给出了初始值数组到Bob,以及形式为"新数组中索引Li到Ri的数字总和是多少？"的Q查询？现在鲍勃有麻烦了!你能救他吗？

即使在大数据集的c ++中,直接解决方案也效率太低.有没有更有效的方法来解决这个问题？

目前我正在通过这个for循环来构造最终数组:

    multiset<int> sums;
    long long int temp = 0;
    for (long long int len = 1; len <= n; ++len)
    {
        for (int start = 0; start+len <= n; ++start)
        {
            temp = 0;
            for (int i = 0; i < len; ++i)
            {
                temp += arr[start + i]; //arr stores the original array of n digits
            }
            sums.insert(temp);
        }
    }

PS:我目前的实施是O(n …