Walking Along a Fence (USACO Bronze 2024 US Open)

这个题比较坑，因为N和P是 $2 \cdot 10^5$ ，所以每次查询不能扫描柱子，否则就变成了 $\mathcal{O}(NP)$ ，无法通过。

那有什么办法可以预先处理数据呢？我们可以看到，这个题目的座标系是很小的，只有 $10^6$ ，所以我们可以将fence拉平，就是一条线，我们关心的其实是这条线上两点间的沿着fence走的距离。所以，一种办法就是给个点标注上到第一个柱子的距离（相对位置），然后处理每个查询时，直接读出起点和终点在这条线上的相对位置，就可以 $\mathcal{O}(1)$ 计算他们之间的最短距离了，注意可以顺时针走，也可以逆时针走。

此题要点是看到座标系很小，再次说明读题一定要仔细，不要漏过细微的条件，包括数据范围、样例的特点，有时还包括测试点性质等。

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n, p;
int x[200005], y[200005];
long long dist[1005][1005];
 
int main() {
    long long d = 0;
 
    scanf("%d %d", &n, &p);
    for (int i = 0; i < p; i++) {
        scanf("%d %d", &x[i], &y[i]);
    }
    for (int i = 0; i < p; i++) {
        int x2 = i == p-1 ? x[0] : x[i+1];
        int y2 = i == p-1 ? y[0] : y[i+1];
        if (x2 == x[i]) {
            for (int j = y[i]; j != y2; j+=y2>y[i]?1:-1) {
                dist[x[i]][j] = d;
                d++;
            }
        } else {
            for (int j = x[i]; j != x2; j+=x2>x[i]?1:-1) {
                dist[j][y[i]] = d;
                d++;
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        int x1, x2, y1, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        printf("%lld\n", min(abs(dist[x1][y1]-dist[x2][y2]), d-abs(dist[x1][y1]-dist[x2][y2])));
    }
 
    return 0;
}