c++ - 快速回答子数组查询的高效算法

Question

前几天我遇到了一个查询相关的问题，但是我无法解决。

给定一个包含 N 个整数和一个正整数 M 的数组，您必须回答 Q 个问题。每个查询的特征为 ( i , j )，其中 i 和 j 分别是数组的索引。在每个查询中，您必须回答存在多少对(r，s)

1. i <= r <= s <= j
2. 索引在 [ r , s ] 中的数组元素之和可以被 M 整除。

限制:

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

我有一个动态编程解决方案，可以在 O( N^2 ) 中预处理每个查询( r ， s )，但这是不够快。有没有更有效的解决方案？我对 Mo 的算法或线段树有一些想法，但我无法理解。

Answer 1

1. 为每个 i = 1..N 计算原始数组的前缀和(假设它从 1 开始) .
   
   Sum[r] 的等效项和 Sum[s]对于任意两个指数 r和 s其中 r < s表示索引在 [r+1, s] 中的数组元素的总和可以被 M 整除(并且我们需要计算区间内此类等价的数量)。这一步的时间复杂度是O(N) .
   
   

2. 预先计算数组Count对于每个 i = 1..N, j = 0..M-1 :
   Count[i][j]存储 Sum[len] 的次数(其中 len <= i )等于 j .这一步的时间复杂度是O(N*M) .
   
   

3. 对于每个查询 (i, j)答案将等于:
   对于余数的每个可能值 k我们找到D(k) - Sum[len] 的次数等于k区间内[i, j] .然后我们将 D(k) 的所有可能对的数量添加到结果中。区间边界即 D(k)*(D(k)-1)/2 .时间复杂度:O(M)对于每个查询。
   
   

复杂度:O(N) + O(N*M) + O(Q*M) = O((Q+N)*M) ，这对于给定的约束是可以的。