Problem statement
Aman is in a hurry! He is late for his office. So he has no time to deal with a long and complex problem statement. You are given two arrays, ‘arr1’ and ‘arr2’. Each element of either array, arr1[i] or arr2[i], is a positive integer not greater than x. Given Q queries, each of the form {L, R}, the answer for each query is
where the count is the frequency of the integer i in the range L R.
The answer to the problem is the product of the answers of all the individual queries modulo 109+7. Return the answer for Aman and Multiplicative Queries.
The first line contains three integers, N, X, and Q, representing the size of the array, the range of allowed values for each array element, and the number of queries, respectively.
The second line contains N positive integers, representing the elements of the array arr1. The ith (1-based indexing) of these represents arr1i.
The third line contains N+1 positive integers, denoting the elements of the array arr2. The ith (0-based indexing) of these represents arr2i.
The ith of the next Q lines contains two integers, L and R, for the ith query.
Return and print the single integer, which is the answer for the given problem statement Aman and Multiplicative Queries for two arrays.
Example 1
Input
6 7 3
1 2 2 3 4 5
1 1 2 3 4 5 5
2 4
1 2
4 6
Output
2
Explanation
In the range specified by the first query, there are 0 occurrences of 1, 2 occurrences of 2, 1 occurrence of 3, and 0 occurrences of both 4 and 5. So the answer for the first query is arr2[0] * arr2[2] * arr2[1] * arr2[0] * arr2[0] = 2.
In the range specified by the second query, there is 1 occurrence of 1, 1 occurrence of 2, 0 occurrences of 3, and 0 occurrences of both 4 and 5. So the answer for the second query is arr2[1] * arr2[1] * arr2[0] * arr2[0] * arr2[0] = 1.
In the range specified by the third query, there are 0 occurrences of 1, 0 occurrences of 2, 1 occurrence of 3, and 1 occurrence of both 4 and 5. So the answer for the third query is arr2[0] * arr2[0] * arr2[1] * arr2[1] * arr2[1] = 1.
Hence the final answer is 2 * 1 * 1 = 2.
Also see, Euclid GCD Algorithm
Approach
The brute force approach to solve this problem Aman and Multiplicative Queries for two arrays is that, we can iterate linearly for all queries and then can calculate the desired output but doing so will cost high time complexity because in the worst case we may need to iterate on all the queries from the 0th index to the last index which will cost the time complexity of O(N * Q) where ‘N’ is the total number of elements in the array. So to optimize this approach, we can use the concept of Mo’s algorithm. In mo's algorithm, we first sort all the queries, which are also known as offline processing of queries. Offline means that your solution reads all queries then process them. After applying Mo’s algorithm we also need to perform division MOD 1000000007; for that we can use modular multiplicative inverses algorithm. Below is the detailed algorithm and implementation of the given approach.
Algorithm
- First, apply the Mo's algorithm on the queries by sorting the queries by dividing the array into blocks of size N.
- Once you have applied the Mo's algorithm, all you need to do is figure out how increasing the count of a number changes your answer and how decreasing the count of a number changes your answer.
- If we increase cnt from x to x+1, our answer gets multiplied by arr2(x+1) and divided by arr2(x).
- If we decrease cnt from x+1 to x, our answer gets multiplied by FUNC(x) and divided by arr2(x+1).
- Since the answer can be large, we need to return answer % 1000000007. For that, we have to use the modular multiplicative inverses algorithm.
Code:
// Code for Multiplicative Queries for two arrays
#include <bits/stdc++.h>
#define pb push_back
#define MOD (1000000007)
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
ll pwr(ll base, ll p, ll mod = MOD){
ll final_ans = 1;while(p){if(p&1)final_ans=(final_ans*base)%mod;base=(base*base)%mod;p/=2;}return final_ans;
}
ll modular_inverse(ll n){
return pwr(n, MOD-2);
}
#define N 1000005
// Declaring input arrays and frequency array
int n, BLOCK, X, arr1[N], arr2[N], cnt[N];
ll curr_value;
ii queryarr[N];
inline int getBlock(int pos){
return (pos-1) / BLOCK;
}
// comparator function for sorting
bool comp(ii a, ii b){
int b1 = getBlock(a.first);
int b2 = getBlock(b.first);
if(b1 != b2) return b1 < b2;
return a.second < b.second;
}
// inline function to remove
inline void remove(int pos){
if(cnt[arr1[pos]] >= 0)
curr_value = (curr_value * modular_inverse(arr2[cnt[arr1[pos]]])) % MOD;
cnt[arr1[pos]]--;
if(cnt[arr1[pos]] >= 0)
curr_value = (curr_value * arr2[cnt[arr1[pos]]]) % MOD;
}
// inline function to add
inline void add(int pos){
if(cnt[arr1[pos]] >= 0)
curr_value = (curr_value * modular_inverse(arr2[cnt[arr1[pos]]])) % MOD;
cnt[arr1[pos]]++;
if(cnt[arr1[pos]] >= 0)
curr_value = (curr_value * arr2[cnt[arr1[pos]]]) % MOD;
}
int main(){
// Taking the input according to given format
int query;
cin>>n;
cin>>X;
cin>>query;
for(int i=1;i<=n;i++){
cin>>arr1[i];
assert(arr1[i] > 0 && arr1[i] <= X);
}
for(int i=0;i<=n;i++){
cin>>arr2[i];
assert(arr2[i] > 0 && arr2[i] <= X);
}
for(int i=0;i<query;i++){
cin>>queryarr[i].first>>queryarr[i].second;
assert(1<=queryarr[i].first && queryarr[i].first<=queryarr[i].second && queryarr[i].second<=n);
}
BLOCK = ceil(sqrt(n));
// Sorting the query array to optimize the problem
sort(queryarr, queryarr+query, comp);
int left = 1, right = 1;
cnt[arr1[1]] = 1;
curr_value = 1;
for(int i=1;i<=X;i++)
curr_value = (curr_value * arr2[cnt[i]]) % MOD;
ll final_ans = 1;
// Working on all the queries for problem Multiplicative Queries for two arrays
for(int i=0;i<query;i++){
int start = queryarr[i].first;
int end = queryarr[i].second;
while(left < start){
remove(left);
left++;
}
while(left > start){
left--;
add(left);
}
while(right < end){
right++;
add(right);
}
while(right > end){
remove(right);
right--;
}
assert(curr_value > 0);
final_ans = (final_ans * curr_value) % MOD;
}
// Multiplicative Queries for two arrays
cout<<final_ans;
return 0;
}Input
|
Output
2Time Complexity
O((n + q) / n
The time complexity for Aman and Multiplicative Queries for two arrays solution is O((n + q) / n). Where 'n' is the size of the given input array and q is the total number of queries. To sort the array of queries it will cost q * log(q) time then for calling the blocks (n / n ) * n time will be required where n is the total instances of the rightmost query and n / n is the number of blocks. The maximum change in the left-most range of query can be n / q.So the total time of complexity will be O((n + q) / n.
Space Complexity
O(n)
The space complexity for Aman and Multiplicative Queries for two arrays solution is O(n). Where 'n' is the size of the given input array. We are creating an extra array 'cnt' to maintain the frequency count that will cost linear time complexity.
38+ registered 