题解 P1442 【铁球落地】

╮(╯_╰)╭一道码力题。对于我这种蒟蒻超级不友好 直接用线段树作预处理，从下往上扫描线，预处理出每个线段在左边跳和在右边跳能跳到哪一条线段。 接着我们可以打个dp，$dp[i][0/1]$表示起点到达第i个线段左边/右边要多少时间，地面特判一下就行了。 先前疯狂WA，后来自己和std拍出一个数据，才发现自己的flag标记在pushdown的时候没有下放（真的蠢），所以这组数据就放这了。 一个拍出来的数据： 5 3 11 11 1 3 33 2 4 55 4 3 44 7 7 11 9 11 16 输出19 代码： ```cpp #include<bits/stdc++.h> #define fo(i, a, b) for (Re int i = (a); i <= (b); ++i) #define fd(i, a, b) for (Re int i = (a); i >= (b); --i) #define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v) #define N 200005 #define Re register #define pb push_back #define F first #define S second #define ll long long #define inf 1000000007 #define mp std::make_pair #define lowbit(x) (x & -x) #define ls (k << 1) #define rs (k << 1 | 1) #define mod 1000000007 int n, T, X, Y, a[N], tot, cnt, ans, x, y, w, i, pos, now, dp[N][2], L, R, m, X0, Y0; struct line{ int x1, x2, y, l, r; friend bool operator < (line qwq, line qaq) { return qaq.y < qwq.y; } }p[N]; struct tree{ int v; bool flag; }t[N << 2]; inline void pushdown (int k) { if (t[k].flag) { t[k].flag = 0; t[ls].v = t[rs].v = t[k].v; t[rs].flag = t[ls].flag = 1; } } inline void add (int k, int l, int r) { if (L <= l && R >= r) { t[k].v = i; t[k].flag = 1; return; } pushdown(k); int mid = l + r >> 1; if (L <= mid) add(ls, l, mid); if (mid < R) add(rs, mid + 1, r); } inline int query (int k, int l, int r) { if (t[k].flag && l <= now && now <= r || l == r && l == now) { return t[k].v; } pushdown(k); int mid = l + r >> 1; if (now <= mid) return query(ls, l, mid); if (mid < now) return query(rs, mid + 1, r); } inline int abs (int x) {return x < 0 ? -x : x;} inline int dis (int x1, int y1, int x2, int y2) {return abs(x1 - x2) + abs(y1 - y2);} int main () { scanf("%d %d", &n, &m); scanf("%d %d", &X0, &Y0); fo (i, 1, n) { scanf("%d %d %d", &p[i].y, &p[i].x1, &p[i].x2); a[i] = p[i].x1; a[i + n] = p[i].x2; } std::sort(a + 1, a + n + n + 1); cnt = std::unique(a + 1, a + n + n + 1) - a - 1; std::sort(p + 1, p + n + 1);//y值从高到低 fo (i, 1, n) if (p[i].y <= Y0 && p[i].x1 <= X0 && p[i].x2 >= X0) { pos = i; break; } int j; i = 0; L = 1; R = cnt; add(1, 1, cnt); for (i = n; i; --i) { now = std::lower_bound(a + 1, a + cnt + 1, p[i].x1) - a; j = query(1, 1, cnt); if (p[i].y - p[j].y <= m) p[i].l = j; else p[i].l = -1; now = std::lower_bound(a + 1, a + cnt + 1, p[i].x2) - a; j = query(1, 1, cnt); if (p[i].y - p[j].y <= m) p[i].r = j; else p[i].r = -1; L = std::lower_bound(a + 1, a + cnt + 1, p[i].x1) - a; R = std::lower_bound(a + 1, a + cnt + 1, p[i].x2) - a; add(1, 1, cnt); } memset(dp, 0x3f, sizeof dp); // fo (i, 1, n) // printf("i = %d l = %d r = %d\n", i, p[i].l, p[i].r); dp[pos][0] = dis(X0, Y0, p[pos].x1, p[pos].y); dp[pos][1] = dis(X0, Y0, p[pos].x2, p[pos].y); fo (i, 1, n) { int nxt = p[i].l; if (nxt != -1) { if (!nxt) dp[0][0] = std::min(dp[0][0], dp[i][0] + p[i].y); else { dp[nxt][0] = std::min(dp[nxt][0], dp[i][0] + dis(p[i].x1, p[i].y, p[nxt].x1, p[nxt].y)); dp[nxt][1] = std::min(dp[nxt][1], dp[i][0] + dis(p[i].x1, p[i].y, p[nxt].x2, p[nxt].y)); } } nxt = p[i].r; if (nxt != -1) { if (!nxt) dp[0][0] = std::min(dp[0][0], dp[i][1] + p[i].y); else { dp[nxt][0] = std::min(dp[nxt][0], dp[i][1] + dis(p[i].x2, p[i].y, p[nxt].x1, p[nxt].y)); dp[nxt][1] = std::min(dp[nxt][1], dp[i][1] + dis(p[i].x2, p[i].y, p[nxt].x2, p[nxt].y)); } } } printf("%d\n", dp[0][0]); return 0; } ```