自动搬运

查看原文

来自洛谷，原作者为

	xiezheyuan 明明我已昼夜无间踏尽前路/梦想中的彼岸为何还未到/明明我已奋力无间/天天上路/我不死也为活更好/快要到终点才能知道/又再回到起点重头上路

搬运于2025-08-24 23:04:05，当前版本为作者最后更新于2024-10-01 21:03:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简要题意

你需要维护一个 $n\times m$ 的网格，初始时每个单位格的积雪深度为 $0$。

接下来有 $q$ 个时刻，每个时刻所有单元格的积雪深度都会增加一个单位。清除一个区域的积雪指将这个区域的所有单元格的积雪深度设定为 $0$。

每个时刻，你可以进行下面三次操作中的一种：

• 1 x 清除第 $x$ 行的积雪。
• 2 x 清除第 $x$ 列的积雪。
• 3 x1 y1 x2 y2 k 你希望从 $(x_1,y_1)$ 走到 $(x_2,y_2)$，每一步可以向上下左右四个方向走到相邻的单元格。但是每个经过的格子积雪单位不能超过 $k$。输出你移动的最小步数。

$1\leq n,m\leq 10^6,1\leq q\leq 3\times 10^5$

思路

嗯，确实是充满俄罗斯风情的题目，这道题质量还是不错的。

考虑我们再第三种操作中，我们是怎么走的，由于每次是整行整列地清除积雪，为了不徒增限制，我们不希望经过过多的行或列。

那我们的最优走法是怎样的呢？

• 直接走曼哈顿距离，这分为两种子情况：

  • $x_1$ 行没有积雪（或者 $y_1\sim y_2$ 列没有积雪，这是等价的，下面省略），且 $y_2$ 列没有积雪，我们直接先横着走走到 $(x_1,y_2)$，然后竖着走走到 $(y_1,y_2)$。
  • $y_1$ 列没有积雪，且 $x_2$ 行没有积雪，和上面同理。
  • $x_1,x_2$ 行没有积雪，且 $y_1,y_2$ 间有一列没有积雪，那么我们先走到这一列，然后竖着走，走到对应行，然后横着走。
  • $y_1,y_2$ 列没有积雪，且 $x_1,x_2$ 间有一行没有积雪，和上面同理。

• 绕路，这分为四种情况，分别是向上下左右四个方向绕路，方便起见，这里只讨论一种情况，即向上绕路。假如 $x_1\leq x_2$，且 $y_1,y_2$ 列没有积雪，那么我们可以找到 $x_1$ 上方最下的没有雪的一行，通过这一行走过去。

然后考虑如何维护这些复杂的信息，我们选用线段树。考虑清除积雪本质上是更新了这一行 / 这一列的时间戳，而无法通过就是时间戳不能小于一个特定的值。考虑用线段树维护区间时间戳的最大最小值。

对于限定某一行没有积雪的情况，就是一遍单点查询加上区间询问最小值，中间有一行或列，就是一遍区间询问最大值。

考虑绕路中，我们需要维护的实际上是序列上一个点左边 / 右边第一个大于一个数的点，可以考虑线段树上二分。

时间复杂度 $O({q(\log n+\log m)})$ 可以通过本题。

代码

#include <bits/stdc++.h>
//#define int long long
#define ls (i << 1)
#define rs (i << 1 | 1)
#define mid ((l + r) >> 1)
#define y1 XZY_y1
using namespace std;

const int N = 1e6 + 5;

