HackerRank Quadrant Queries Problem Solution
In this post, we will solve HackerRank Quadrant Queries Problem Solution.
There are n points on a plane. Each point p[i] is described by [x[i], y[i]], where 1 ≤ i ≤n. There are three types of queries needed:
- X i j Reflect all points in the inclusive range between points p[i] and p[j] along the x- axis.
- Yij Reflect all points in the inclusive range between points p[i] and pl] along the y-
axis. - Cij Count the number of points in the inclusive range between points p[i] and p[j] in each of the 4 quadrants. Then print a single line of four space-separated integers describing the respective numbers of points in the first, second, third, and fourth quadrants in that order
Given a set of n points and q queries, perform each query in order. For example, given points p = [(1, 1), (-1,-1)] and
queries = [‘X 1 2’, ‘C 1 2’, ‘Y 1 1 C 1 2’]. Initially the points are in quadrants 1 and 3. The first query says to reflect points with indices from 1 to 2 along the -axis. After the query, p = [(1,-1), (-1, 1)] and quadrants are 4 and 2. The next query prints the number of points in each quadrant: 0 1 0 1. The third query says to reflect the point with index 1 to 1 along the y-axis, so now p= [(-1,-1), (-1, 1)]. The points now lie in quadrants 3 and 2, so the fourth query output is @ 1 1 0.
Note: Points may sometimes share the same coordinates.
Function Description
Complete the quadrants function in the editor below. It should print the results of each C type query on a new line.
quadrants has the following parameters:
- p[p[1]…p[n]]; a 2-dimensional array of integers where each element p[i] contains two
integers [1] and y[i] - queries[queries[1]…queries[n]: an array of strings
Input Format
The first line contains a single integer, n, that denotes the number of points.
Each line i of the n subsequent lines contains two space-separated integers that describe the respective [2] and y[i] values for point p[i].
The next line contains a single integer, q, that denotes the number of queries.
Each of the a subsequent lines contains three space-separated values that describe a query in one of the three forms defined above.
Output Format
For each query of type C i j, print four space-separated integers that describe the number of points having indices in the inclusive range between i and j in the first, second, third, and fourth graph quadrants in that order.
Sample Input
4
1 1
-1 1
-1 -1
1 -1
5
C 1 4
X 2 4
C 3 4
Y 1 2
C 1 3
Sample Output
1 1 1 1
1 1 0 0
0 2 0 1Explanation
Initially, p = [[1, 1], -1, 1, -1, -1], [1, 1]] so there is one point in each of the four quadrants. The first query results in printing 1 1 1 1.
The second query, X 2 4, reflects the points in the inclusive range between indices 2 and 4 along the x-axis. Now p = [[1,1],-1,-1], [1, 1], [1, 1]].
The query C 3 4 requires that the number of points considering p[3] through p[4] be printed: 1 1 0 0
The third query, Y 1 2 requires reflection of p[1]p[2] along the y-axis. Now p = [[1, 1], [1, 1], [−1, 1], [1, 1]].
The last query, C 1 3 requires that the number of points considering p[1] through p[3] be printed: 0 2 0 1
Quadrant Queries C Solution
#include<stdio.h>
#define g getchar_unlocked()
struct abc
{
int f,s,t,ft;
};
typedef struct abc abc;
abc st[500004]={0};
int x[100002],y[100002];
char ii[500004][2]={0};
update(int node,int beg,int end,int i,int j,int type)
{
int mid,nnode,temp;
if(i>end || j<beg)
return;
if(i<=beg && end<=j)
{
if(type==1)
{
ii[node][0]=1-ii[node][0];
st[node].f=(st[node].f+st[node].ft)-(st[node].ft=st[node].f);
st[node].s=(st[node].s+st[node].t)-(st[node].t=st[node].s);
return(0);
}
else
{
ii[node][1]=1-ii[node][1];
st[node].f=(st[node].f+st[node].s)-(st[node].s=st[node].f);
st[node].t=(st[node].t+st[node].ft)-(st[node].ft=st[node].t);
return(0);
}
}
mid=(beg+end)/2;
nnode=(node)<<1;
update(nnode,beg,mid,i,j,type);
update(nnode+1,mid+1,end,i,j,type);
st[node].f=st[nnode].f+st[nnode+1].f;
st[node].s=st[nnode].s+st[nnode+1].s;
st[node].t=st[nnode].t+st[nnode+1].t;
st[node].ft=st[nnode].ft+st[nnode+1].ft;
if(ii[node][0]==1)
{
st[node].f=(st[node].f+st[node].ft)-(st[node].ft=st[node].f);
st[node].s=(st[node].s+st[node].t)-(st[node].t=st[node].s);
}
if(ii[node][1]==1)
{
st[node].f=(st[node].f+st[node].s)-(st[node].s=st[node].f);
st[node].t=(st[node].t+st[node].ft)-(st[node].ft=st[node].t);
}
return(0);
}
abc query(int node,int beg,int end,int xt,int yt,int i,int j)
{
int mid,nnode,t1,t2;
abc ans={0};
if(i>end || j<beg)
return(ans);
if(i<=beg && end<=j)
{
abc ans=st[node];
if(xt==1)
{
ans.f=(ans.f+ans.ft)-(ans.ft=ans.f);
ans.s=(ans.s+ans.t)-(ans.t=ans.s);
}
if(yt==1)
{
ans.f=(ans.f+ans.s)-(ans.s=ans.f);
ans.t=(ans.t+ans.ft)-(ans.ft=ans.t);
}
return(ans);
}
abc ans1,ans2;
mid=(beg+end)/2;
nnode=2*node;
t1=(xt+ii[node][0])%2;
t2=(yt+ii[node][1])%2;
ans1=query(nnode,beg,mid,t1,t2,i,j);
ans2=query(nnode+1,mid+1,end,t1,t2,i,j);
ans1.f+=ans2.f;ans1.s+=ans2.s;ans1.t+=ans2.t;ans1.ft+=ans2.ft;
return(ans1);
}
init(int node,int beg,int end)
{
int nnode,mid;
if(beg==end)
{
if(x[beg]>0)
{
if(y[beg]>0)
(st[node].f)++;
else (st[node].ft)++;
}
else
{
if(y[beg]>0)
(st[node].s)++;
else (st[node].t)++;
}
return;
}
nnode=(node)<<1;
mid=(beg+end)/2;
init(nnode,beg,mid);
init(nnode+1,mid+1,end);
st[node].f=st[nnode].f+st[nnode+1].f;
st[node].s=st[nnode].s+st[nnode+1].s;
st[node].t=st[nnode].t+st[nnode+1].t;
st[node].ft=st[nnode].ft+st[nnode+1].ft;
return(0);
}
scan()
{
int t=0,m=1;
char c;
c=g;
while((c<'0' || c>'9') && c!='-')
c=g;
if(c=='-')
{
m=-1;
c=g;
}
while(c>='0' && c<='9')
{
t=(t<<3)+(t<<1)+c-'0';
c=g;
}
return(t*m);
}
int main()
{
int n,q,a,b,i;
char tp;
abc ans;
n=scan();
for(i=0;i<n;i++)
{x[i]=scan();y[i]=scan();}
init(1,0,n-1);
q=scan();
while(q--)
{
tp=getchar();a=scan();b=scan();
if(tp=='X')
update(1,0,n-1,a-1,b-1,1);
else if(tp=='Y')
update(1,0,n-1,a-1,b-1,2);
else {
ans=query(1,0,n-1,0,0,a-1,b-1);
printf("%d %d %d %d\n",ans.f,ans.s,ans.t,ans.ft);
}
}
return(0);
}Quadrant Queries C++ Solution
#include <bits/stdc++.h>
using namespace std;
int N, Q;
int X[100010];
int Y[100010];
int L, R;
char type;
struct Node
{
int count[4] = {0};
int x_flip = 0;
int y_flip = 0;
Node() {}
Node(int a, int b, int c, int d)
{
count[0] = a;
count[1] = b;
count[2] = c;
count[3] = d;
}
void FlipX()
{
swap(count[0], count[3]);
swap(count[1], count[2]);
}
void FlipY()
{
swap(count[0], count[1]);
swap(count[2], count[3]);
}
};
Node tree[1000010];
Node GetNode(int x, int y)
{
Node res;
if(y > 0)
{
res.count[(x < 0)]++;
}
else
{
res.count[2 + (x > 0)]++;
}
return res;
}
Node Combine(Node a, Node b)
{
Node res;
for(int i = 0; i < 4; i++)
{
res.count[i] = a.count[i] + b.count[i];
}
return res;
}
Node Reflect(Node node)
{
Node res;
vector<pair<int, int>> indices =
(type == 'X') ? vector<pair<int, int>>({{0, 3}, {1, 2}, {2, 1}, {3, 0}})
: vector<pair<int, int>>({{0, 1}, {1, 0}, {2, 3}, {3, 2}});
for(auto it : indices)
{
res.count[it.first] = node.count[it.second];
}
return res;
}
void Reflect(int node, int low, int high, int L, int R)
{
if(low > high || high < L || low > R)
{
return;
}
// if(low == high)
if(low >= L && high <= R)
{
// tree[node] = Reflect(tree[node]);
tree[node].x_flip ^= (type == 'X');
tree[node].y_flip ^= (type == 'Y');
if(type == 'X') tree[node].FlipX();
if(type == 'Y') tree[node].FlipY();
return;
}
int mid = (low + high) / 2;
Reflect(node * 2 + 1, low, mid, L, R);
Reflect(node * 2 + 2, mid + 1, high, L, R);
int x_flip = tree[node].x_flip;
int y_flip = tree[node].y_flip;
tree[node] = Combine(tree[node * 2 + 1], tree[node * 2 + 2]);
tree[node].x_flip = x_flip;
tree[node].y_flip = y_flip;
// if(type == 'X') tree[node].FlipX();
// if(type == 'Y') tree[node].FlipY();
if(tree[node].x_flip) tree[node].FlipX();
if(tree[node].y_flip) tree[node].FlipY();
}
void Build(int node, int low, int high)
{
if(low == high)
{
tree[node] = GetNode(X[low], Y[low]);
return;
}
int mid = (low + high) / 2;
Build(node * 2 + 1, low, mid);
Build(node * 2 + 2, mid + 1, high);
tree[node] = Combine(tree[node * 2 + 1], tree[node * 2 + 2]);
}
Node Count(int node, int low, int high, int L, int R, int flip_x = 0, int flip_y = 0)
{
if(low > high || high < L || low > R)
{
return Node(0,0,0,0);
}
if(low >= L && high <= R)
{
auto res = tree[node];
if(flip_x) res.FlipX();
if(flip_y) res.FlipY();
return res;
}
int mid = (low + high) / 2;
// if(R <= mid)
// {
// return Count(node * 2 + 1, low, mid, L, R);
// }
// else if(L > mid)
// {
// return Count(node * 2 + 2, mid + 1, high, L, R);
// }
// Node a = Count(node * 2 + 1, low, mid, L, min(R, mid));
// Node b = Count(node * 2 + 2, mid + 1, high, max(mid + 1, L), R);
flip_x ^= tree[node].x_flip;
flip_y ^= tree[node].y_flip;
Node a = Count(node * 2 + 1, low, mid, L, R, flip_x, flip_y);
Node b = Count(node * 2 + 2, mid + 1, high, L, R, flip_x, flip_y);
return Combine(a, b);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for(int i = 0; i < N; i++)
{
cin >> X[i] >> Y[i];
}
Build(0, 0, N - 1);
cin >> Q;
for(int i = 0; i < Q; i++)
{
cin >> type >> L >> R;
L--; R--;
switch(type)
{
case 'X':
{
Reflect(0, 0, N - 1, L, R);
break;
}
case 'Y':
{
Reflect(0, 0, N - 1, L, R);
break;
}
case 'C':
{
Node ans = Count(0, 0, N - 1, L, R);
for(int i = 0; i < 4; i++)
{
cout << ans.count[i] << " ";
}
cout << "\n";
break;
}
}
}
return 0;
}Quadrant Queries C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
namespace Algorithms.hackerrank
{
public class Solution
{
private enum Quadrant
{
First = 0,
Second,
Third,
Forth
}
private enum QueryType
{
X = 0, // reflection about x-axis
Y, // reflection about y-axis,
XY,
None,
C
}
private sealed class Segment
{
public QueryType Type { get; set; }
public int Start { get; private set; }
public int End { get; private set; }
private int[] count = new int[4];
private static QueryType[,] tb = new QueryType[4, 4];
public int[] Count { get { return this.count; } }
public Segment(int start, int end)
{
this.Start = start;
this.End = end;
this.Type = QueryType.None;
}
public int this[int i]
{
get { return count[i]; }
set { count[i] = value; }
}
private void Swap(Quadrant i, Quadrant j)
{
int x = count[(int)i];
count[(int)i] = count[(int)j];
count[(int)j] = x;
}
public void Transform()
{
switch (Type)
{
case QueryType.X:
Swap(Quadrant.First, Quadrant.Forth);
Swap(Quadrant.Second, Quadrant.Third);
break;
case QueryType.Y:
Swap(Quadrant.First, Quadrant.Second);
Swap(Quadrant.Third, Quadrant.Forth);
break;
case QueryType.XY:
Swap(Quadrant.First, Quadrant.Third);
Swap(Quadrant.Second, Quadrant.Forth);
break;
}
Type = QueryType.None;
}
static Segment()
{
for (QueryType t1 = QueryType.X; t1 <= QueryType.None; t1++)
{
for (QueryType t2 = QueryType.X; t2 <= QueryType.None; t2++)
{
tb[(int)t1, (int)t2] = Transform(t1, t2);
}
}
}
public void Transform(QueryType type)
{
Type = tb[(int)type, (int)Type];
}
private static QueryType Transform(QueryType t1, QueryType t2)
{
if (t1 == QueryType.X)
{
switch (t2)
{
case QueryType.X: return QueryType.None;
case QueryType.Y: return QueryType.XY;
case QueryType.XY: return QueryType.Y;
case QueryType.None: return QueryType.X;
}
}
else if (t1 == QueryType.Y)
{
switch (t2)
{
case QueryType.X: return QueryType.XY;
case QueryType.Y: return QueryType.None;
case QueryType.XY: return QueryType.X;
case QueryType.None: return QueryType.Y;
}
}
else if (t1 == QueryType.XY)
{
switch (t2)
{
case QueryType.X: return QueryType.Y;
case QueryType.Y: return QueryType.X;
case QueryType.XY: return QueryType.None;
case QueryType.None: return QueryType.XY;
}
}
return t2;
}
public override string ToString()
{
return string.Format("{0} - {1} : {2} {3} {4} {5} : {6}", Start, End, count[0], count[1], count[2], count[3], Type);
}
}
private sealed class SegmentTree
{
public delegate void Count(int[] count, int index);
private Segment[] segments;
private Count fn;
public SegmentTree(int N, Count fn)
{
segments = new Segment[270000]; // for this particular question, it can't go beyond this size
this.fn = fn;
Initialize(0, 1, N);
}
private void Initialize(int index, int start, int end)
{
Segment seg = new Segment(start, end);
segments[index] = seg;
if (start == end)
{
fn(seg.Count, start);
return;
}
int leftIdx = GetLeftChildIndex(index);
int rightIdx = GetRightChildIndex(index);
Initialize(leftIdx, start, (start + end) / 2);
Initialize(rightIdx, (start + end) / 2 + 1, end);
Segment left = segments[leftIdx];
Segment right = segments[rightIdx];
for (int i = 0; i < 4; i++)
{
seg[i] = left[i] + right[i];
}
}
public void Update(int start, int end, QueryType type)
{
Update(0, start, end, type);
}
private void Update(int index, int start, int end, QueryType type)
{
var seg = segments[index];
if (seg.Start == seg.End)
{
// elementary segment, at leaf
seg.Transform(type);
seg.Transform();
return;
}
int leftIdx = GetLeftChildIndex(index);
int rightIdx = GetRightChildIndex(index);
var left = segments[leftIdx];
var right = segments[rightIdx];
if (seg.Start == start && seg.End == end)
{
// current segment covers the exact range, stops here, push update to both children
seg.Transform(type);
left.Transform(seg.Type);
right.Transform(seg.Type);
seg.Transform();
return;
}
// propagate the transformation to both children
left.Transform(seg.Type);
right.Transform(seg.Type);
seg.Type = QueryType.None;
if (start <= left.End)
{
Update(leftIdx, start, Math.Min(end, left.End), type);
}
else
{
Update(leftIdx, left.Start, left.End, QueryType.None);
}
if (end >= right.Start)
{
Update(rightIdx, Math.Max(start, right.Start), end, type);
}
else
{
Update(rightIdx, right.Start, right.End, QueryType.None);
}
for (int i = 0; i < 4; i++)
{
seg[i] = left[i] + right[i];
}
}
public int[] Query(int start, int end)
{
int[] count = new int[4];
Query(0, start, end, count);
return count;
}
private void Query(int index, int start, int end, int[] count)
{
Segment seg = segments[index];
if (seg.Type != QueryType.None)
{
Update(index, start, end, QueryType.None);
}
if (seg.Start == start && seg.End == end)
{
for (int i = 0; i < 4; i++)
{
count[i] += seg[i];
}
return;
}
int leftIdx = GetLeftChildIndex(index);
int rightIdx = GetRightChildIndex(index);
var left = segments[leftIdx];
var right = segments[rightIdx];
if (start <= left.End) Query(leftIdx, start, Math.Min(end, left.End), count);
if (end >= right.Start) Query(rightIdx, Math.Max(start, right.Start), end, count);
}
private int GetRightChildIndex(int i) { return 2 * i + 1; }
private int GetLeftChildIndex(int i) { return 2 * i + 2; }
}
private Quadrant FindQuadrant(int x, int y)
{
if (x > 0 && y > 0) return Quadrant.First;
if (x < 0 && y < 0) return Quadrant.Third;
if (x > 0) return Quadrant.Forth;
return Quadrant.Second;
}
private void Solve(int start, int end, QueryType type)
{
if (type == QueryType.C)
{
int[] count = tree.Query(start, end);
Console.WriteLine(string.Format("{0} {1} {2} {3}", count[0], count[1], count[2], count[3]));
}
else
{
tree.Update(start, end, type);
}
}
private void Count(int[] count, int index)
{
string[] ln = rd.ReadLine().Split(' ');
Quadrant q = FindQuadrant(int.Parse(ln[0]), int.Parse(ln[1]));
count[(int)q] = 1;
}
private TextReader rd;
private SegmentTree tree;
private int N = 0;
private void Run(TextReader rd)
{
N = int.Parse(rd.ReadLine());
this.rd = rd;
tree = new SegmentTree(N, Count);
int Q = int.Parse(rd.ReadLine());
for (; Q > 0; Q--)
{
string[] ln = rd.ReadLine().Split(' ');
var t = ln[0];
QueryType type = QueryType.C;
if (t == "X") type = QueryType.X;
else if (t == "Y") type = QueryType.Y;
Solve(int.Parse(ln[1]), int.Parse(ln[2]), type);
}
//Console.ReadKey();
}
public static void Main(string[] args)
{
TextReader rd = Console.In;
if (args.Length != 0) rd = new StreamReader(new FileStream(args[0], FileMode.Open, FileAccess.Read));
new Solution().Run(rd);
}
}
}Quadrant Queries Java Solution
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
private static final int[] BC = new int[1<<16];
public static void main(String[] argv) throws Exception {
prep();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line1 = br.readLine();
int N = Integer.parseInt(line1);
ArrayList<String> dump = new ArrayList<String>(100000);
int[] x = new int[N/32+1];
int[] y = new int[N/32+1];
long rs = System.currentTimeMillis();
for(int i=0;i<N;i++){
String line2 = br.readLine();
String[] tmp2 = line2.split(" ");
if(tmp2[0].charAt(0) != '-') x[i/32] |= 1<< i%32;
if(tmp2[1].charAt(0) != '-') y[i/32] |= 1<< i%32;
}
long re = System.currentTimeMillis();
String line3 = br.readLine();
int Q = Integer.parseInt(line3);
boolean wasC = false;
int[] tmp1 = new int[N/32+1];
int[] tmp24= new int[N/32+1];
int[] tmp2 = new int[N/32+1];
int[] cnt1 = new int[N/32+1];
int[] cnt24= new int[N/32+1];
int[] cnt2 = new int[N/32+1];
long ws = System.currentTimeMillis();
for(int i=0;i<Q;i++){
String line4 = br.readLine();
String[] tmp4 = line4.split(" ");
int sindex = Integer.parseInt(tmp4[1]);
int eindex = Integer.parseInt(tmp4[2]);
int sm = (sindex-1)%32;
int sn = (sindex-1)/32;
int em = eindex%32;
int en = eindex/32;
int es = eindex-sindex+1;
if(tmp4[0].equals("X")) {
if(sn == en){
int mask = ((1<<(es))-1)<<(sm);
y[en] ^= mask;
}else{
int mask = -1;
int fmask = mask<<(sm);
int emask = (1<<(em))-1;
y[sn] ^= fmask;
for(int j=sn+1;j<en;j++) y[j] ^= mask;
y[en] ^= emask;
}
wasC = false;
}else if(tmp4[0].equals("Y")) {
if(sn == en){
int mask = ((1<<(es))-1)<<(sm);
x[en] ^= mask;
}else{
int mask = -1;
int fmask = mask<<(sm);
int emask = (1<<(em))-1;
x[sn] ^= fmask;
for(int j=sn+1;j<en;j++) x[j] ^= mask;
x[en] ^= emask;
}
wasC = false;
}else{
/*
if(!wasC || wasC){
for(int j=0;j<x.length;j++) {
tmp1[j] = x[j] & y[j];
tmp24[j] = x[j] ^ y[j];
tmp2[j] = tmp24[j] & y[j];
cnt1[j] = bitCount(tmp1[j]);
cnt24[j]= bitCount(tmp24[j]);
cnt2[j] = bitCount(tmp2[j]);
}
}
*/
int maskes = ((1<<(es))-1)<<(sm);
int maskall = -1;
int fmask = maskall<<(sm);
int emask = (1<<(em))-1;
// 1st quadrant x bit: 1, y bit: 1 (x & y)
int c1 = 0;
if(sn == en){
c1 += bitCount(x[en] & y[en] & maskes);
}else{
c1 += bitCount(x[sn] & y[sn] & fmask);
for(int j=sn+1;j<en;j++) c1 += bitCount(x[j] & y[j]);
c1 += bitCount(x[en] & y[en] & emask);
}
// 2nd quadrant x bit: 0, y bit: 1
// 4th quadrant x bit: 1, y bit: 0
// x xor y = c2 + c4
// (x xor y) & y = c2
int c24 = 0;
int c2 = 0;
if(sn == en){
int t2 = (x[en] ^ y[en]) & maskes;
c24 += bitCount(t2);
c2 += bitCount(t2 & y[en]);
}else{
int t2 = (x[sn] ^ y[sn]) & fmask;
c24 += bitCount(t2);
c2 += bitCount(t2 & y[sn]);
for(int j=sn+1;j<en;j++) {
t2 = x[j] ^ y[j];
c24 += bitCount(t2);
c2 += bitCount(t2 & y[j]);
}
t2 = (x[en] ^ y[en]) & emask;
c24 += bitCount(t2);
c2 += bitCount(t2 & y[en]);
}
int c4 = c24 - c2;
// 3rd quadrant x bit: 0, y bit: 0 (total - c1 - c2 - c4)
int c3 = eindex - sindex + 1 - c1 - c2 - c4;
dump.add(c1+" "+c2+" "+c3+" "+c4);
//System.out.println(c1+" "+c2+" "+c3+" "+c4);
wasC = true;
}
}
long we = System.currentTimeMillis();
for(int i=0;i<dump.size();i++) System.out.println(dump.get(i));
br.close();
//System.out.println("R:"+(re-rs));
//System.out.println("W:"+(we-ws));
}
private static void prep() {
int max = 1<<16;
int step1 = 1<<8;
for(int i=0;i<step1;i++) BC[i] = Integer.bitCount(i);
for(int i=step1;i<max;i++){
BC[i] = BC[i&0xFF] + BC[(i>>8)&0xFF];
}
}
private static int bitCount(int i){
return BC[i&0xFFFF] + BC[(i>>16)&0xFFFF];
}
}Quadrant Queries JavaScript Solution
'use strict';
var SZ = 30;
var MASK = 0;
for (var i = 0, j = 1; i < SZ; i++, j *= 2) { MASK |= j; }
function Quadrant(N) {
this.N = N;
this.len = Math.floor(N / SZ) + ((N % SZ == 0) ? 0 : 1);
this.quadrants0 = new Array(this.len);
this.quadrants1 = new Array(this.len);
this.quadrants2 = new Array(this.len);
this.quadrants3 = new Array(this.len);
this.counts0 = new Array(this.len);
this.counts1 = new Array(this.len);
this.counts2 = new Array(this.len);
this.counts3 = new Array(this.len);
for (var i = 0; i < this.len; i++) {
this.quadrants0[i] = 0;
this.quadrants1[i] = 0;
this.quadrants2[i] = 0;
this.quadrants3[i] = 0;
this.counts0[i] = 0;
this.counts1[i] = 0;
this.counts2[i] = 0;
this.counts3[i] = 0;
}
this.iMasks = [];
this.jMasks = [];
for (var k = 0; k < SZ; k++) {
this.iMasks[k] = this.getMask(k, SZ - 1); // (MASK >> (SZ - (i % SZ))) ^ MASK
this.jMasks[k] = this.getMask(0, k); // (MASK >> (SZ - 1 - (j % SZ)))
}
}
Quadrant.prototype.init = function(points) {
for (var i = 0; i < this.N; i++) {
var d = Math.floor(i / SZ);
var bit = 1 << (i % SZ);
var pt = points[i];
var x = pt[0];
var y = pt[1]
var q = (
((x >= 0 && y >= 0) ? 0 : 0)
+ ((x < 0 && y >= 0) ? 1 : 0)
+ ((x < 0 && y < 0) ? 2 : 0)
+ ((x >= 0 && y < 0) ? 3 : 0)
);
if (q == 0) {
this.quadrants0[d] |= bit;
this.counts0[d]++;
} else if (q == 1) {
this.quadrants1[d] |= bit;
this.counts1[d]++;
} else if (q == 2) {
this.quadrants2[d] |= bit;
this.counts2[d]++;
} else if (q == 3) {
this.quadrants3[d] |= bit;
this.counts3[d]++;
} else {}
}
};
Quadrant.prototype.recount = function(idx) {
var q0 = this.quadrants0[idx];
var q1 = this.quadrants1[idx];
var q2 = this.quadrants2[idx];
var q3 = this.quadrants3[idx];
var count0 = 0;
var count1 = 0;
var count2 = 0;
var count3 = 0;
while (q0 > 0) { if (q0 & 1) { count0++; } q0 >>= 1; }
while (q1 > 0) { if (q1 & 1) { count1++; } q1 >>= 1; }
while (q2 > 0) { if (q2 & 1) { count2++; } q2 >>= 1; }
while (q3 > 0) { if (q3 & 1) { count3++; } q3 >>= 1; }
this.counts0[idx] = count0;
this.counts1[idx] = count1;
this.counts2[idx] = count2;
this.counts3[idx] = count3;
}
Quadrant.prototype.maskSwapY = function(idx, mask) {
var q0 = this.quadrants0[idx] & mask;
var q1 = this.quadrants1[idx] & mask;
var q2 = this.quadrants2[idx] & mask;
var q3 = this.quadrants3[idx] & mask;
this.quadrants0[idx] ^= q0;
this.quadrants1[idx] ^= q1;
this.quadrants2[idx] ^= q2;
this.quadrants3[idx] ^= q3;
this.quadrants0[idx] |= q3;
this.quadrants1[idx] |= q2;
this.quadrants2[idx] |= q1;
this.quadrants3[idx] |= q0;
this.recount(idx);
}
Quadrant.prototype.getMask = function(i, j) {
return (MASK >> (SZ - (i % SZ))) ^ (MASK >> (SZ - 1 - (j % SZ)));
};
Quadrant.prototype.maskSwapX = function(idx, mask) {
var q0 = this.quadrants0[idx] & mask;
var q1 = this.quadrants1[idx] & mask;
var q2 = this.quadrants2[idx] & mask;
var q3 = this.quadrants3[idx] & mask;
this.quadrants0[idx] ^= q0;
this.quadrants1[idx] ^= q1;
this.quadrants2[idx] ^= q2;
this.quadrants3[idx] ^= q3;
this.quadrants0[idx] |= q1;
this.quadrants1[idx] |= q0;
this.quadrants2[idx] |= q3;
this.quadrants3[idx] |= q2;
this.recount(idx);
};
Quadrant.prototype.swapY = function(i, j) {
var i0 = Math.floor(i / SZ);
var j0 = Math.floor(j / SZ);
var i1 = i0 + ((i % SZ != 0) ? 1 : 0);
var j1 = j0 - ((((j + 1) % SZ) != 0) ? 1 : 0);
if (i0 == j0) {
this.maskSwapY(i0, this.getMask(i, j));
return;
}
if (i0 < i1) { this.maskSwapY(i0, this.iMasks[i % SZ]); }
if (j0 > j1) { this.maskSwapY(j0, this.jMasks[j % SZ]); }
for (var idx = i1; idx <= j1; idx++) {
var q0 = this.quadrants0[idx];
var q1 = this.quadrants1[idx];
var q2 = this.quadrants2[idx];
var q3 = this.quadrants3[idx];
this.quadrants0[idx] = q3;
this.quadrants1[idx] = q2;
this.quadrants2[idx] = q1;
this.quadrants3[idx] = q0;
var c0 = this.counts0[idx];
var c1 = this.counts1[idx];
var c2 = this.counts2[idx];
var c3 = this.counts3[idx];
this.counts0[idx] = c3;
this.counts1[idx] = c2;
this.counts2[idx] = c1;
this.counts3[idx] = c0;
}
}
Quadrant.prototype.swapX = function(i, j) {
var i0 = Math.floor(i / SZ);
var j0 = Math.floor(j / SZ);
var i1 = i0 + ((i % SZ != 0) ? 1 : 0);
var j1 = j0 - ((((j + 1) % SZ) != 0) ? 1 : 0);
if (i0 == j0) {
this.maskSwapX(i0, this.getMask(i, j));
return;
}
if (i0 < i1) { this.maskSwapX(i0, this.iMasks[i % SZ]); }
if (j0 > j1) { this.maskSwapX(j0, this.jMasks[j % SZ]); }
for (var idx = i1; idx <= j1; idx++) {
var q0 = this.quadrants0[idx];
var q1 = this.quadrants1[idx];
var q2 = this.quadrants2[idx];
var q3 = this.quadrants3[idx];
this.quadrants0[idx] = q1;
this.quadrants1[idx] = q0;
this.quadrants2[idx] = q3;
this.quadrants3[idx] = q2;
var c0 = this.counts0[idx];
var c1 = this.counts1[idx];
var c2 = this.counts2[idx];
var c3 = this.counts3[idx];
this.counts0[idx] = c1;
this.counts1[idx] = c0;
this.counts2[idx] = c3;
this.counts3[idx] = c2;
}
}
Quadrant.prototype.maskCount = function(idx, mask) {
var c0 = 0, c1 = 0, c2 = 0, c3 = 0;
var q0 = this.quadrants0[idx] & mask;
var q1 = this.quadrants1[idx] & mask;
var q2 = this.quadrants2[idx] & mask;
var q3 = this.quadrants3[idx] & mask;
while (q0 > 0) { if (q0 & 1) { c0++; } q0 >>= 1; }
while (q1 > 0) { if (q1 & 1) { c1++; } q1 >>= 1; }
while (q2 > 0) { if (q2 & 1) { c2++; } q2 >>= 1; }
while (q3 > 0) { if (q3 & 1) { c3++; } q3 >>= 1; }
return [c0, c1, c2, c3];
};
Quadrant.prototype.count = function(i, j) {
var i0 = Math.floor(i / SZ);
var j0 = Math.floor(j / SZ);
var i1 = i0 + ((i % SZ != 0) ? 1 : 0);
var j1 = j0 - ((((j + 1) % SZ) != 0) ? 1 : 0);
var count0 = 0, count1 = 0, count2 = 0, count3 = 0;
if (i0 == j0) {
var a = this.maskCount(i0, this.getMask(i, j));
count0 += a[0]; count1 += a[1]; count2 += a[2]; count3 += a[3];
return (count0 + ' ' + count1 + ' ' + count2 + ' ' + count3);
}
if (i0 < i1) {
var a = this.maskCount(i0, this.iMasks[i % SZ]);
count0 += a[0]; count1 += a[1]; count2 += a[2]; count3 += a[3];
}
if (j0 > j1) {
var a = this.maskCount(j0, this.jMasks[j % SZ]);
count0 += a[0]; count1 += a[1]; count2 += a[2]; count3 += a[3];
}
for (var k = i1; k <= j1; k++) {
count0 += this.counts0[k];
count1 += this.counts1[k];
count2 += this.counts2[k];
count3 += this.counts3[k];
}
return (count0 + ' ' + count1 + ' ' + count2 + ' ' + count3);
}
function processData(input) {
var parse_fun = function (s) { return parseInt(s, 10); };
var lines = input.split('\n');
var N = parse_fun(lines.shift());
var points = lines.splice(0, N).map(function (s) {
return s.split(' ').map(parse_fun);
});
var quadrant = new Quadrant(N);
quadrant.init(points);
var Q = parse_fun(lines.shift());
var queries = lines.splice(0, Q);
var res = [];
for (var q = 0; q < Q; q++) {
var params = queries[q].split(' ');
var op = params[0];
var i = parse_fun(params[1]) - 1;
var j = parse_fun(params[2]) - 1;
if (op == 'X') {
quadrant.swapY(i, j);
} else if (op == 'Y') {
quadrant.swapX(i, j);
} else if (op == 'C') {
res.push(quadrant.count(i, j));
} else {}
}
process.stdout.write(res.join('\n'));
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
var _input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});Quadrant Queries Python Solution
#!/usr/env python
import bisect
from math import sqrt
import optparse
import sys
from random import randint as rand
_Rx = [3, 2, 1, 0]
_Ry = [1, 0, 3, 2]
def create_test(N, Q, fp):
r = [(rand(-2, 2), rand(-2, 2)) for i in range(N)]
print(N, file = fp)
for ri in r:
print('%d %d' % ri, file = fp)
ops = [ "X", "Y", "C" ]
queries = [(ops[rand(0, 2)], rand(1, N), rand(1, N)) for q in range(Q)]
print(Q, file = fp)
for op, i, j in queries:
if i > j:
i, j = j, i
print('%1s %d %d' % (op, i, j), file = fp)
return [r, queries]
def quadrant(x, y):
'''
Return the quadrant the point r is in.
'''
if x > 0:
if y > 0: return 0
else: return 3
else:
if y > 0: return 1
else: return 2
def getInput(f, shift = -1):
'''
The first line contains N, the number of points. N lines follow.
The ith line contains xi and yi separated by a space. The next line
contains Q the number of queries. The next Q lines contain one query
each, of one of the above forms. All indices are 1 indexed.
Return the points r and the queries q, in [r, q]
'''
l = f.readline().strip()
n = int(l)
r = []
for i in range(n):
l = f.readline().strip()
x, y = l.split()
r.append([int(x), int(y)])
l = f.readline().strip()
Q = int(l)
queries = []
for k in range(Q):
l = f.readline().strip()
op, i, j = l.split()
queries.append((op, int(i) + shift, int(j) + shift))
return [r, queries]
class QuadrantBook:
'''
A data structure to facilitate the processing of quadrant queries.
'''
def __init__(self, r, factor = 32):
N = len(r)
self.blocksize = int(sqrt(factor * N))
nblocks = (N - 1) // self.blocksize + 1
# self.inq[b][q] is the list of points in the quadrant q with indices
# between b L and (b+1)L, where L is the blocksize.
self.inq = [[[] for q in range(4) ] for b in range(nblocks)]
for i, ri in enumerate(r):
b = self.getBlock(i)
q = quadrant(ri[0], ri[1])
self.inq[b][q].append(i)
def countInQuadrants( self, i, j):
'''
Count the number of points in each quadrant with indices between i and j,
inclusive.
'''
bi = self.getBlock(i)
bj = self.getBlock(j)
cq = [0] * 4
if bi == bj:
for q, idx in enumerate(self.inq[bi]):
ki, kj = getIndex(idx, i, j)
cq[q] = kj - ki
return cq
else:
for q in range(4):
ni = self.inq[bi][q]
nj = self.inq[bj][q]
ki = bisect.bisect_left(ni, i)
kj = bisect.bisect_right(nj, j)
cq[q] = len(ni) - ki
for nb in self.inq[bi + 1: bj]:
cq[q] += len(nb[q])
cq[q] += kj
return cq
def reflect( self, i, j, axis):
'''
Update the list of points in each quadrant after reflection along the
given axis.
'''
if axis == "X":
R = _Rx
W = [(0, 3), (1, 2)]
else:
R = _Ry
W = [(0, 1), (2, 3)]
bi = self.getBlock( i)
bj = self.getBlock( j)
if bi == bj:
self.reflectInBlock( i, j, bi, R)
else:
ni = self.inq[bi]
kiq = [bisect.bisect_left(idx, i) for idx in ni]
rfxi = [ni[q][ki:] for q, ki in enumerate(kiq)]
for q, ki in enumerate(kiq):
ni[q] = ni[q][:ki] + rfxi[R[q]]
nj = self.inq[bj]
kjq = [bisect.bisect_right( idx, j) for idx in nj]
rfxj = [nj[q][:kj] for q, kj in enumerate(kjq)]
for q, kj in enumerate( kjq):
nj[q] = rfxj[R[q]] + nj[q][kj:]
for nb in self.inq[bi + 1: bj]:
for w1, w2 in W:
nb[w1], nb[w2] = nb[w2], nb[w1]
def getBlock( self, i ):
'''
Get the block index for point i.
'''
return i // self.blocksize
def reflectInBlock(self, i, j, b, R):
'''
Update the list of points in each quadrant after reflection along the
given axis, assuming that i and j are in the same block b.
'''
nb = self.inq[b]
kij = [getIndex( idx, i, j) for idx in nb]
rf = [nb[q][ki: kj] for q, (ki, kj) in enumerate(kij)]
for q, (ki, kj) in enumerate(kij):
nb[q] = nb[q][:ki] + rf[R[q]] + nb[q][kj:]
def getIndex( lst, i, j):
'''
In the sorted list, find ki such that lst[ki-1]<i<=lst[ki], and kj such
that lst[kj]<=j<lst[kj+1]. If i<lst[0], ki=0; if j>lst[-1], kj=len(lst).
This convention splices the list at the right places.
@param i<=j
'''
ki = bisect.bisect_left(lst, i)
kj = bisect.bisect_right(lst, j, ki)
return [ki, kj]
def processQueries(r, queries, factor = 32):
qbook = QuadrantBook(r, factor)
for op, i, j in queries:
if op.upper() == 'C':
cq = qbook.countInQuadrants(i, j)
print('%d %d %d %d' % tuple(cq), file = sys.stdout)
elif op.upper() in ['X', 'Y']:
qbook.reflect( i, j, op)
if __name__ == '__main__':
usage = '%prog'
opt = optparse.OptionParser(usage)
opt.add_option('-N', type = 'int', default = 100)
opt.add_option('-Q', type = 'int', default = 10)
opt.add_option('-c', '--create', action = 'store_true', default = False, help = 'Create test case instead of running the query.')
opt.add_option('-i', '--input', type='string', default = None, help = 'Input file.')
opt.add_option('-b', '--block-factor', type = 'float', default = 32., help = 'Use sqrt(b * N) as the block size.')
opts, args = opt.parse_args()
if opts.create:
r, queries = create_test(opts.N, opts.Q, sys.stdout)
else:
r, queries = getInput(opts.input and open(opts.input, 'r') or sys.stdin)
processQueries(r, queries, opts.block_factor)
