列车
感觉自己 DS 学傻了，赛时瞄了一眼口胡了个神秘科技做法并鉴定为不可做题，赛后一说做法是普通线段树秒会。
把限制画在二维平面上是显然的，令横轴为 \(i\)，纵轴为 \(j\)，则初始有用的部分形成一个倒三角。
考虑分别刻画两种操作：
- 查询操作相当于在平面上查询点 \((x, y)\) 左上角的最小值。
- 修改操作相当于把 \((x, y)\) 右下角的点全部设为极大值。
观察修改操作，发现被设为极大值的部分一定是楼梯形状的。观察查询操作，发现当 \(i\) 确定时，\(j\) 越小 \(p\) 越小，因此维护二维平面是没有必要的，对于每个 \(i\) 维护最小的 \(\bm j\) 即可。这样就把二维平面拍成了一维序列来维护。
考虑用线段树来维护这个序列：
- 修改操作：用
set维护楼梯的形状，修改之前先在set上暴力查询修改的是哪部分楼梯，将需要修改的部分在线段树上修改即可。因为每次修改最多只会增加一个段，所以set上暴力修改均摊复杂度是正确的。线段树具体需要维护的是区间赋值、区间求最小值的操作。 - 查询操作：分为两部分。第一部分是在楼梯内部的区域，这部分直接在线段树上查询。第二部分是在楼梯外部的区域，此时 \(i\) 取最大，\(j\) 取最小一定最优。特判掉即可。
时间复杂度 \(O(n\log n)\)。
#include <bits/stdc++.h>
#define lc (p << 1)
#define rc ((p << 1) | 1)
#define fi first
#define se second
using namespace std;
typedef long long ll;
using pi = pair<int, int>;
const int N = 200005, inf = 0x3f3f3f3f;
int n, m, pos[N];
set<pi> s1, s2;
struct Node{int l, r;int mn, tag;
};
struct Segtree{Node tr[4 * N];void modify(int p, int v){tr[p].mn = v - pos[tr[p].r];tr[p].tag = v;}void pushup(int p){tr[p].mn = min(tr[lc].mn, tr[rc].mn);}void pushdown(int p){if(tr[p].tag){modify(lc, tr[p].tag);modify(rc, tr[p].tag);}tr[p].tag = 0;}void build(int p, int ln, int rn){tr[p] = {ln, rn, 0, 0};if(ln == rn) return;int mid = (ln + rn) >> 1;build(lc, ln, mid);build(rc, mid + 1, rn);pushup(p);}void update(int p, int ln, int rn, int v){if(ln <= tr[p].l && tr[p].r <= rn){modify(p, v);return;}int mid = (tr[p].l + tr[p].r) >> 1;pushdown(p);if(ln <= mid) update(lc, ln, rn, v);if(rn >= mid + 1) update(rc, ln, rn, v);pushup(p);}int query(int p, int ln, int rn){if(ln <= tr[p].l && tr[p].r <= rn) return tr[p].mn;pushdown(p);int mid = (tr[p].l + tr[p].r) >> 1;if(rn <= mid) return query(lc, ln, rn);if(ln >= mid + 1) return query(rc, ln, rn);return min(query(lc, ln, rn), query(rc, ln, rn));}
}tr1;
void OP1(int x, int y)
{int now = x;auto it = s1.upper_bound({x, inf});--it;int nowh = (*it).se;if(y <= nowh) return;it = s1.lower_bound({x, 0});int rn = -1;while(1){if(it == s1.end()){rn = n;break;}rn = (*it).fi - 1;int tx = (*it).fi, ty = (*it).se;if(ty > y) break;++it;s1.erase({tx, ty});s2.erase({ty, tx});}s1.insert({x, y});s2.insert({y, x});tr1.update(1, x, rn, pos[y]);
}
void OP2(int x, int y)
{int res = inf;auto it = s2.upper_bound({y, 0});int rn = 1;if(it != s2.begin()){rn = min(x + 1, (*it).se);if(1 <= rn - 1) res = min(res, pos[y] - pos[rn - 1]);}if(rn <= x) res = min(res, tr1.query(1, rn, x));if(res >= inf) cout << "-1\n";else cout << res << "\n";
}
void solve()
{cin >> n >> m;for(int i = 1; i <= n; i++) cin >> pos[i];pos[n + 1] = 2 * inf;s1.clear(); s2.clear();s1.insert({0, 0});s2.insert({0, 0});for(int i = 1; i <= n; i++){s1.insert({i, i});s2.insert({i, i});}tr1.build(1, 1, n);while(m--){int op, x, y;cin >> op >> x >> y;if(op == 1) OP1(x, y + 1);else OP2(x, y);}
}
int main()
{// freopen("train.in", "r", stdin);// freopen("train.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--) solve();return 0;
}