题意简述
有一个n×m的矩阵a,每个数是[1,n×m]之间的整数,并且互不相同。然后有Q次询问,每次询问给定x,y,问你有多少个数满足:它在行中是第x大,在列中是第y大。
n,m<=1000,Q<=5e5。
思路框架
设x[i][j]表示a[i][j]在第i行里第几大,y[i][j]表示a[i][j]在第j列第几大。
设ans[i][j]表示在行里排第i大,列里排第j大的数有多少。对于所有i,j,ans[x[i][j]][y[i][j]++。
每次询问输出ans[x][y]即珂。O(nmlog(n+m)+Q)
x[i][j]和y[i][j],您珂以用一个lowerbound解决,或者像我一样sb的写一个树状数组。
代码
1 |
|