洛谷链接

分析

离散化（记得算上起点），之后的每个格子相当于一个矩形。显然矩形只有四个角是重要的，对所有角跑最短路。

第一问，对于询问点求出在哪个矩形，四个方向过来取 $\min$ 即可。

第二问，相当于对每个矩形要求它每个时刻扩展了多少点。那么从四个角开始，分别考察每个角扩张的过程。对于某一个角，它一开始扩张的时候贡献是 $1$，之后每个时刻比前一个时刻的贡献多 $1$。而之后它可能会撞到另外一个角，那么撞完了之后发现每个时刻比前一个时刻的贡献增量就减少了 $1$。而之后它可能又要撞到另外一个角，那么撞完了之后每个时刻比前一个时刻的贡献增量就又少了 $1$。而之后它可能就要撞到它对面的那个角了，那这么一撞就相当于强制停止这个角的贡献了。于是我们只需要算出这个角分别什么时候撞到两个邻角，什么时候撞到对角，然后使用一些差分维护贡献即可。当然这三个时间的相对顺序也不是一定的，因此需要一些讨论。可以画图来辅助理解。由于范围很大，需要将所有差分和询问离线处理。

总复杂度 $\mathcal{O}(n^2\log n + q\log n)$ 或 $\mathcal{O}(n^2\log n + q\log (n^2 + q))$。但也可能其实是类似的，但反正也就那样。总之能过。

