Read problems statements in Mandarin Chinese  and Russian. 
This time Chef does not want to bother you with long story, so the problem description will be as short as possible. You are given a square matrix A, which has N rows and N columns. Chef wants you to answer following queries: given a rectangular submatrix with upper-left corner in (X_{1},  Y_{1}) and lower-right corner in  (X_{2}, Y_{2}), and you are to count number of disctinct elements in this submarix, i.e count number of such distinct A_{i, j} that (X_{1}  ≤ i ≤  X_{2}) and (Y_{1}  ≤ j ≤  Y_{2}). [You may assume that i is looping through the rows and j through columns]

------ Input ------ 

The first line of the input file will contain single integer N. Then N lines with N numbers in each follow - description of the matrix. The rows are indexed from top to bottom that is top row has index 1, and columns are indexed from left to right that is left column has index 1. There is a single integer Q that follows on the next line right after the matrix description - number of Chef's queries. Then Q queries follow. Each query is described by four integers - X_{1}, Y_{1}, X_{2}, and Y_{2}.

------ Output ------ 

Output Q integers, each in a separate line - answers for the queries. 

------ Constraints ------ 

$1≤N≤300$
$1≤Q≤10^{5}$
$1≤A_{i, j}≤10$
$1≤X_{1}≤X_{2}≤N$
$1≤Y_{1}≤Y_{2}≤N$

----- Sample Input 1 ------ 
3
1 2 3
3 2 1
5 6 3
3
1 1 2 3
2 2 2 2
1 1 3 3 
----- Sample Output 1 ------ 
3
1
5

Difficulty: MEDIUM_HARD
Tags: Sorting

Range queries

Segment trees revisited

Complete search

Data structures
Skill types: Sorting

Data structures

Range queries

Complete search

Starter code:

Solutions:
from collections import defaultdict
d = defaultdict(lambda : defaultdict(lambda : defaultdict(lambda : 0)))
s = int(input())
for i in range(1, s + 1):
	a = list(map(int, input().split()))
	for j in range(1, s + 1):
		d[a[j - 1]][i][j] = 1
for k in range(1, 11):
	for i in range(1, s + 1):
		for j in range(1, s + 1):
			d[k][i][j] += d[k][i - 1][j] + d[k][i][j - 1] - d[k][i - 1][j - 1]
q = int(input())
for _ in range(q):
	(x1, y1, x2, y2) = list(map(int, input().split()))
	ans = 0
	for k in range(1, 11):
		ans += d[k][x2][y2] - d[k][x2][y1 - 1] - d[k][x1 - 1][y2] + d[k][x1 - 1][y1 - 1] != 0
	print(ans)


n = int(input().rstrip('\n'))
a = [[0] * n] * n
for i in range(n):
	line = list(map(int, input().rstrip('\n').split()))
	a[i] = line
