3624. Number of Integers With Popcount-Depth Equal to K II Hard

1/**
2 * [3624] Number of Integers With Popcount-Depth Equal to K II
3 *
4 * You are given an integer array nums.
5 * For any positive integer x, define the following sequence:
6 * 
7 * 	p0 = x
8 * 	pi+1 = popcount(pi) for all i >= 0, where popcount(y) is the number of set bits (1's) in the binary representation of y.
9 * 
10 * This sequence will eventually reach the value 1.
11 * The popcount-depth of x is defined as the smallest integer d >= 0 such that pd = 1.
12 * For example, if x = 7 (binary representation "111"). Then, the sequence is: 7 → 3 → 2 → 1, so the popcount-depth of 7 is 3.
13 * You are also given a 2D integer array queries, where each queries[i] is either:
14 * 
15 * 	[1, l, r, k] - Determine the number of indices j such that l <= j <= r and the popcount-depth of nums[j] is equal to k.
16 * 	[2, idx, val] - Update nums[idx] to val.
17 * 
18 * Return an integer array answer, where answer[i] is the number of indices for the i^th query of type [1, l, r, k].
19 *  
20 * <strong class="example">Example 1:
21 * <div class="example-block">
22 * Input: <span class="example-io">nums = [2,4], queries = [[1,0,1,1],[2,1,1],[1,0,1,0]]</span>
23 * Output: <span class="example-io">[2,1]</span>
24 * Explanation:
25 * <table style="border: 1px solid black;">
26 * 	<thead>
27 * 		<tr>
28 * 			<th style="border: 1px solid black;">i</th>
29 * 			<th style="border: 1px solid black;">queries[i]</th>
30 * 			<th style="border: 1px solid black;">nums</th>
31 * 			<th style="border: 1px solid black;">binary(nums)</th>
32 * 			<th style="border: 1px solid black;">popcount-<br />
33 * 			depth</th>
34 * 			<th style="border: 1px solid black;">[l, r]</th>
35 * 			<th style="border: 1px solid black;">k</th>
36 * 			<th style="border: 1px solid black;">Valid<br />
37 * 			nums[j]</th>
38 * 			<th style="border: 1px solid black;">updated<br />
39 * 			nums</th>
40 * 			<th style="border: 1px solid black;">Answer</th>
41 * 		</tr>
42 * 	</thead>
43 * 	<tbody>
44 * 		<tr>
45 * 			<td style="border: 1px solid black;">0</td>
46 * 			<td style="border: 1px solid black;">[1,0,1,1]</td>
47 * 			<td style="border: 1px solid black;">[2,4]</td>
48 * 			<td style="border: 1px solid black;">[10, 100]</td>
49 * 			<td style="border: 1px solid black;">[1, 1]</td>
50 * 			<td style="border: 1px solid black;">[0, 1]</td>
51 * 			<td style="border: 1px solid black;">1</td>
52 * 			<td style="border: 1px solid black;">[0, 1]</td>
53 * 			<td style="border: 1px solid black;">&mdash;</td>
54 * 			<td style="border: 1px solid black;">2</td>
55 * 		</tr>
56 * 		<tr>
57 * 			<td style="border: 1px solid black;">1</td>
58 * 			<td style="border: 1px solid black;">[2,1,1]</td>
59 * 			<td style="border: 1px solid black;">[2,4]</td>
60 * 			<td style="border: 1px solid black;">[10, 100]</td>
61 * 			<td style="border: 1px solid black;">[1, 1]</td>
62 * 			<td style="border: 1px solid black;">&mdash;</td>
63 * 			<td style="border: 1px solid black;">&mdash;</td>
64 * 			<td style="border: 1px solid black;">&mdash;</td>
65 * 			<td style="border: 1px solid black;">[2,1]</td>
66 * 			<td style="border: 1px solid black;">&mdash;</td>
67 * 		</tr>
68 * 		<tr>
69 * 			<td style="border: 1px solid black;">2</td>
70 * 			<td style="border: 1px solid black;">[1,0,1,0]</td>
71 * 			<td style="border: 1px solid black;">[2,1]</td>
72 * 			<td style="border: 1px solid black;">[10, 1]</td>
73 * 			<td style="border: 1px solid black;">[1, 0]</td>
74 * 			<td style="border: 1px solid black;">[0, 1]</td>
75 * 			<td style="border: 1px solid black;">0</td>
76 * 			<td style="border: 1px solid black;">[1]</td>
77 * 			<td style="border: 1px solid black;">&mdash;</td>
78 * 			<td style="border: 1px solid black;">1</td>
79 * 		</tr>
80 * 	</tbody>
81 * </table>
82 * Thus, the final answer is [2, 1].
83 * </div>
84 * <strong class="example">Example 2:
85 * <div class="example-block">
86 * Input: <span class="example-io">nums = [3,5,6], queries = [[1,0,2,2],[2,1,4],[1,1,2,1],[1,0,1,0]]</span>
87 * Output: <span class="example-io">[3,1,0]</span>
88 * Explanation:
89 * <table style="border: 1px solid black;">
90 * 	<thead>
91 * 		<tr>
92 * 			<th style="border: 1px solid black;">i</th>
93 * 			<th style="border: 1px solid black;">queries[i]</th>
94 * 			<th style="border: 1px solid black;">nums</th>
95 * 			<th style="border: 1px solid black;">binary(nums)</th>
96 * 			<th style="border: 1px solid black;">popcount-<br />
97 * 			depth</th>
98 * 			<th style="border: 1px solid black;">[l, r]</th>
99 * 			<th style="border: 1px solid black;">k</th>
100 * 			<th style="border: 1px solid black;">Valid<br />
101 * 			nums[j]</th>
102 * 			<th style="border: 1px solid black;">updated<br />
103 * 			nums</th>
104 * 			<th style="border: 1px solid black;">Answer</th>
105 * 		</tr>
106 * 	</thead>
107 * 	<tbody>
108 * 		<tr>
109 * 			<td style="border: 1px solid black;">0</td>
110 * 			<td style="border: 1px solid black;">[1,0,2,2]</td>
111 * 			<td style="border: 1px solid black;">[3, 5, 6]</td>
112 * 			<td style="border: 1px solid black;">[11, 101, 110]</td>
113 * 			<td style="border: 1px solid black;">[2, 2, 2]</td>
114 * 			<td style="border: 1px solid black;">[0, 2]</td>
115 * 			<td style="border: 1px solid black;">2</td>
116 * 			<td style="border: 1px solid black;">[0, 1, 2]</td>
117 * 			<td style="border: 1px solid black;">&mdash;</td>
118 * 			<td style="border: 1px solid black;">3</td>
119 * 		</tr>
120 * 		<tr>
121 * 			<td style="border: 1px solid black;">1</td>
122 * 			<td style="border: 1px solid black;">[2,1,4]</td>
123 * 			<td style="border: 1px solid black;">[3, 5, 6]</td>
124 * 			<td style="border: 1px solid black;">[11, 101, 110]</td>
125 * 			<td style="border: 1px solid black;">[2, 2, 2]</td>
126 * 			<td style="border: 1px solid black;">&mdash;</td>
127 * 			<td style="border: 1px solid black;">&mdash;</td>
128 * 			<td style="border: 1px solid black;">&mdash;</td>
129 * 			<td style="border: 1px solid black;">[3, 4, 6]</td>
130 * 			<td style="border: 1px solid black;">&mdash;</td>
131 * 		</tr>
132 * 		<tr>
133 * 			<td style="border: 1px solid black;">2</td>
134 * 			<td style="border: 1px solid black;">[1,1,2,1]</td>
135 * 			<td style="border: 1px solid black;">[3, 4, 6]</td>
136 * 			<td style="border: 1px solid black;">[11, 100, 110]</td>
137 * 			<td style="border: 1px solid black;">[2, 1, 2]</td>
138 * 			<td style="border: 1px solid black;">[1, 2]</td>
139 * 			<td style="border: 1px solid black;">1</td>
140 * 			<td style="border: 1px solid black;">[1]</td>
141 * 			<td style="border: 1px solid black;">&mdash;</td>
142 * 			<td style="border: 1px solid black;">1</td>
143 * 		</tr>
144 * 		<tr>
145 * 			<td style="border: 1px solid black;">3</td>
146 * 			<td style="border: 1px solid black;">[1,0,1,0]</td>
147 * 			<td style="border: 1px solid black;">[3, 4, 6]</td>
148 * 			<td style="border: 1px solid black;">[11, 100, 110]</td>
149 * 			<td style="border: 1px solid black;">[2, 1, 2]</td>
150 * 			<td style="border: 1px solid black;">[0, 1]</td>
151 * 			<td style="border: 1px solid black;">0</td>
152 * 			<td style="border: 1px solid black;">[]</td>
153 * 			<td style="border: 1px solid black;">&mdash;</td>
154 * 			<td style="border: 1px solid black;">0</td>
155 * 		</tr>
156 * 	</tbody>
157 * </table>
158 * Thus, the final answer is [3, 1, 0].
159 * </div>
160 * <strong class="example">Example 3:
161 * <div class="example-block">
162 * Input: <span class="example-io">nums = [1,2], queries = [[1,0,1,1],[2,0,3],[1,0,0,1],[1,0,0,2]]</span>
163 * Output: <span class="example-io">[1,0,1]</span>
164 * Explanation:
165 * <table style="border: 1px solid black;">
166 * 	<thead>
167 * 		<tr>
168 * 			<th style="border: 1px solid black;">i</th>
169 * 			<th style="border: 1px solid black;">queries[i]</th>
170 * 			<th style="border: 1px solid black;">nums</th>
171 * 			<th style="border: 1px solid black;">binary(nums)</th>
172 * 			<th style="border: 1px solid black;">popcount-<br />
173 * 			depth</th>
174 * 			<th style="border: 1px solid black;">[l, r]</th>
175 * 			<th style="border: 1px solid black;">k</th>
176 * 			<th style="border: 1px solid black;">Valid<br />
177 * 			nums[j]</th>
178 * 			<th style="border: 1px solid black;">updated<br />
179 * 			nums</th>
180 * 			<th style="border: 1px solid black;">Answer</th>
181 * 		</tr>
182 * 	</thead>
183 * 	<tbody>
184 * 		<tr>
185 * 			<td style="border: 1px solid black;">0</td>
186 * 			<td style="border: 1px solid black;">[1,0,1,1]</td>
187 * 			<td style="border: 1px solid black;">[1, 2]</td>
188 * 			<td style="border: 1px solid black;">[1, 10]</td>
189 * 			<td style="border: 1px solid black;">[0, 1]</td>
190 * 			<td style="border: 1px solid black;">[0, 1]</td>
191 * 			<td style="border: 1px solid black;">1</td>
192 * 			<td style="border: 1px solid black;">[1]</td>
193 * 			<td style="border: 1px solid black;">&mdash;</td>
194 * 			<td style="border: 1px solid black;">1</td>
195 * 		</tr>
196 * 		<tr>
197 * 			<td style="border: 1px solid black;">1</td>
198 * 			<td style="border: 1px solid black;">[2,0,3]</td>
199 * 			<td style="border: 1px solid black;">[1, 2]</td>
200 * 			<td style="border: 1px solid black;">[1, 10]</td>
201 * 			<td style="border: 1px solid black;">[0, 1]</td>
202 * 			<td style="border: 1px solid black;">&mdash;</td>
203 * 			<td style="border: 1px solid black;">&mdash;</td>
204 * 			<td style="border: 1px solid black;">&mdash;</td>
205 * 			<td style="border: 1px solid black;">[3, 2]</td>
206 * 			<td style="border: 1px solid black;"> </td>
207 * 		</tr>
208 * 		<tr>
209 * 			<td style="border: 1px solid black;">2</td>
210 * 			<td style="border: 1px solid black;">[1,0,0,1]</td>
211 * 			<td style="border: 1px solid black;">[3, 2]</td>
212 * 			<td style="border: 1px solid black;">[11, 10]</td>
213 * 			<td style="border: 1px solid black;">[2, 1]</td>
214 * 			<td style="border: 1px solid black;">[0, 0]</td>
215 * 			<td style="border: 1px solid black;">1</td>
216 * 			<td style="border: 1px solid black;">[]</td>
217 * 			<td style="border: 1px solid black;">&mdash;</td>
218 * 			<td style="border: 1px solid black;">0</td>
219 * 		</tr>
220 * 		<tr>
221 * 			<td style="border: 1px solid black;">3</td>
222 * 			<td style="border: 1px solid black;">[1,0,0,2]</td>
223 * 			<td style="border: 1px solid black;">[3, 2]</td>
224 * 			<td style="border: 1px solid black;">[11, 10]</td>
225 * 			<td style="border: 1px solid black;">[2, 1]</td>
226 * 			<td style="border: 1px solid black;">[0, 0]</td>
227 * 			<td style="border: 1px solid black;">2</td>
228 * 			<td style="border: 1px solid black;">[0]</td>
229 * 			<td style="border: 1px solid black;">&mdash;</td>
230 * 			<td style="border: 1px solid black;">1</td>
231 * 		</tr>
232 * 	</tbody>
233 * </table>
234 * Thus, the final answer is [1, 0, 1].
235 * </div>
236 *  
237 * Constraints:
238 * 
239 * 	1 <= n == nums.length <= 10^5
240 * 	1 <= nums[i] <= 10^15
241 * 	1 <= queries.length <= 10^5
242 * 	queries[i].length == 3 or 4
243 * 	
244 * 		queries[i] == [1, l, r, k] or,
245 * 		queries[i] == [2, idx, val]
246 * 		0 <= l <= r <= n - 1
247 * 		0 <= k <= 5
248 * 		0 <= idx <= n - 1
249 * 		1 <= val <= 10^15
250 * 	
251 * 	
252 * 
253 */
254pub struct Solution {}
255
256// problem: https://leetcode.com/problems/number-of-integers-with-popcount-depth-equal-to-k-ii/
257// discuss: https://leetcode.com/problems/number-of-integers-with-popcount-depth-equal-to-k-ii/discuss/?currentPage=1&orderBy=most_votes&query=
258
259// submission codes start here
260
261impl Solution {
262    pub fn popcount_depth(nums: Vec<i64>, queries: Vec<Vec<i64>>) -> Vec<i32> {
263        vec![]
264    }
265}
266
267// submission codes end
268
269#[cfg(test)]
270mod tests {
271    use super::*;
272
273    #[test]
274    fn test_3624() {
275    }
276}
277