ビット配列とサブ配列の異なる値

Question

配列のビット配列およびすべてのサブ配列の異なる値の数の見方（配列のサイズは< = 1e5、配列の要素は< = 1e6）。例えば、 。 A [] = {1,2,3} 異なる値は4（1,2,3,0）です。

Answer 1

サブアレイの右側の境界の部分を修正しましょう。左境界線をイメージしましょうrから始まる左に移動するlandの値は何回変更できますか？最大でO(log(MAX_VALUE))です。どうして？部分配列のand値は変更されません

1. ：我々は左に1つの以上の要素を追加した場合、我々は二つの選択肢を持っています。

2. 変更されます。その場合、そのビット数は厳密に少なくなります（前のand値のサブマスクなので）。

このように、何らかの値が変更されたlという値しか考慮されていません。今すぐただ見つけてください。

すべての有効なiに対して、i番目のビットを持たない最後の要素の位置を格納しましょう（現在の要素のすべてのビットを反復して更新できます） 。この方法では、値がすぐに変化する次の位置を見つけることができます（つまり、設定されているすべてのビットに対してこの配列の最大値です）。ポジションをソートすると、O(1)の次に大きいポジションを見つけることができます。

このソリューションの複雑さの合計時間はO(N * log(MAX_VALUE) * log(log(MAX_VALUE)))です（配列の各要素のすべてのビットを反復処理し、それぞれの位置の配列を並べ替えて繰り返します）。空間の複雑さはO(N + MAX_VALUE)です。それは与えられた制約のために十分なはずです。

Answer 2

ビットを表す列として数字を想像してください。我々は1のシーケンスを水平に伸ばしていく。例えば：

Array index: 0 1 2 3 4 5 6 7 

Bit columns: 0 1 1 1 1 1 0 0 
       0 0 0 1 1 1 1 1 
       0 0 1 1 1 1 1 0 
       1 0 0 0 1 1 0 1 
       0 1 1 1 1 1 1 0 

左側に見ると、ゼロの後の任意のサブアレイand EDのビット行は、その行でその後変化がないことを意味ゼロ、であり続けるであろう。

たとえば、インデックス5を考えてみましょう。簡単に調べるために

     Index 5 -> 
Sorted bit rows: 1 0 0 0 1 1 
        0 0 0 1 1 1 
        0 0 1 1 1 1 
        0 1 1 1 1 1 
        0 1 1 1 1 1 

    Index 5 to 4, no change 
    Index 4 to 3, change 
    Index 2 to 1, change 
    Index 1 to 0, change 

：今すぐ左に1のインデックス5からの水平方向の列をソートすることは私たちのビット構成（ソートが各反復で行わなければならない）の変化を検出するための簡単な方法を提供しますこれらの変更は、kraskevichは、1行の水平シーケンスの長さを示す、各行の最後の未設定ビットだけを記録し、発生した固有のビット構成を格納するブール値アレイ（1e6個数最大）を記録することを提案しています。

Numbers: 1, 2, 3 

Bits: 1 0 1 
     0 1 1 

我々は左から右に移動すると、各行の最後の未設定のビットのインデックスの記録を保持し、また新たなビット構成の記録（それらのほとんどで1e6）キープ：

を

Indexes of last unset bit for each row on each iteration 
Numbers: 1, 2, 3 

A[0]: -1  arrayHash = [false,true,false,false], count = 1 
     0 

A[1]: -1 1 Now sort the column descending, representing (current - index) 
     0 0  the lengths of sequences of 1's extending to the left. 

As we move from top to bottom on this column, each value change represents a bit 
configuration and a possibly distinct count: 

    Record present bit configuration b10 
    => arrayHash = [false,true,true,false] 

    1 => 1 - 1 => sequence length 0, ignore sequence length 0 
    0 => 1 - 0 => sequence length 1, 
        unset second bit: b10 => b00 
        => new bit configuration b00 
        => arrayHash = [true,true,true,false] 

3回目の反復：

Numbers: 1, 2, 3 

A[2]: -1 1 1 
     0 0 0 

Record present bit configuration b11 
    => arrayHash = [true,true,true,true] 

（私たちは必ずしもarrayHashが満たされたかわからないので、私たちは続けています。）

1 => 2 - 1 => sequence length 1 
        unset first bit: b11 => b10 
        => seen bit configuration b10 
    0 => 2 - 0 => sequence length 2, 
        unset second bit: b10 => b00 
        => seen bit configuration b00