s = [[[0] * 11 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, n + 1):
		x = a[i - 1][j - 1]
		s[i][j][x] = 1
		for k in range(1, 11):
			s[i][j][k] = s[i][j][k] + s[i - 1][j][k] + s[i][j - 1][k] - s[i - 1][j - 1][k]
q = int(input().rstrip('\n'))
for _ in range(q):
	[x1, y1, x2, y2] = list(map(int, input().rstrip('\n').split()))
	cnt = 0
	for i in range(1, 11):
		if s[x2][y2][i] - s[x2][y1 - 1][i] - s[x1 - 1][y2][i] + s[x1 - 1][y1 - 1][i] > 0:
			cnt = cnt + 1
	print(cnt)


import sys
from collections import Counter, defaultdict, deque
from math import gcd, sqrt, ceil

def li():
	return [int(i) for i in sys.stdin.readline().split()]

def si():
	return sys.stdin.readline().split()

def ii():
	return int(sys.stdin.readline())

def ip():
	return input()
n = ii()
a = [[0] * n] * n
for i in range(n):
	a[i] = li()
s = [[[0] * 11 for _ in range(n + 1)] for _ in range(n + 1)]
q = ii()
for i in range(1, n + 1):
	for j in range(1, n + 1):
		x = a[i - 1][j - 1]
		s[i][j][x] = 1
		for k in range(1, 11):
			s[i][j][k] = s[i][j][k] + s[i - 1][j][k] + s[i][j - 1][k] - s[i - 1][j - 1][k]
for _ in range(q):
	(x1, y1, x2, y2) = li()
	cnt = 0
	for i in range(1, 11):
		if s[x2][y2][i] - s[x2][y1 - 1][i] - s[x1 - 1][y2][i] + s[x1 - 1][y1 - 1][i] > 0:
			cnt += 1
	print(cnt)


import sys
n = int(sys.stdin.readline().rstrip('\n'))
a = [[0] * n] * n
for i in range(n):
	line = list(map(int, sys.stdin.readline().rstrip('\n').split()))
	a[i] = line
s = [[[0] * 11 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, n + 1):
		x = a[i - 1][j - 1]
		s[i][j][x] = 1
		for k in range(1, 11):
			s[i][j][k] = s[i][j][k] + s[i - 1][j][k] + s[i][j - 1][k] - s[i - 1][j - 1][k]
q = int(sys.stdin.readline().rstrip('\n'))
for _ in range(q):
	[x1, y1, x2, y2] = list(map(int, sys.stdin.readline().rstrip('\n').split()))
	cnt = 0
	for i in range(1, 11):
		if s[x2][y2][i] - s[x2][y1 - 1][i] - s[x1 - 1][y2][i] + s[x1 - 1][y1 - 1][i] > 0:
			cnt = cnt + 1
	print(cnt)


def f(x):
	return int(x) - 1
n = int(input())
arr = []
for i in range(n):
	arr.append([int(x) for x in input().split()])
pre = [[{arr[y][x]: 1} for x in range(n)] for y in range(n)]
for i in range(1, n):
	d = pre[0][i]
	for j in pre[0][i - 1]:
		if d.get(j) is None:
			d[j] = pre[0][i - 1][j]
		else:
			d[j] += pre[0][i - 1][j]
	d = pre[i][0]
	for j in pre[i - 1][0]:
		if d.get(j) is None:
			d[j] = pre[i - 1][0][j]
		else:
			d[j] += pre[i - 1][0][j]
for i in range(1, n):
	for j in range(1, n):
		d = pre[i][j]
		for k in pre[i - 1][j]:
			if d.get(k) is None:
				d[k] = pre[i - 1][j][k]
			else:
				d[k] += pre[i - 1][j][k]
		for k in pre[i][j - 1]:
			if d.get(k) is None:
				d[k] = pre[i][j - 1][k]
			else:
				d[k] += pre[i][j - 1][k]
		for k in pre[i - 1][j - 1]:
			d[k] -= pre[i - 1][j - 1][k]
q = int(input())
for i in range(q):
	(r1, c1, r2, c2) = map(f, input().split())
	d = pre[r2][c2].copy()
	if r1 - 1 >= 0:
		top = pre[r1 - 1][c2]
		for j in top:
			d[j] -= top[j]
	if c1 - 1 >= 0:
		left = pre[r2][c1 - 1]
		for j in left:
			d[j] -= left[j]
	if r1 - 1 >= 0 and c1 - 1 >= 0:
		corner = pre[r1 - 1][c1 - 1]
		for j in corner:
			d[j] += corner[j]
	c = 0
	for i in d:
		if d[i] != 0:
			c += 1
	print(c)


MAX_A_VAL = 10

def prep(A):
	N = len(A[0])
	Aprep = [list([None] * N) for n in range(N)]
	Aprep[0][0] = [0] * MAX_A_VAL
	Aprep[0][0][A[0][0] - 1] = 1
	for j in range(1, N):
		Aprep[0][j] = list(Aprep[0][j - 1])
		Aprep[0][j][A[0][j] - 1] += 1
	for i in range(1, N):
		Aprep[i][0] = list(Aprep[i - 1][0])
		Aprep[i][0][A[i][0] - 1] += 1
	for i in range(1, N):
		for j in range(1, N):
			Aprep[i][j] = [Aprep[i - 1][j][m] + Aprep[i][j - 1][m] - Aprep[i - 1][j - 1][m] for m in range(MAX_A_VAL)]
			Aprep[i][j][A[i][j] - 1] += 1
	return Aprep

def main():
	N = int(input())
	A = [list((int(num) for num in input().split())) for i in range(N)]
	Aprep = prep(A)
	Q = int(input())
	for q in range(Q):
		(X1, Y1, X2, Y2) = (int(num) - 1 for num in input().split())
		present = 0
		for m in range(MAX_A_VAL):
			occur = Aprep[X2][Y2][m]
			if X1 > 0:
				occur -= Aprep[X1 - 1][Y2][m]
			if Y1 > 0:
				occur -= Aprep[X2][Y1 - 1][m]
			if X1 > 0 and Y1 > 0:
				occur += Aprep[X1 - 1][Y1 - 1][m]
			if occur > 0:
				present += 1
		print(present)
main()