0

我正在尝试使用段树解决 SPOJ 问题GSS1（你能回答这些查询吗）。我正在使用“init”方法来初始化树，并使用“query”方法来获取范围 [i,j] 中的最大值。

限制 |A[i]| <= 15707 和 1<=N（元素数）<=50000。

int A[50500], tree[100500];

void init(int n, int b, int e) // n=1, b=lower, e=end
{
    if(b == e)
    {
        tree[n] = A[b];
        return;
    }
    init(2 * n, b, (b + e) / 2);
    init(2 * n + 1, ((b + e) / 2) + 1, e);

    tree[n] = (tree[2 * n] > tree[2 * n + 1]) ? tree[2 * n] : tree[2 * n + 1];
}

int query(int n, int b, int e, int i, int j) // n=1, b=lower, e=end, [i,j]=range
{
    if(i>e || j<b) 
        return -20000;
    if(b>=i && e<=j)  
        return tree[n];

    int p1 = query(2 * n, b, (b + e) / 2, i, j);
    int p2 = query(2 * n + 1, ((b + e) / 2) + 1, e, i, j);

    return (p1 > p2) ? p1 : p2;
}

程序给出了错误的答案。我调试了大多数情况下的代码（负数、奇数/偶数 N），但我无法弄清楚算法有什么问题。

如果有人能指出我正确的方向，我将不胜感激。

谢谢

4

2 回答 2

1

我担心（接受的）答案在这里错过了一个非常重要的点。问题在于代码本身使用的算法。代码说节点的答案是它的子节点值的最大值。但是最大子数组很可能部分位于两个孩子中。例如

-1 -2 3 4 5 6 -5 -10 (n=8)

代码将输出 11 而答案是 18。

您还需要调查这种情况才能击败 WA。（我之所以回答这个问题，是因为接受的答案并不完全正确，也没有正确回答这个问题。）

于 2016-06-15T13:14:38.143 回答
0

编辑：看来你的实现也是正确的，我只是有另一个。我们都误读了问题陈述。

我猜你query用参数调用你的函数

query( 1, 0, n-1, x-1, y-1 );

我相信当您的 n 不是 2 的 pow 时，以这种方式处理分段树是错误的。
我向您提供

  1. 将数组扩大tree到 131072 个元素（2^17）和A65536 个（2^16）；
  2. 发现最小的k这样不小于n并且是2的pow；
  3. 将元素从n(0-based) 初始化为k-1-20000；
  4. n等于k; _
  5. 确保你打电话init(1,0,n-1);

希望这能帮助您击败 WA。

于 2012-08-10T09:51:28.880 回答