解题思路

本题要求计算每只鸟在飞行时首次撞击的墙的次数。关键在于分析鸟的飞行方向与墙的位置关系，利用线段树优化查询过程：

核心步骤：

1. 墙的处理：将墙按水平和垂直分类，记录其坐标范围。
2. 坐标离散化：对墙和鸟的坐标进行离散化，以便线段树处理。
3. 线段树操作：
   • 按y坐标排序墙，用线段树维护x坐标区间，查询鸟在垂直方向飞行时最近的墙。
   • 按x坐标排序墙，用线段树维护y坐标区间，查询鸟在水平方向飞行时最近的墙。
4. 方向选择：鸟选择四个方向中最早撞击墙的方向，统计每面墙的撞击次数。

题意分析

问题本质：

• 输入：N面与坐标轴平行的墙，M只鸟的位置。
• 输出：每面墙被鸟撞击的次数。

关键点：

1. 墙的特征：墙为水平或垂直的线段，不相交。
2. 鸟的飞行：鸟向四个轴向方向飞行，选择最早撞击墙的方向。
3. 撞击判定：鸟的飞行路径与墙的线段相交时视为撞击。

标程实现

#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i,j,k) for(int i=j;i<k;++i)
#define ms(i,j,k) memset(i,j,sizeof(int)*k)
using namespace std;
const int N = 50005, S = N * 3;
int wall, tot;
int dis[N], v[N], w[N], c[S * 3];
int x[S], y[S], rx[S], ry[S], xs[S], ys[S], px[S], py[S];
int *num;
bool cmp(int a, int b) { return num[a] < num[b]; }

// 坐标离散化
void relabel(int *x, int *r, int tot, int *a, int *mp) {
    int k, p, m = 0;
    rep(i,0,tot) r[i] = i;
    num = x;
    sort(r, r + tot, cmp);
    a[r[0]] = ++m; mp[m] = x[r[0]];
    rep(i,1,tot) {
        k = r[i]; p = r[i - 1];
        if (x[k] != x[p]) a[k] = ++m, mp[m] = x[k];
        else a[k] = m;
    }
}

// 线段树查询：获取指定位置的标记
int get(int t, int l, int r, int q) {
    if (c[t] != -2) return c[t];
    int mid = l + r >> 1;
    if (q <= mid) return get(t * 2, l, mid, q);
    else return get(t * 2 + 1, mid + 1, r, q);
}

// 线段树更新：区间标记
void set(int t, int l, int r, int ql, int qr, int qc) {
    if (ql <= l && r <= qr) { c[t] = qc; return; }
    if (c[t] != -2) {
        c[t * 2] = c[t * 2 + 1] = c[t];
        c[t] = -2;
    }
    int mid = l + r >> 1;
    if (ql <= mid) set(t * 2, l, mid, ql, qr, qc);
    if (qr > mid) set(t * 2 + 1, mid + 1, r, ql, qr, qc);
}

// 扫描鸟的位置，更新最近撞击墙的信息
void scan(int k, int *ys, int *xs, int *py, int n) {
    if (k < wall) { // 处理垂直墙
        int k2 = k ^ 1;
        if (xs[k2] >= xs[k])
            set(1, 1, n, xs[k], xs[k2], k / 2);
    } else { // 处理鸟的位置
        int t = get(1, 1, n, xs[k]);
        if (~t) {
            int d = min(abs(py[ys[k]] - py[ys[t * 2]]), abs(py[ys[k]] - py[ys[t * 2 + 1]]));
            k -= wall;
            if (d < dis[k]) dis[k] = d, v[k] = t;
        }
    }
}

// 处理鸟在水平/垂直方向的飞行
void fly(int *ry, int *ys, int *xs, int *py, int n) {
    c[1] = -1;
    rep(i,0,tot) scan(ry[i], ys, xs, py, n);
    c[1] = -1;
    for(int i=tot-1;i>=0;--i) scan(ry[i], ys, xs, py, n);
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    wall = n * 2; tot = wall + m;
    
    // 读取墙和鸟的坐标
    rep(i,0,tot) scanf("%d%d", x + i, y + i);
    
    // 离散化x坐标
    relabel(x, rx, tot, xs, px);
    
    // 离散化y坐标
    relabel(y, ry, tot, ys, py);
    
    // 初始化距离数组和计数数组
    ms(dis, 0x7f, m); ms(w, 0, n);
    
    // 处理垂直方向飞行，查询水平墙
    fly(ry, ys, xs, py, xs[rx[tot - 1]]);
    
    // 处理水平方向飞行，查询垂直墙
    fly(rx, xs, ys, px, ys[ry[tot - 1]]);
    
    // 统计每面墙的撞击次数
    rep(i,0,m) ++w[v[i]];
    
    // 输出结果
    rep(i,0,n) printf("%d\n", w[i]);
    
    return 0;
}

代码解释

1. 坐标离散化：

   • relabel函数将墙和鸟的坐标映射到连续整数，减少线段树处理范围。
   • 排序后去重，生成坐标到排名的映射表。

2. 线段树操作：

   • set函数用于区间标记，记录墙的x/y坐标范围。
   • get函数查询指定位置的标记，确定最近的墙。

3. 飞行方向处理：

   • fly函数分两次扫描（正序和逆序），处理鸟在水平/垂直方向的飞行。
   • 通过线段树快速定位最近的墙，更新鸟的撞击记录。

4. 结果统计：

   • v[i]记录第i只鸟撞击的墙，w数组统计每面墙的撞击次数。

关键逻辑

• 方向选择：鸟选择四个方向中飞行距离最短的方向，确保首次撞击的墙唯一。
• 线段树优化：通过区间标记和查询，高效处理大量墙和鸟的位置关系。
• 离散化处理：将大范围坐标映射到小区间，减少线段树节点数，提高效率。