HackerEarth Xor Rectangle problem solution YASH PAL, 31 July 2024 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;} coding problems