4

シナリオはありませんが、ここで問題が発生します。これは私を夢中にさせているだけです。nxnブール行列があります。最初はすべての要素が0、n <= 10 ^ 6であり、入力として指定されます。次に、最大10^5のクエリがあります。各クエリは、列cのすべての要素を0または1に設定するか、行rのすべての要素を0または1に設定することができます。別のタイプのクエリで、列cまたは行rに1の総数を出力することもできます。

私はこれをどのように解決するのか分かりません、そしてどんな助けもいただければ幸いです。明らかに、クエリごとのO（n）ソリューションは実行可能ではありません。

4

2 に答える 2

3

番号を使用して変更を注文するというアイデアは、Dukelingの投稿から引用されています。

2つのマップと4つのバイナリインデックスツリー（BIT、別名フェニックツリー）が必要になります。行には1つのマップと2つのBIT、列には1つのマップと2つのBITが必要です。m_rowそれらを、、、f_row[0]およびf_row[1];と呼びましょう。m_col、f_col[0]およびf_col[1]それぞれ。

マップは、配列、ツリーのような構造、またはハッシュを使用して実装できます。2つのマップは、行/列への最後の変更を格納するために使用されます。最大で105の変更が可能であるため、その事実を使用して、単純な配列の実装からスペースを節約できます。

BITには2つの操作があります。

  • adjust(value, delta_freq)value、量によって頻度を調整しますdelta_freq。
  • rsq(from_value, to_value)、（rsqは範囲合計クエリを表します）は、からfrom_valueまでのすべての頻度の合計を求めto_valueます。

グローバル変数を宣言しましょう：version

numRow2Dブール行列の行数と2Dブール行列の列数を定義しましょうnumCol。

BITは、行と列への変更の数をカウントするために使用されるため、少なくともMAX_QUERY + 1のサイズである必要があります。これは、クエリの数と同じ数になる可能性があります。

初期化：

version = 1
# Map should return <0, 0> for rows or cols not yet
# directly updated by query
m_row = m_col = empty map
f_row[0] = f_row[1] = f_col[0] = f_col[1] = empty BIT

アルゴリズムの更新：

update(isRow, value, idx):
    if (isRow):
        # Since setting a row/column to a new value will reset
        # everything done to it, we need to erase earlier
        # modification to it.
        # For example, turn on/off on a row a few times, then
        # query some column
        <prevValue, prevVersion> = m_row.get(idx)
        if ( prevVersion > 0 ):
            f_row[prevValue].adjust( prevVersion, -1 )

        m_row.map( idx, <value, version> )
        f_row[value].adjust( version, 1 )
    else:
        <prevValue, prevVersion> = m_col.get(idx)
        if ( prevVersion > 0 ):
            f_col[prevValue].adjust( prevVersion, -1 )

        m_col.map( idx, <value, version> )
        f_col[value].adjust( version, 1 )

    version = version + 1

カウントアルゴリズム：

count(isRow, idx):
    if (isRow):
        # If this is row, we want to find number of reverse modifications
        # done by updating the columns
        <value, row_version> = m_row.get(idx)
        count = f_col[1 - value].rsq(row_version + 1, version)
    else:
        # If this is column, we want to find number of reverse modifications
        # done by updating the rows
        <value, col_version> = m_col.get(idx)
        count = f_row[1 - value].rsq(col_version + 1, version)

    if (isRow):
       if (value == 1):
           return numRow - count
       else:
           return count
    else:
       if (value == 1):
           return numCol - count
       else:
           return count

複雑さは、更新とカウントの両方で最悪の場合は対数です。

于 2013-02-04T22:36:40.043 に答える
1

バージョンは、更新ごとに自動インクリメントされる値を意味します。

各行と列に最終バージョンと最終更新値を保存します。

行のリスト（ゼロのバージョンとカウント、および1のカウント）を格納します。列についても同じです。つまり、グリッド全体のリストは2つだけです。

行が更新されると、そのバージョンが現在のバージョンに設定され、行のリストにバージョンとが挿入されますif (oldRowValue == 0) zeroCount = oldZeroCount else zeroCount = oldZeroCount + 1（したがって、これはゼロの数ではなく、値がゼロで更新された回数です）。oneCountについても同じです。列についても同じです。

行を出力すると、行のバージョンと最後の値が取得され、列リストでそのバージョンのバイナリ検索が実行されます（最初の値がより大きい）。それで：

if (rowValue == 1)
  target = n*rowValue
           - (latestColZeroCount - colZeroCount)
           + (latestColOneCount - colOneCount)
else
  target = (latestColOneCount - colOneCount)

上記が機能するかどうかはわかりません。

これは、更新の場合はO（1）、印刷の場合はO（log k）です。ここで、kは更新の数です。

于 2013-02-04T21:19:26.523 に答える