LightOJ: Points in Rectangle

Problem link: loj 1266

Technique: Binary Indexed Tree

If you don't know about Binary Indexed Tree, first learn it. You can also check BIT here BIT

Given two types of query,

• 0 x y: we got a new point at co-ordinate (x,y) [ if already a point exist in the same co-ordinate, this query does nothing ] 
• 1 x1 y1 x2 y2: we are given a rectangle whose lower left co-ordinate is (x1, y1) and upper-right corner is (x2, y2); your task is to find the number of points, given so far, that lie inside this rectangle. You can assume that (x1 < x2, y1 < y2).

We will maintain a 2-D BIT(Binary Indexed Tree) to solve this problem. For query 0 x y, we will call update function each time we got a new point (x,y). For the second query, we will call out query_sum function with parameter (x,y); it means we will get the sum of the rectangle that's lower left co-ordinate is (1,1) and upper right co-ordinate is (x,y). Let's see a testcase:

1
4
0 1 1
0 2 6
1 1 1 6 6
1 2 2 5 5

We got two points (1,1) and (2,6), let's plot these points:

Now let's see the first query, we have to find how many points are inside (1,1) and (6,6). We will call out query_sum function with parameter (6,6), And this will cover the whole area from (1,1) to (6,6) and we will get output = 2
Ok, for the second query we need to find points inside (2,2) and (5,5). We will call our query_sum function with (5,5) and the selected area would be like this:

But we have some extra area here as our query starts from (2,2). So we need to remove those extra area. Basically we need to calculate our desired area as follow:

area = query_sum(x2,y2)-query_sum(x1-1,y2-1)-query_sum(x2-1,y1-1)+query_sum(x1-1,y1-1)

Let's see how does it look, Here:

A = query_sum(x2,y2)

B = query_sum(x1-1,y2-1)

C = query_sum(x2-1,y1-1)

D = query_sum(x1-1,y1-1)

     

 

We added D because, while subtracting B and C, D got subtracted twice. So we need to balance it by adding. Hope you understand what we need to do here.

Code:

	#include <bits/stdc++.h>
	#include <ext/pb_ds/assoc_container.hpp>
	#include <iostream>
	using namespace std;
	using namespace __gnu_pbds;
	#define ll long long
	#define Max(a,b) ((a>=b)? a : b)
	#define Min(a,b) ((a<=b)? a : b)
	#define pb push_back
	#define MOD 1000000007
	#define MP make_pair
	#define vi vector<int>
	#define vll vector<ll>
	#define MAX 1123456
	//typedef __int128 bigll;
	int a[1002][1002];
	int bit[1002][1002];
	int query_sum(int x,int y)
	{
	int ret=0;
	if(x<0 || y<0)return 0;
	for(int i=x; i>=0; i=(i&(i+1))-1)
	for(int j=y; j>=0; j=(j&(j+1))-1)
	ret+=bit[i][j];
	return ret;
	}
	void update(int x,int y,int val)
	{
	for (int i = x; i <=1000; i = i | (i+1))
	for (int j = y; j <=1000 ; j = j | (j+1))
	bit[i][j] += val;
	}
	int get_sum(int x,int y,int l,int r)
	{
	return query_sum(l,r) - query_sum(x-1,r) - query_sum(l,y-1) + query_sum(x-1,y-1);
	}
	int main()
	{
	//ios_base::sync_with_stdio(false);
	//cin.tie(NULL);
	//FILE*f=freopen("input.txt","r",stdin);
	//FILE*o=freopen("output.txt","w",stdout);
	int x,y,t,q,l,r,c;
	scanf("%d",&t);
	for(int tc=1;tc<=t;tc++)
	{
	memset(bit,0,sizeof(bit));
	memset(a,0,sizeof(a));
	printf("Case %d:\n",tc);
	scanf("%d",&q);
	while(q--)
	{
	scanf("%d",&c);
	if(c==0)
	{
	scanf("%d %d",&x,&y);
	if(a[x][y]!=1)
	{
	a[x][y]=1;
	update(x,y,1);
	}
	}
	else
	{
	scanf("%d %d %d %d",&x,&y,&l,&r);
	printf("%d\n",get_sum(x,y,l,r));
	}
	}
	}
	//fclose(f);
	//fclose(o);
	return 0;
	}

view raw loj_1266.cpp hosted with ❤ by GitHub