dp
利用单调双向队列。类似sliding windows。
View Code #include#include #include #include using namespace std; #define maxn 260 struct Node { int pos, a; Node() { } Node(int pp, int aa) : pos(pp), a(aa) { } } q[maxn]; int n, sub, m; int f[maxn][maxn], fmax[maxn][maxn], fmin[maxn][maxn]; int lmax[maxn][maxn], lmin[maxn][maxn]; int front, rear; int ins1(Node x) { while (front < rear && x.pos - q[front].pos >= sub) front++; while (front < rear && x.a > q[rear - 1].a) rear--; q[rear++] = x; return q[front].a; } int ins2(Node x) { while (front < rear && x.pos - q[front].pos >= sub) front++; while (front < rear && x.a < q[rear - 1].a) rear--; q[rear++] = x; return q[front].a; } void input() { scanf("%d%d%d", &n, &sub, &m); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &f[i][j]); } void work() { for (int i = 0; i < n; i++) { front = rear = 0; for (int j = 0; j < sub - 1; j++) ins1(Node(j, f[i][j])); for (int j = sub - 1; j < n; j++) lmax[i][j] = ins1(Node(j, f[i][j])); } for (int i = sub - 1; i < n; i++) { front = rear = 0; for (int j = 0; j < sub - 1; j++) ins1(Node(j, lmax[j][i])); for (int j = sub - 1; j < n; j++) fmax[j][i] = ins1(Node(j, lmax[j][i])); } for (int i = 0; i < n; i++) { front = rear = 0; for (int j = 0; j < sub - 1; j++) ins2(Node(j, f[i][j])); for (int j = sub - 1; j < n; j++) lmin[i][j] = ins2(Node(j, f[i][j])); } for (int i = sub - 1; i < n; i++) { front = rear = 0; for (int j = 0; j < sub - 1; j++) ins2(Node(j, lmin[j][i])); for (int j = sub - 1; j < n; j++) fmin[j][i] = ins2(Node(j, lmin[j][i])); } } int main() { //freopen("t.txt", "r", stdin); input(); work(); for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); a = a + sub - 2; b = b + sub - 2; printf("%d\n", fmax[a][b] - fmin[a][b]); } return 0; }