Dada una array arr[] que consta de N enteros, una array Q[][] que consta de consultas de la forma {l, r} . Para cada consulta {l, r} , la tarea es determinar la suma mínima de todos los valores que deben agregarse a cada elemento de array en ese rango de modo que el AND bit a bit de todos los números en ese rango exceda 0 .
Nota: Se pueden agregar diferentes valores a diferentes enteros en el rango dado.
Ejemplos:
Entrada: arr[] = {1, 2, 4, 8}, Q[][] = {{1, 4}, {2, 3}, {1, 3}}
Salida: 3 2 2
Explicación: representación binaria de elementos de array son los siguientes:
1 – 0001
2 – 0010
4 – 0100
8 – 1000
Para la primera consulta {1, 4}, agregue 1 a todos los números presentes en el rango excepto el primer número. Por lo tanto, Bitwise AND = (1 & 3 & 5 & 9) = 1 y suma mínima de elementos agregados = 3.
Para la segunda consulta {2, 3}, agregue 2 al 3er elemento. Por lo tanto, AND bit a bit = (2 y 6) = 2 y suma mínima de elementos agregados = 2.
Para la tercera consulta {1, 3}, agregue 1 a los elementos 2 y 3. Por lo tanto, Bitwise AND = (1 & 3 & 5) = 1 y suma mínima de elementos agregados = 2.Entrada: arr[] = {4, 6, 5, 3}, Q[][] = {{1, 4}}
Salida: 1
Explicación: La forma óptima de hacer que Bitwise AND no sea cero es agregar 1 a último elemento Por lo tanto, AND bit a bit = (4 & 6 & 5 & 4) = 4 y suma mínima de elementos sumados = 1.
Enfoque: la idea es observar primero que el AND bit a bit de todos los enteros en el rango [l, r] solo puede ser distinto de cero si se establece un bit en un índice particular para cada entero en ese rango.
Siga los pasos a continuación para resolver el problema:
- Inicialice un vector 2D pre donde pre[i][j] almacena la suma mínima de enteros que se agregarán a todos los enteros desde el índice 0 hasta el índice i de modo que, para cada uno de ellos, se establezca su j -ésimo bit.
- Para cada elemento en el índice i , verifique cada uno de sus bits de j = 0 a 31 .
- Inicialice una suma variable con 0 .
- Si se establece el j -ésimo bit, actualice pre[i][j] como pre[i][j]=pre[i-1][j] e incremente la suma en 2 j . De lo contrario, actualice pre[i][j] = pre[i-1][j] + 2 j – sum donde (2 j -sum) es el valor que debe agregarse para establecer el j -ésimo bit de arr[i] .
- Ahora, para cada consulta {l, r} , la suma mínima requerida para establecer el j -ésimo bit de todos los elementos en el rango dado es pre[r][j] – pre[l-1][j] .
- Para cada consulta {l, r} , encuentre la respuesta para cada bit de j = 0 a 31 e imprima el mínimo entre ellos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the min sum required // to set the jth bit of all integer void processing(vector<int> v, vector<vector<long long int> >& pre) { // Number of elements int N = v.size(); // Traverse all elements for (int i = 0; i < N; i++) { // Binary representation bitset<32> b(v[i]); long long int sum = 0; // Take previous values if (i != 0) { pre[i] = pre[i - 1]; } // Processing each bit and // store it in 2d vector for (int j = 0; j < 32; j++) { if (b[j] == 1) { sum += 1ll << j; } else { pre[i][j] += (1ll << j) - sum; } } } } // Function to print the minimum // sum for each query long long int process_query(vector<vector<int> > Q, vector<vector<long long int> >& pre) { // Stores the sum for each query vector<int> ans; for (int i = 0; i < Q.size(); i++) { // Update wrt 0-based index --Q[i][0], --Q[i][1]; // Initizlize answer long long int min1 = INT_MAX; // Find minimum sum for each bit if (Q[i][0] == 0) { for (int j = 0; j < 32; j++) { min1 = min(pre[Q[i][1]][j], min1); } } else { for (int j = 0; j < 32; j++) { min1 = min(pre[Q[i][1]][j] - pre[Q[i][0] - 1][j], min1); } } // Store the answer for // each query ans.push_back(min1); } // Print the answer vector for (int i = 0; i < ans.size(); i++) { cout << ans[i] << " "; } } // Driver Code int main() { // Given array vector<int> arr = { 1, 2, 4, 8 }; // Given Queries vector<vector<int> > Q = { { 1, 4 }, { 2, 3 }, { 1, 3 } }; // 2d Prefix vector vector<vector<long long int> > pre( 100001, vector<long long int>(32, 0)); // Preprocessing processing(arr, pre); // Function call for queries process_query(Q, pre); return 0; }
3 2 2
Complejidad de tiempo: O(N*32 + tamaño de(Q)*32)
Espacio auxiliar: O(N*32)
Publicación traducida automáticamente
Artículo escrito por abhishek_padghan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA