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

編集：あなたの実装も正しいようです、私はちょうど別のものを持っています。そして、私たちは両方とも問題の記述を読み違えました。

queryparamsを使って関数を呼び出すと思います

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

あなたのnが2の捕虜でないとき、そのような方法でセグメントツリーを扱うのは間違っていると私は信じています
。

  1. tree配列を131072要素（2 ^ 17）およびA65536（2 ^ 16）に拡大します。
  2. そのような最小のものkは2より小さくなくn、2の捕虜であることがわかりました。
  3. 要素をn（0ベース）からk-1-20000で初期化します。
  4. n等しくするk;
  5. 必ず電話してくださいinit(1,0,n-1);

それがあなたがWAを打ち負かすのに役立つことを願っています。

于 2012-08-10T09:51:28.880 に答える