当前位置: 首页 > news >正文

Luogu P14255 列车(train) 题解 [ 蓝 ] [ 线段树 ] [ 二维平面转化 ]

列车

感觉自己 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;
}
http://www.hskmm.com/?act=detail&tid=34228

相关文章:

  • 使用VS2022和Unity时可能出现的问题总结
  • 2025年喷雾机器人,取件机器人,工业机器人厂家权威推荐榜单:智能高效与稳定性能的行业首选!
  • 2025年给汤机厂家推荐排行榜,高效节能/智能控制/稳定耐用的优质品牌选择!
  • 理想完美主义者的宣战:当一人面对整个时代的“合理”谎言
  • Java中的this关键字的用法
  • 网络安全威胁狩猎:主动防御的终极指南
  • C#在二合一平板电脑关于旋转模式相关设置
  • 2026 中考游记
  • MinIO 介绍(3)--MinIO 客户端 mc 管理员功能
  • 8.16
  • 2025-10-19
  • 一文读懂隔离见证
  • 12131
  • 关于火柴盒的记忆
  • PWN手的成长之路-19-int_overflow
  • FFmpeg开发笔记(八十四)使用国产的librestreaming实现RTMP直播
  • 2025 年闪测仪厂家企业品牌推荐排行榜,一键式闪测仪,卧式闪测仪,影像闪测仪,立式闪测仪,2D3D 混合式闪测仪,高精度闪测仪,大量程闪测仪,复合式闪测仪公司推荐
  • 2025 年耐火砖厂家企业品牌推荐排行榜,绝热,轻质,莫来石,保温,莫来石轻质,氧化铝泡沫,氧化铝空心球,抗渗碳,高温轻质莫来石,高温耐火砖公司推荐
  • 2025 年护栏板厂家企业品牌推荐排行榜,波形,高速,镀锌,二波,三波,喷塑,国标,绳索,公路护栏板,护栏板立柱公司推荐
  • 2025 年船用锅炉厂家企业品牌推荐排行榜,基于市场口碑,评选值得信赖的船用锅炉公司推荐
  • 2025 年反应釜厂家企业品牌推荐排行榜,实验室,高压,加氢,不锈钢,试验室,氢化,聚合,高温,钛材反应釜公司推荐
  • 2025 年铸铁闸门厂家企业品牌推荐排行榜,四川铸铁闸门,镶铜铸铁闸门,渠道铸铁闸门,圆形铸铁闸门,方形铸铁闸门公司推荐
  • 2025 年启闭机厂家企业品牌推荐排行榜,四川启闭机,四川卷扬启闭机,四川螺杆启闭机,固定卷扬启闭机,手电两用螺杆启闭机,电装启闭机公司推荐
  • 2025 年清污机厂家企业品牌推荐排行榜,四川清污机,格栅清污机,回转式清污机,回转式格栅清污机,不锈钢清污机公司推荐公司推荐
  • AI视频换人工具来了!动作表情完美还原,附下载链接
  • java入门代码示例
  • 下一代超级计算的CPU设计之道
  • 10.18 学校模拟赛 T4
  • 元推理框架,自指自洽,人工智能领域的杂交水稻
  • 在AI技术唾手可得的时代,挖掘新需求成为制胜关键——某知名Linux软件资源库需求洞察