题目链接 http://noi.ac/problem/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('\n');
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3429459.html