noi.ac #36 模拟

\(des\)

存在 \(1000 \times 1000\) 的矩阵，保证元素互不相同，\(2e5\) 次询问，每次询

问给定 \(x, y\) 问存在多少点 \((a, b)\) 满足该元素是 \(a\) 行的 \(x\) 大， \(b\)

列的 \(y\) 大。

\(sol\)

这数据范围给的不敢写暴力啊，然而这 T1 就是暴力啊

需要对所有可能的情况预处理，处理处所有可能的询问

时间复杂度 \(O(n^2logn)\)

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstring>

#include <string>

using namespace std;

const int N = 1010;

#define gc getchar()

#define Rep(i, a, b) for(int i = a; i <= b; i ++)

#define LL long long

inline int read() {int x = 0; char c = gc; while(c < '0' || c > '9') c = gc;

while(c >= '0' && c <= '9')	x = x * 10 + c - '0', c = gc; return x;}

inline LL readLL() {LL x = 0; char c = gc; while(c < '0' || c > '9') c = gc;

while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc; return x;}

int A[N][N], B[N][N];

int Sa[N][N], Sb[N][N];

int Answer[N][N];

int n, m, q;

int main() {

	n = read(), m = read(), q = read();

	Rep(i, 1, n) Rep(j, 1, m) A[i][j] = read();

	Rep(i, 1, m) Rep(j, 1, n) B[i][j] = A[j][i];

	Rep(i, 1, n) Rep(j, 1, m) Sa[i][j] = A[i][j];

	Rep(i, 1, m) Rep(j, 1, n) Sb[i][j] = B[i][j];

	Rep(i, 1, n) sort(Sa[i] + 1, Sa[i] + m + 1);

	Rep(i, 1, m) sort(Sb[i] + 1, Sb[i] + n + 1);

	Rep(i, 1, n)

		Rep(j, 1, m) {

			int Num = A[i][j];

			int x = lower_bound(Sa[i] + 1, Sa[i] + m + 1, Num) - Sa[i];

			int y = lower_bound(Sb[j] + 1, Sb[j] + n + 1, Num) - Sb[j];

			int xx = m - x + 1, yy = n - y + 1;

			Answer[xx][yy] ++;

		}

	Rep(i, 1, q) {

		int x = read(), y = read();

		printf("%d\n", Answer[x][y]);

	}

	return 0;

}

巴特西

noi.ac #36 模拟

最新文章

热门文章