题目链接:https://syzoj.com/problem/449
内存限制：128 MiB 时间限制：1000 ms

题目描述

小P最近在玩一个叫R6的游戏，在游戏地图相当于一个n*m的矩阵。游戏中玩家需要击杀他所在的行和列中最高的NPC。
不过这种玩法显然难不倒聪明的小P，于是他开始想计算有多少人是他所在排第x高并在他所在列是第y高的。
小P为了腾出更多时间玩R6，所以他请你帮他算这个问题。但是小P太皮了，他可能在矩阵的任何一个点上出现，所以你要对每一组询问计算小P可能出现的所有点的答案。
他可能有很多询问，你需要快速回答所有的询问。
如果你帮他解决了问题，你就能跟他一起玩R6!(当然你还要写模拟赛)

输入格式

第一行三个整数 n,m,q。
接下来n行，每行m个整数，代表第i行第j列的整数hi,jh_{i,j}h​i,j​​表示第i排第j列的人的身高。
接下来q行，每行两个整数x，y，表示一组询问。

输出格式

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

输入

3 3 2
1 8 9
3 2 7
6 5 4
3 3
2 2

输出

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。

解题思路

先记录下每个数所在的行和列，然后从大到小算出此数在此行此列的排名，并利用桶排的思想，让处于此行此列的排名个数加一。

#include <stdio.h>
#include <string.h>
#define MAXN 1005
int row[MAXN], col[MAXN], h[MAXN * MAXN][2], ans[MAXN][MAXN];
int main() {
#ifndef LACOL
    freopen("r6.in", "r", stdin);
    freopen("r6.out", "w", stdout);
#endif
    int n, m, q, s, x, y;
    while (~scanf("%d%d%d", &n, &m, &q)) {
        memset(row, 0, sizeof(row));
        memset(col, 0, sizeof(col));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%d", &s);
                h[s][0] = i;
                h[s][1] = j;
            }
        }
        for (int i = m * n; i > 0; i--)
            ans[++row[h[i][0]]][++col[h[i][1]]]++;
        while (q--) {
            scanf("%d%d", &x, &y);
            printf("%d\n", ans[x][y]);
        }    
    }
    return 0;
}