noi.ac#36 题解

题目链接

(Solution:)

直接大力预处理,(O(n^2log_2n)+O(q))可过

(Code:)

#include<bits/stdc++.h>
using namespace std;
namespace my_std
{
	typedef long long ll;
	typedef double db;
	const db PI=acos(-1.0);
	#define cp complex<db>
	#define MP make_pair
	#define fir first
	#define sec second
	#define fr(i,x,y) for(int i=(x);i<=(y);i++)
	#define pfr(i,x,y) for(int i=(y);i>=(x);i--)
	#define gfr(u) for(int i=head[u];i;i=e[i].nxt)
	#define pf printf
	inline ll read()
	{
		ll sum=0,f=1;
		char ch=0;
		while(!isdigit(ch))
		{
			if(ch=='-') f=-1;
			ch=getchar();
		}
		while(isdigit(ch))
		{
			sum=(sum<<1)+(sum<<3)+(ch^48);
			ch=getchar();
		}
		return sum*f;
	}
	inline void write(int x)
	{
	    if(x<0)
		{
	    	putchar('-');
			x=-x;
		}
	    if(x>9) write(x/10);
	    putchar(x%10+'0');
	}
}
using namespace my_std;
const int N=1050;
int n,m,q,a[N][N],b[N][N],aa[N][N],bb[N][N],ans[N][N]; 
int main(void)
{
    n=read(),m=read(),q=read();
    fr(i,1,n) fr(j,1,m) a[i][j]=read();
    fr(i,1,m) fr(j,1,n) b[i][j]=a[j][i];
    fr(i,1,n) fr(j,1,m) aa[i][j]=a[i][j];
    fr(i,1,m) fr(j,1,n) bb[i][j]=b[i][j];
    fr(i,1,n) sort(aa[i]+1,aa[i]+m+1);
    fr(i,1,m) sort(bb[i]+1,bb[i]+n+1);
    fr(i,1,n) 
    {
    	fr(j,1,m)
		{
            int x=lower_bound(aa[i]+1,aa[i]+m+1,a[i][j])-aa[i];
			int y=lower_bound(bb[j]+1,bb[j]+n+1,a[i][j])-bb[j];
            ans[m-x+1][n-y+1] ++;
        }
	}
    while(q--)
    {
        int x=read(),y=read();
        write(ans[x][y]);
        putchar('
');
    }
    return 0;
}