0

N 個の数字 (すべて正で、4 桁以下) を持つ配列Aが与えられた場合、 2種類のクエリがサポートされます。合計 M 個のクエリがあります。

  1. インデックスL,R (両方を含む) で指定された範囲をKで更新します。
  2. L,R (両方を含む)で指定された範囲内の最大の要素を返します。

数値をK回更新するということは、数値をK回回転させることを意味します。

たとえば、1234 は 2341 に回転します。

905 は 059 に回転し、059 は 590 に回転します。

注：059と59は別の番号です。59 は 95 に回転します。

指定された配列要素に先行ゼロがありません。

制約:

0 <= AI < 10000

1 <= N <= 800000

1 <= M <= 200000

0 <= K <= 60

ツリーノードが含まれる範囲の回転数を格納するセグメントツリーを考えました。これを遅延伝播で実装しましたが、遅延伝播でもクエリの実装に最悪の場合 O(N) 時間がかかり、TIME LIMIT EXCEEDED につながります。

誰でもより速いアプローチを提案できますか?

配列または構造体の一部のプロパティが不足していますか?

4

1 に答える 1

2

回転数を保存するというあなたの考えは正しいです。より太く（クエリごと
に）機能させる方法は次のとおりです。 1) ノード構造の定義:O(log N)

class Node:
    int shift = 0 //number of rotations
    int max[12] //maximum value for shift = 0..11
    Node left_child //the left child of this node
    Node right_child //the right child of this node

2)伝播:

void propagate(Node node):
    node.left_child.shift += node.shift
    node.left_child.shift %= 12
    node.right_child.shift += node.shift
    node.right_child.shift %= 12
    node.shift = 0
    for i = 0..11:
        node.max[i] = max(get_max(node.left_child, i), 
                          get_max(node.right_child, i))

int get_max(Node node, int shift):
     return node.max[(shift + node.shift) % 12]

3) 従来のセグメント ツリーと同様に、更新と取得操作を実装できます。

なぜそれは速く働くのですか？propagate再帰的ではないためです。これは、クエリに応答するときのツリー トラバーサル中にアクセスされるノードに対してのみ呼び出されます。そして、クエリごとにそのようなノードしかありませんO(log N)（セグメントツリーのプロパティのため）。

定数 12 が使用されるのはなぜですか? lcm(1, 2, 3, 4) = 12.(1, 2, 3, 4各配列要素の可能な桁数であるため)。

于 2014-08-09T15:17:42.587 に答える