3525. Find X Value of Array II Hard

1/**
2 * [3525] Find X Value of Array II
3 *
4 * You are given an array of positive integers nums and a positive integer k. You are also given a 2D array queries, where queries[i] = [indexi, valuei, starti, xi].
5 * You are allowed to perform an operation once on nums, where you can remove any suffix from nums such that nums remains non-empty.
6 * The x-value of nums for a given x is defined as the number of ways to perform this operation so that the product of the remaining elements leaves a remainder of x modulo k.
7 * For each query in queries you need to determine the x-value of nums for xi after performing the following actions:
8 * 
9 * 	Update nums[indexi] to valuei. Only this step persists for the rest of the queries.
10 * 	Remove the prefix nums[0..(starti - 1)] (where nums[0..(-1)] will be used to represent the empty prefix).
11 * 
12 * Return an array result of size queries.length where result[i] is the answer for the i^th query.
13 * A prefix of an array is a <span data-keyword="subarray">subarray</span> that starts from the beginning of the array and extends to any point within it.
14 * A suffix of an array is a <span data-keyword="subarray">subarray</span> that starts at any point within the array and extends to the end of the array.
15 * Note that the prefix and suffix to be chosen for the operation can be empty.
16 * Note that x-value has a different definition in this version.
17 *  
18 * <strong class="example">Example 1:
19 * <div class="example-block">
20 * Input: <span class="example-io">nums = [1,2,3,4,5], k = 3, queries = [[2,2,0,2],[3,3,3,0],[0,1,0,1]]</span>
21 * Output: <span class="example-io">[2,2,2]</span>
22 * Explanation:
23 * 
24 * 	For query 0, nums becomes [1, 2, 2, 4, 5], and the empty prefix must be removed. The possible operations are:
25 * 	
26 * 		Remove the suffix [2, 4, 5]. nums becomes [1, 2].
27 * 		Remove the empty suffix. nums becomes [1, 2, 2, 4, 5] with a product 80, which gives remainder 2 when divided by 3.
28 * 	
29 * 	
30 * 	For query 1, nums becomes [1, 2, 2, 3, 5], and the prefix [1, 2, 2] must be removed. The possible operations are:
31 * 	
32 * 		Remove the empty suffix. nums becomes [3, 5].
33 * 		Remove the suffix [5]. nums becomes [3].
34 * 	
35 * 	
36 * 	For query 2, nums becomes [1, 2, 2, 3, 5], and the empty prefix must be removed. The possible operations are:
37 * 	
38 * 		Remove the suffix [2, 2, 3, 5]. nums becomes [1].
39 * 		Remove the suffix [3, 5]. nums becomes [1, 2, 2].
40 * 	
41 * 	
42 * </div>
43 * <strong class="example">Example 2:
44 * <div class="example-block">
45 * Input: <span class="example-io">nums = [1,2,4,8,16,32], k = 4, queries = [[0,2,0,2],[0,2,0,1]]</span>
46 * Output: <span class="example-io">[1,0]</span>
47 * Explanation:
48 * 
49 * 	For query 0, nums becomes [2, 2, 4, 8, 16, 32]. The only possible operation is:
50 * 	
51 * 		Remove the suffix [2, 4, 8, 16, 32].
52 * 	
53 * 	
54 * 	For query 1, nums becomes [2, 2, 4, 8, 16, 32]. There is no possible way to perform the operation.
55 * </div>
56 * <strong class="example">Example 3:
57 * <div class="example-block">
58 * Input: <span class="example-io">nums = [1,1,2,1,1], k = 2, queries = [[2,1,0,1]]</span>
59 * Output: <span class="example-io">[5]</span>
60 * </div>
61 *  
62 * Constraints:
63 * 
64 * 	1 <= nums[i] <= 10^9
65 * 	1 <= nums.length <= 10^5
66 * 	1 <= k <= 5
67 * 	1 <= queries.length <= 2 * 10^4
68 * 	queries[i] == [indexi, valuei, starti, xi]
69 * 	0 <= indexi <= nums.length - 1
70 * 	1 <= valuei <= 10^9
71 * 	0 <= starti <= nums.length - 1
72 * 	0 <= xi <= k - 1
73 * 
74 */
75pub struct Solution {}
76
77// problem: https://leetcode.com/problems/find-x-value-of-array-ii/
78// discuss: https://leetcode.com/problems/find-x-value-of-array-ii/discuss/?currentPage=1&orderBy=most_votes&query=
79
80// submission codes start here
81
82impl Solution {
83    pub fn result_array(nums: Vec<i32>, k: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
84        vec![]
85    }
86}
87
88// submission codes end
89
90#[cfg(test)]
91mod tests {
92    use super::*;
93
94    #[test]
95    fn test_3525() {
96    }
97}
98