サブアレイクエリに迅速に応答する効率的なアルゴリズム

Question

先日、クエリに関する問題が発生しましたが、解決できません。

N整数と正の整数Mを持つ配列を考えると、あなたはQクエリに答える必要があります。各クエリは、（i,j）のように特徴付けられ、ここでおよびjがそれぞれ配列のインデックスです。各クエリでは、あなたが存在してどのように多くのペア（R、の）答えなければならないように

1. 私 < = R < = S < = J
2. 合計[r,s]の添字を持つ配列要素のうちの1つは、Mで割り切れる。
の

制限：

N <= 50,000 
Q <= 50,000 
M <= 100 

私はO（N^2）ですべてのクエリ（R、の）を前処理、動的プログラミングソリューションを持っていますが、それが十分に高速ではありません。より効率的なソリューションはありますか？私はMoのアルゴリズム、またはセグメントツリーでいくつかのアイデアを持っていますが、それを得ることはできません。

Answer 1

1. 毎i = 1..Nため（それは1ベースだと仮定して）元の配列のプレフィックス合計を計算します。
   
   r < sは[r+1, s]にインデックスを持つ配列要素の和がMで割り切れることを意味する（我々は間隔内のこのような等価の数を計算する必要がある）任意の2つの指標rとsためSum[r]とSum[s]の同値。このステップの時間複雑度はO(N)です。
   
   

2. 事前計算i = 1..N, j = 0..M-1すべての配列Count：
   Count[i][j]格納Sum[len]（len <= i）はjに等しかった回数。このステップの時間複雑度はO(N*M)です。 Sum[len]間隔[i, j]内kに等しい回数 - 私たちはD(k)を見つける残りkのすべての可能な値について
   ：答えは等しくなり、すべてのクエリ(i, j)については
   
   

3. 。次に、可能なすべての可能なペアの数をのD(k)間隔境界に加算します。時間の複雑さ：O(M)すべてのクエリ。
   
   

複雑：O(N) + O(N*M) + O(Q*M) = O((Q+N)*M)、与えられた制約のためにOKでしょう。

Answer 2

まずなおMの倍数に合計任意サブアレイ(r, s)用：

sum(r, s) == sum(i, s) - sum(i, r - 1) 

      == (qa * M + ra) - (qb * M + rb) 

raとrbの両方M未満、以上に0（すなわち各剰余後です0で割る。M）。

今すぐはMで割り切れるので、残りはMで除算したあと0です。したがって：

ra == rb 

我々はサブアレイ(i, i)合計を分割した後、すべての余りを計算する場合は、(i, i + 1)、...、r1、r2としてMによって(i, j)、...

R[0] == the number of subarrays starting at i that are divisible by M 

あらゆるk >= 0とR[k] > 1我々はR[k]を数えることができるようk < Mため：R[k]次いで、kと等しい余りの数になるように、rjは、次いでサイズMのアレイR内のすべてのこれらのカウントを格納します2選択：

(R[k] * (R[k] - 1))/2 

サブアレイがMで割り切れるですiから始まるありません。

これらの値をすべて作成して合計すると、(r, s)クエリごとにO（N + M）の回答が得られます。