In this HackerEarth Rasta and The Matrix problem Rasta loves matrices. He has a 1018 × 1018 matrix. Every cell has a color, initially white.

Rasta also loves queries. He asks you to perform q queries. We have queries of two types:

1 x l r: if x = 0, then it means that you should change the color of all cells in rows l, l+1, ..., r (white to black and black to white). Otherwise (x = 1) you should do this to columns number l, l+1, ... r.

2 l r x y: You should print the number of black cells in subrectangle of this matrix, consisting of rows number l, l+1, ..., r and columns number x, x+1, ..., y.


HackerEarth Rasta and The Matrix problem solution


HackerEarth Rasta and The Matrix problem solution.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define Foreach(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
#define rof(i,a,b) for(int (i)=(a);(i) > (b); --(i))
#define rep(i, c) for(auto &(i) : (c))
#define x first
#define y second
#define pb push_back
#define PB pop_back()
#define iOS ios_base::sync_with_stdio(false)
#define sqr(a) (((a) * (a)))
#define all(a) a.begin() , a.end()
#define error(x) cerr << #x << " = " << (x) <<endl
#define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
#define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
#define coud(a,b) cout<<fixed << setprecision((b)) << (a)
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define umap unordered_map
#define double long double
typedef long long ll;
#define int ll
typedef pair<int,int>pii;
typedef vector<int> vi;
typedef complex<double> point;
template <typename T> using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> inline void smax(T &x,T y){ x = max((x), (y));}
template <class T> inline void smin(T &x,T y){ x = min((x), (y));}
struct seg{
int b, l, r;
bool lz;
seg * L, * R;
seg(){b = l = r = lz = 0; L = R = NULL;}
seg(int x, int y){l = x, r = y, b = 0, lz = 0; L = R = NULL;}
inline void le(){
if(r - l < 2 or L != NULL) return ;
int mid = (l+r)/2;
L = new seg(l, mid);
}
inline void ri(){
if(r - l < 2 or R != NULL) return ;
int mid = (l+r)/2;
R = new seg(mid, r);
}
inline void color(bool h){
if(!h)
return ;
lz = !lz;
b = r - l - b;
}
inline void shift(){
le();ri();
L -> color(lz);
R -> color(lz);
lz = false;
}
inline void upd(int x, int y){
if(x >= r or l >= y) return ;
if(x <= l && r <= y){
color(true);
return ;
}
shift();
L -> upd(x, y);
R -> upd(x, y);
b = L -> b + R -> b;
}
inline int cnt(int x, int y){
if(x >= r or l >= y) return 0;
if(x <= l && r <= y) return b;
shift();
return L -> cnt(x, y) +
R -> cnt(x, y) ;
}
};
int n;
const ll INF = 1e18 + 20;
const int mod = 1e9 + 7;
main(){
iOS;
cin >> n;
int l, r, t, x, y;
int last_ans = 0;
seg s[2];
For(i,0,2)
s[i] = seg(0LL, INF);
while(n--){
cin >> t;
if(t == 1){
cin >> x >> l >> r;
l ^= last_ans;
r ^= last_ans;
-- l;
s[x].upd(l, r);
}
else{
cin >> l >> r >> x >> y;
x ^= last_ans;
y ^= last_ans;
l ^= last_ans;
r ^= last_ans;
-- l, -- x;
int t1 = r - l, t2 = y - x;
int b1 = s[0].cnt(l, r), b2 = s[1].cnt(x, y);
int w1 = t1 - b1, w2 = t2 - b2;
b1 %= mod;
b2 %= mod;
w1 %= mod;
w2 %= mod;
int g = (1LL * b1 * w2)%mod,
f = (1LL * b2 * w1)%mod;
last_ans = (g + f)%mod;
cout << last_ans << '\n';
}
}
return 0;
}