struct sgt{
    int mint[N << 2], maxt[N << 2];
    void update(int p, int v, int i, int l, int r){
        if(l == r) return mint[i] = maxt[i] = v, void();
        if(p <= mid) update(p, v, ls, l, mid);
        else update(p, v, rs, mid + 1, r);
        mint[i] = min(mint[ls], mint[rs]);
        maxt[i] = max(maxt[ls], maxt[rs]);
    }
    int qmax(int ql, int qr, int i, int l, int r){
        if(ql <= l && r <= qr) return maxt[i];
        int ans = 0;
        if(ql <= mid) ans = max(ans, qmax(ql, qr, ls, l, mid));
        if(qr > mid) ans = max(ans, qmax(ql, qr, rs, mid + 1, r));
        return ans;
    }
    int qmin(int ql, int qr, int i, int l, int r){
        if(ql <= l && r <= qr) return mint[i];
        int ans = 1e9;
        if(ql <= mid) ans = min(ans, qmin(ql, qr, ls, l, mid));
        if(qr > mid) ans = min(ans, qmin(ql, qr, rs, mid + 1, r));
        return ans;
    }
    int find_l(int p, int v, int i, int l, int r){
        if(r < p || maxt[i] < v) return 0;
        if(l == r) return l;
        int x = find_l(p, v, ls, l, mid);
        if(x) return x;
        return find_l(p, v, rs, mid + 1, r);
    }
    int find_r(int p, int v, int i, int l, int r){
        if(l > p || maxt[i] < v) return 0;
        if(l == r) return l;
        int x = find_r(p, v, rs, mid + 1, r);
        if(x) return x;
        return find_r(p, v, ls, l, mid);
    }
} row, col;
int n, m, q;

int query(int tim){
    int x1, y1, x2, y2, k;
    cin >> x1 >> y1 >> x2 >> y2 >> k;
    int xl = min(x1, x2), yl = min(y1, y2);
    int xr = max(x1, x2), yr = max(y1, y2);
    bool x_can_row = (tim - k) <= max(row.qmin(x1, x1, 1, 1, n), col.qmin(yl, yr, 1, 1, m));
    bool x_can_col = (tim - k) <= max(col.qmin(y1, y1, 1, 1, m), row.qmin(xl, xr, 1, 1, n));
    bool y_can_row = (tim - k) <= max(row.qmin(x2, x2, 1, 1, n), col.qmin(yl, yr, 1, 1, m));
    bool y_can_col = (tim - k) <= max(col.qmin(y2, y2, 1, 1, m), row.qmin(xl, xr, 1, 1, n));
    int dist = xr - xl + yr - yl;
    if((x_can_row && y_can_col) || (x_can_col && y_can_row)) return dist;
    if(x_can_row && y_can_row){
        if((tim - k) <= col.qmax(yl, yr, 1, 1, m)) return dist;
    }
    if(x_can_col && y_can_col){
        if((tim - k) <= row.qmax(xl, xr, 1, 1, n)) return dist;
    }
    if(x1 == x2 && y1 == y2) return 0;
    int ans = INT_MAX;
    if(x_can_col && y_can_col){
        if(x1 > x2) swap(x1, x2), swap(y1, y2);
        int x = row.find_r(x1, tim - k, 1, 1, n);
        if(x) ans = min(ans, x1 - x + abs(y1 - y2) + x2 - x);
        x = row.find_l(x2, tim - k, 1, 1, n);
        if(x) ans = min(ans, x - x1 + x - x2 + abs(y1 - y2));
    }
    if(x_can_row && y_can_row){
        if(y1 > y2) swap(x1, x2), swap(y1, y2);
        int y = col.find_r(y1, tim - k, 1, 1, m);
        if(y) ans = min(ans, y1 - y + abs(x1 - x2) + y2 - y);
        y = col.find_l(y2, tim - k, 1, 1, m);
        if(y) ans = min(ans, y - y1 + y - y2 + abs(x1 - x2));
    }
    if(ans >= INT_MAX) ans = -1;
    return ans;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> q;
    for(int i=1;i<=q;i++){
        int op, x;
        cin >> op;
        if(op == 1){
            cin >> x;
            row.update(x, i, 1, 1, n);
        }
        else if(op == 2){
            cin >> x;
            col.update(x, i, 1, 1, m);
        }
        else cout << query(i) << '\n';
    }
    return 0;
}

// Written by xiezheyuan