问题1512--小P的R6

1512: 小P的R6

时间限制: 0 Sec  内存限制: 0 MB
提交: 30  解决: 8
[状态] [讨论版] [提交] [命题人:]
题目描述

小P最近在玩一个叫R6的游戏,在游戏地图相当于一个n*m的矩阵。游戏中玩家需要击杀他所在的行和列中最高的NPC。

不过这种玩法显然难不倒聪明的小P,于是他开始想计算有多少人是他所在排第x高并在他所在列是第y高的。

小P为了腾出更多时间玩R6,所以他请你帮他算这个问题。但是小P太皮了,他可能在矩阵的任何一个点上出现,所以你要对每一组询问计算小P可能出现的所有点的答案。

他可能有很多询问,你需要快速回答所有的询问。 

输入

第一行三个整数 n,m,q。 (n,m≤1000,q≤500000)

接下来n行,每行m个整数,代表第i行第j列的整数hi,j表示第i排第j列的人的身高。

接下来q行,每行两个整数x,y,表示一组询问。

输出
输出共q行,每行一个整数,表示第i组询问的答案。


样例输入 Copy
3 3 2
1 8 9
3 2 7
6 5 4
3 3
2 2
样例输出 Copy
3
2
提示
对于第一组询问,(1,1),(2,2),(3,3)是符合条件的。
对于第二组询问,(2,1),(3,2)是符合条件的。


身高保证在[1,n∗m]中,并且每个整数出现且仅出现一次。

对于20%的数据,n,m,q≤100。

对于另外10%的数据,n,m≤100,q≤100000。

对于另外20%的数据,n,m,q,≤400。

对于全部的数据,n,m≤1000,q≤500000。

来源/分类