Problem Link
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, q, l, r;
cin >> n >> q;
long arr[n];
vector<long> b[n];
for(int i = 0; i < n; i++)
{
cin >> arr[i];
long temp = arr[i];
int x = 0;
for(int j = 0; j < 32; j++)
{
b[i].push_back(0);
}
while(temp)
{
b[i][x] = temp % 2;
temp /= 2;
x++;
}
}
for(int i = 1; i < n; i++)
{
for(int j = 0; j < 32; j++)
{
b[i][j] += b[i - 1][j];
}
}
while(q--)
{
cin >> l >> r;
l --;
r--;
long res = 0;
for(int i = 0; i < 31; i++)
{
int setBits, unsetBits;
if(l > 0)
{
setBits = b[r][i] - b[l - 1][i];
unsetBits = r - l + 1 - setBits;
}
else
{
setBits = b[r][i];
unsetBits = r - l + 1 - setBits;
}
if(setBits < unsetBits)
{
res |= (1 << i);
}
}
cout << res << endl;
}
}
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, q, l, r;
cin >> n >> q;
long arr[n];
vector<long> b[n];
for(int i = 0; i < n; i++)
{
cin >> arr[i];
long temp = arr[i];
int x = 0;
for(int j = 0; j < 32; j++)
{
b[i].push_back(0);
}
while(temp)
{
b[i][x] = temp % 2;
temp /= 2;
x++;
}
}
for(int i = 1; i < n; i++)
{
for(int j = 0; j < 32; j++)
{
b[i][j] += b[i - 1][j];
}
}
while(q--)
{
cin >> l >> r;
l --;
r--;
long res = 0;
for(int i = 0; i < 31; i++)
{
int setBits, unsetBits;
if(l > 0)
{
setBits = b[r][i] - b[l - 1][i];
unsetBits = r - l + 1 - setBits;
}
else
{
setBits = b[r][i];
unsetBits = r - l + 1 - setBits;
}
if(setBits < unsetBits)
{
res |= (1 << i);
}
}
cout << res << endl;
}
}
Comments
Post a Comment