1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
// 2438. Range Product Queries of Powers
#include "leetcode.h"
/*
* given a positive integer 'n', there exists a 0-indexed array called 'powers'
* composed of the minimum number of powers of 2 that sum to 'n'. the array is
* sorted in non-decreasing order, and there is only one way to form the array.
* you are also given a 0-indexed 2d integer array 'queries' where 'queries[i] =
* [left_i, right_i]'. each 'queries[i]' represents a query where you have to
* find the product of all 'powers[j]' with 'left_i <= j <= right_i'. return an
* array 'answers', equal in length to 'queries', where 'answers[i]' is the
* answer to each i'th query. since the answer may be too large, each
* 'answers[i]' should be returned modulo 10e9+7.
*/
const int mod = 1e9 + 7;
void get_products(int *powers, long long *seg, int root, int low, int high) {
if (low == high) {
seg[root] = powers[low];
return;
}
int i = (root << 1) + 1;
int mid = (low + high) >> 1;
get_products(powers, seg, i, low, mid);
get_products(powers, seg, i + 1, mid + 1, high);
seg[root] = (seg[i] * seg[i + 1]) % mod;
}
int range_query(long long *seg, int root, int low, int high, int left,
int right) {
if (high < left || low > right)
return 1;
if (low >= left && high <= right)
return seg[root];
int i = (root << 1) + 1;
int mid = (low + high) >> 1;
long p1 = range_query(seg, i, low, mid, left, right);
long p2 = range_query(seg, i + 1, mid + 1, high, left, right);
return (p1 * p2) % mod;
}
int *productQueries(int n, int **queries, int queriesSize, int *queriesColSize,
int *returnSize) {
int powers[33], ns = 0, mask = 1;
while (n > 0) {
if (n & mask) {
powers[ns++] = mask;
n &= ~mask;
}
mask <<= 1;
}
long long seg[150];
get_products(powers, seg, 0, 0, ns - 1);
int *ans = (int *)malloc(queriesSize * sizeof(int));
for (int i = 0; i < queriesSize; ++i)
ans[i] = range_query(seg, 0, 0, ns - 1, queries[i][0], queries[i][1]);
*returnSize = queriesSize;
return ans;
}
int main() {
int q1i[3][2] = {{0, 1}, {2, 2}, {0, 3}}, q2i[1][2] = {{0, 0}};
struct two_d_arr q1, q2;
two_d_arr_init(&q1, ARRAY_SIZE(q1i), ARRAY_SIZE(q1i[0]), q1i);
two_d_arr_init(&q2, ARRAY_SIZE(q2i), ARRAY_SIZE(q2i[0]), q2i);
int rs1, *pq1 = productQueries(15, q1.arr, q1.row_size, q1.col_size, &rs1);
int rs2, *pq2 = productQueries(2, q2.arr, q2.row_size, q2.col_size, &rs2);
for (int i = 0; i < rs1; i++)
printf("%d ", pq1[i]); // expect: 2 4 6
printf("\n");
for (int i = 0; i < rs2; i++)
printf("%d ", pq2[i]); // expect: 2
printf("\n");
free(pq1);
free(pq2);
two_d_arr_free(&q1);
two_d_arr_free(&q2);
}
|