题解：P11081 [ROI 2019 Day 1] 自动驾驶
xiezheyuan · · 题解
简要题意
你需要维护一个
接下来有
每个时刻，你可以进行下面三次操作中的一种：
1 x清除第x 行的积雪。2 x清除第x 列的积雪。3 x1 y1 x2 y2 k你希望从(x_1,y_1) 走到(x_2,y_2) ，每一步可以向上下左右四个方向走到相邻的单元格。但是每个经过的格子积雪单位不能超过k 。输出你移动的最小步数。
思路
嗯，确实是充满俄罗斯风情的题目，这道题质量还是不错的。
考虑我们再第三种操作中，我们是怎么走的，由于每次是整行整列地清除积雪，为了不徒增限制，我们不希望经过过多的行或列。
那我们的最优走法是怎样的呢？
-
直接走曼哈顿距离，这分为两种子情况：
-
- 绕路，这分为四种情况，分别是向上下左右四个方向绕路，方便起见，这里只讨论一种情况，即向上绕路。假如
x_1\leq x_2 ，且y_1,y_2 列没有积雪，那么我们可以找到x_1 上方最下的没有雪的一行，通过这一行走过去。
然后考虑如何维护这些复杂的信息，我们选用线段树。考虑清除积雪本质上是更新了这一行 / 这一列的时间戳，而无法通过就是时间戳不能小于一个特定的值。考虑用线段树维护区间时间戳的最大最小值。
对于限定某一行没有积雪的情况，就是一遍单点查询加上区间询问最小值，中间有一行或列，就是一遍区间询问最大值。
考虑绕路中，我们需要维护的实际上是序列上一个点左边 / 右边第一个大于一个数的点，可以考虑线段树上二分。
时间复杂度
代码
#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