# HackerEarth Xor Rectangle problem solution

In this HackerEarth Xor Rectangle problem solution, You have an array of N integers S1, S2, ... SN. Consider a N x N matrix such that Aij = Si XOR SJ.
You have been given Q queries. Each query consists of four integers x1, y1, x2, y2 which denotes a submatrix with (x1, y1) as their top-left corner and (x2, y2) as their bottom-right corner such that x1 <= x2 and y1 <= y2. For each query, you have to print the summation of all integers lying in queried submatrix.

## HackerEarth Xor Rectangle problem solution.

`#include<bits/stdc++.h>using namespace std;#define ll long long#define rep(i,n) for(int i=0;i<n;i++)int s[1000011][32];int p[1000011];int main() {    ios_base::sync_with_stdio(0);    cin.tie(0);    int N;    cin >> N;    for(int i=1;i<=N;i++) {        cin >> p[i];        for(int j=0;j<20;j++) {            if(p[i]&(1<<j)) {                s[i][j]++;            }            s[i][j]+=s[i-1][j];        }    }    ll o1,o2,z1,z2;    int Q,x1,y1,x2,y2;    cin >> Q;    while(Q--) {        cin >> x1 >> y1 >> x2 >> y2;        ll ans = 0;        rep(j,20) {            o1 = s[x2][j]-s[x1-1][j];            z1 = x2-x1+1 - o1;            o2 = s[y2][j]-s[y1-1][j];            z2 = y2-y1+1 - o2;            ans+=(o1*z2+o2*z1)*(1LL<<j);        }        cout << ans << "\n";    }}`

### Second solution

`#pragma GCC optimize("O3")#define _CRT_SECURE_NO_WARNINGS#include <fstream>#include <iostream>#include <string>#include <complex>#include <math.h>#include <set>#include <vector>#include <map>#include <queue>#include <stdio.h>#include <stack>#include <algorithm>#include <list>#include <ctime>#include <memory.h>#include <assert.h>#define y0 sdkfaslhagaklsldk#define y1 aasdfasdfasdf#define yn askfhwqriuperikldjk#define j1 assdgsdgasghsf#define tm sdfjahlfasfh#define lr asgasgash#define norm asdfasdgasdgsd#define have adsgagshdshfhds#define ends asdgahhfdsfshdshfd#define eps 1e-11#define M_PI 3.141592653589793#define bs 1000000007#define bsize 512#define ldouble long doubleusing namespace std;long long INF = 1e9;const int N = 1200031;int tests,n;int ar[N],s[N][22];int main(){    ios_base::sync_with_stdio(0);    cin.tie(0);    cin>>n;    for (int i=1;i<=n;i++)    {        cin>>ar[i];        for (int j=0;j<20;j++)        {            s[i][j]=s[i-1][j];            if (ar[i]&(1<<j))                s[i][j]+=1;        }    }    cin>>tests;    for (;tests;--tests)    {        int a,b,c,d;        cin>>a>>c>>b>>d;        long long ans=0;        for (int bit=0;bit<20;bit++)        {            int cnt1=s[b][bit]-s[a-1][bit];            int cnt2=(b-a+1)-cnt1;            int cnt3=s[d][bit]-s[c-1][bit];            int cnt4=(d-c+1)-cnt3;            ans+=(1ll<<bit)*cnt1*cnt4+(1ll<<bit)*cnt2*cnt3;        }        cout<<ans<<"\n";    }    return 0;}`