::::success[代码]

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <array>
#define int long long
using namespace std;
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++
char buf[1<<21], *p1, *p2, ch;
long long read() {
    long long ret = 0, neg = 0; char c = getchar(); neg = (c == '-');
    while (c < '0' || c > '9') c = getchar(), neg |= (c == '-');
    while (c >= '0' && c <= '9') ret = ret * 10 + c - '0', c = getchar();
    return ret * (neg ? -1 : 1);
}
const int inf = 0x3f3f3f3f3f3f3f;
int n, tp, q;
int d_x[1005], dxcnt;
int d_y[1005], dycnt;
/*
01
23
*/
struct node { int x, y, t, dis; };
inline bool operator<(node x, node y) { return x.dis > y.dis; }
priority_queue<node> Q;
bool vis[1005][1005][4];
int dist[1005][1005][4];
int ban[1005][1005];
void _dijkstra() {
    memset(dist, 63, sizeof dist);
    int sx = lower_bound(d_x + 1, d_x + dxcnt + 1, 0) - d_x;
    int sy = lower_bound(d_y + 1, d_y + dycnt + 1, 0) - d_y;
    Q.push((node) { sx, sy, 0, dist[sx][sy][0] = 0 });
    while (Q.size()) {
        node tmp = Q.top(); Q.pop();
        int x = tmp.x, y = tmp.y, t = tmp.t;
        if (vis[x][y][t]) continue;
        vis[x][y][t] = 1;
        auto chkupd = [&](int tx, int ty, int tt, int ww) {
            if (!ban[tx][ty] && dist[tx][ty][tt] > dist[x][y][t] + ww) 
                Q.push((node) { tx, ty, tt, dist[tx][ty][tt] = dist[x][y][t] + ww });
        };
        if (t == 0) {
            if (x != 1) chkupd(x - 1, y, 1, 1);
            if (y != dycnt - 1) chkupd(x, y + 1, 2, 1);
            chkupd(x, y, 1, d_x[x + 1] - d_x[x] - 1);
            chkupd(x, y, 2, d_y[y + 1] - d_y[y] - 1);
        } else if (t == 1) {
            if (x != dxcnt - 1) chkupd(x + 1, y, 0, 1);
            if (y != dycnt - 1) chkupd(x, y + 1, 3, 1);
            chkupd(x, y, 0, d_x[x + 1] - d_x[x] - 1);
            chkupd(x, y, 3, d_y[y + 1] - d_y[y] - 1);
        } else if (t == 2) {
            if (x != 1) chkupd(x - 1, y, 3, 1);
            if (y != 1) chkupd(x, y - 1, 0, 1);
            chkupd(x, y, 3, d_x[x + 1] - d_x[x] - 1);
            chkupd(x, y, 0, d_y[y + 1] - d_y[y] - 1);
        } else {
            if (x != dxcnt - 1) chkupd(x + 1, y, 2, 1);
            if (y != 1) chkupd(x, y - 1, 1, 1);
            chkupd(x, y, 2, d_x[x + 1] - d_x[x] - 1);
            chkupd(x, y, 1, d_y[y + 1] - d_y[y] - 1);
        }
    }
}
struct Node { int op, s, d, x; };
vector<Node> vec;
int ans[200005];
inline int calc(int s, int d, int len) { int t = s + len * d; return (s * 2 + (len + 1) * d) * len / 2; }
void work() {
    for (int i = 1; i < dxcnt; i++) {
        for (int j = 1; j < dycnt; j++) {
            if (ban[i][j]) continue;
            int X = d_x[i + 1] - d_x[i], Y = d_y[j + 1] - d_y[j], t;
            if (X == Y && Y == 1) vec.push_back({ 1, 1, 0, dist[i][j][0] }), vec.push_back({ -1, 1, 0, dist[i][j][0] + 1 });
            else for (int k : { 0, 1, 2, 3 }) {
                t = Y - 2 - abs(dist[i][j][k] - dist[i][j][k ^ 2]);
                int t1 = (t >> 1) + (t & 1) * (k < (k ^ 2)) + max(dist[i][j][k], dist[i][j][k ^ 2]);
                t = X - 2 - abs(dist[i][j][k] - dist[i][j][k ^ 1]);
                int t2 = (t >> 1) + (t & 1) * (k < (k ^ 1)) + max(dist[i][j][k], dist[i][j][k ^ 1]);
                t = X + Y - 3 - abs(dist[i][j][k] - dist[i][j][k ^ 3]);
                int t3 = (t >> 1) + (t & 1) * (k < (k ^ 3)) + max(dist[i][j][k], dist[i][j][k ^ 3]);
                if (t1 < dist[i][j][k] || t2 < dist[i][j][k]) continue;
                (t1 > t2) ? swap(t1, t2) : void();
                vec.push_back({ 1, 1, 1, dist[i][j][k] });
                if (t3 < t1) {
                    vec.push_back({ -1, t3 + 2 - dist[i][j][k], -1, t3 + 1 });
                    continue;
                }
                vec.push_back({ -1, t1 + 2 - dist[i][j][k], -1, t1 + 1 });
                vec.push_back({ 1, t1 + 1 - dist[i][j][k], 0, t1 + 1 });
                if (t3 < t2) {
                    vec.push_back({ -1, t1 + 1 - dist[i][j][k], 0, t3 + 1 });
                    continue;
                }
                vec.push_back({ -1, t1 + 1 - dist[i][j][k], 0, t2 + 1 });
                vec.push_back({ 1, t1 - dist[i][j][k], -1, t2 + 1 });
                vec.push_back({ -1, max(0ll, t1 - dist[i][j][k] - (t3 - t2)), 1, min(t3 + 1, t2 + 1 + t1 - dist[i][j][k]) });
            }
        }
    }
    sort(vec.begin(), vec.end(), [](Node x, Node y) { return x.x == y.x ? (abs(x.op) > abs(y.op)) : (x.x < y.x); });
    int dd = 0, al = 0, k = 0, lst = 0;
    for (auto v : vec) {
        dd += calc(al, k, v.x - lst); al += k * (v.x - lst); lst = v.x;
        if (v.op == 0) ans[v.d] = dd;
        else if (v.op == 1) al += v.s, k += v.d, dd += v.s;
        else al -= v.s, k += v.d, dd -= v.s;
    }
}
array<int, 4> rect[405];
signed main() {
    freopen("field.in", "r", stdin);
    freopen("field.out", "w", stdout);
    n = read(), tp = read(), q = read();
    for (int i = 1; i <= n; i++) {
        int &x1 = rect[i][0], &x2 = rect[i][1], &y1 = rect[i][2], &y2 = rect[i][3];
        x1 = read(), x2 = read(), y1 = read(), y2 = read();
        d_x[++dxcnt] = x1, d_x[++dxcnt] = x2 + 1;
        d_y[++dycnt] = y1, d_y[++dycnt] = y2 + 1;
    }
    d_x[++dxcnt] = 0, d_x[++dxcnt] = 1;
    d_x[++dxcnt] = -inf, d_x[++dxcnt] = inf;
    d_y[++dycnt] = 0, d_y[++dycnt] = 1;
    d_y[++dycnt] = -inf, d_y[++dycnt] = inf;
    sort(d_x + 1, d_x + dxcnt + 1); dxcnt = unique(d_x + 1, d_x + dxcnt + 1) - d_x - 1;
    sort(d_y + 1, d_y + dycnt + 1); dycnt = unique(d_y + 1, d_y + dycnt + 1) - d_y - 1;
    for (int i = 1; i <= n; i++) {
        int x1, x2, y1, y2;
        x1 = lower_bound(d_x + 1, d_x + dxcnt + 1, rect[i][0]) - d_x;
        x2 = lower_bound(d_x + 1, d_x + dxcnt + 1, rect[i][1] + 1) - d_x;
        y1 = lower_bound(d_y + 1, d_y + dycnt + 1, rect[i][2]) - d_y;
        y2 = lower_bound(d_y + 1, d_y + dycnt + 1, rect[i][3] + 1) - d_y;
        ++ban[x1][y1], --ban[x2][y1], --ban[x1][y2], ++ban[x2][y2];
    }
    for (int i = 1; i <= dxcnt; i++) {
        for (int j = 1; j <= dycnt; j++) 
            ban[i][j] += ban[i - 1][j] + ban[i][j - 1] - ban[i - 1][j - 1];
    }
    _dijkstra();
    if (tp == 1) {
        while (q--) {
            int x = read(), y = read(), tx, ty, ans;
            tx = upper_bound(d_x + 1, d_x + dxcnt + 1, x) - d_x - 1;
            ty = upper_bound(d_y + 1, d_y + dycnt + 1, y) - d_y - 1;
            ans = min({ 
                dist[tx][ty][0] + x - d_x[tx] + d_y[ty + 1] - y - 1, 
                dist[tx][ty][1] + d_x[tx + 1] - x - 1 + d_y[ty + 1] - y - 1, 
                dist[tx][ty][2] + x - d_x[tx] + y - d_y[ty], 
                dist[tx][ty][3] + d_x[tx + 1] - x - 1 + y - d_y[ty]
            });
            cout << (ans >= inf ? -1 : ans) << "\n";
        }
    } else {
        for (int i = 1; i <= q; i++) vec.push_back({ 0, 0, i, read() }); work();
        for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
    }
    return 0;
}

::::