2021 牛客多校第一场 J.Journey Among Railway Stations @ Wings            分类 ACM
发布于 星期二, 七月 27 日, 2021 年
更新于 星期三, 七月 28 日, 2021 年

笑死根本不知道代码是怎么 AC 的.

题目

题意

$n$ 个车站, 第 $i$ 个车站到下一个 $(i+1)$ 车站的用时为 $cost_i$. 车站在时间段 $[u_i, v_i]$ 开放, 开放时段才能够停靠. 如果到达车站的时刻在开放时段前, 可以等待至开放并成功停靠; 如果到达车站的时刻在开放时段后, 则停靠失败. $q$次询问,

  1. 区间 $[l, r]$, 问从车站 $l$ 到车站 $r$, 是否都能够成功停靠
  2. 修改一个车站的开放时段
  3. 修改从一个车站出发到下一个车站的用时.

$T$ 组数据.

$1 \le T \le 10^4, 2 \le n \le 10^6, 1 \le q \le 10^6, 1 \le u_i, v_i, cost_i \le 10^9$

题解

区间问题, 考虑线段树. 区间查询, 单点修改.

考虑两个区间怎么合并. 注意到"有向", 合并不满足交换律.

叶子节点, 也就是一个车站, 有开放时间段 $[u_i, v_i]$, 按照贪心的思想, 越早发车, 越有可能不超过下一个车站的关闭时间 $v_{i+1}$. 同时越有可能不超过再下一个车站的关闭时间, 以此类推. 那么对于一个连续的车站区间来说, 在第一个站会有一个最晚发车时间, 使得晚于这个时间发车, 不能完全走完这一段区间. 我们把这个时间记录在线段树的节点中, 记为 $limit$. 再对一个区间记录一个最短时刻 $earlist$, 表示完成这个区间的最小时刻. 根据贪心, 如果用在最小时刻 $earlist$ 完成一个区间并到下一个站(时刻 $earlist + cost$), 却不能再下一个站的最晚发车时间 $limit$ 前到达, 那么就无法到达下一个站. 考虑下一个区间, 也是一样, 如果不能在下一个区间的 $limit$ 前到达下一个区间的第一个站, 那么就无法完成这两个区间. 无法完成的话合并就打个失败的标记, 下面考虑能够完成, 区间怎么合并.

为方便在叙述合并区间的时候, 左边的区间称为左区间, 右边的区间称为右区间, 合并成的区间称为大区间.

大区间的 $limit$ 可能来自左区间的 $limit$, 同时需要考虑右区间的限制, 记 $cost$ 为这个区间最后一个站到下一个站(区间外某个站)的用时, $precost$ 为第一个站到最后一个站的 $cost$ 前缀和(注意这个 $precost$ 不是经过这个区间的用时, 因为车可能在某个站点等待开放, 导致实际时间比 $precost$ 长). 设 $latist_{lr} = limit_r - cost_l$, 即满足右区间条件推出来的, 左区间到最后一个站的最晚到达时间. 而满足左区间条件推出来的最晚到达时间为 $latist_{ll} = limit_l + precost_l + t$ ($t \ge 0$ 是等待时间), 大区间需要同时满足左右区间的条件, 大区间中, 最晚到达左区间最后一个点的时间 $latist = limit + precost_l + t'$ 需要对 $latist_{ll}$ 和 $latist_{lr}$ 取 min, 即 $limit + precost_l + t = \min \{ limit_l + precost_l + t, limit_r - cost_l \}$. 有 $limit + t' = \min \{limit_l + t, limit_r - precost_l - cost_l\}$.

(麻了, 不会推, 天晓得我怎么写了个 $limit = \min \{ limit_l, limit_r - precost_l - cost_l \}$ 然后就过了. 人已经傻了.)

$earlist, cost, precost$ 直接推就行.

笑死根本不会做但是过了, 复杂度 $O((n+q) \log n)$

代码
int T, n, q;
LL L[MAXN], R[MAXN], cost[MAXN];
struct Node {
	int l, r, mid;
	LL earlist, cost, precost, limit;
} t[MAXN << 2];

void updateNode(int u, LL L_, LL R_, LL cost_) {
	t[u].earlist = L_, t[u].cost = cost_, t[u].precost = 0, t[u].limit = R_;
}

Node merge(int l, int r, Node LNode, Node RNode) {
	Node res;
	res.l = l, res.r = r, res.mid = (l+r)>>1;
	if (LNode.earlist == -1 || RNode.earlist == -1 || LNode.earlist + LNode.cost > RNode.limit)
		res.earlist = res.limit = -1;
	else {
		res.limit = min(LNode.limit, RNode.limit - LNode.cost - LNode.precost);
		res.earlist = max(LNode.earlist + LNode.cost + RNode.precost, RNode.earlist);
	}
	res.cost = RNode.cost;
	res.precost = LNode.precost + LNode.cost + RNode.precost;
	return res;
}

void pushUp(int u) {
	t[u] = merge(t[u].l, t[u].r, t[LCH(u)], t[RCH(u)]);
}

void build(int l, int r, int u) {
	t[u] = Node{l, r, (l+r)>>1};
	if (l == r)
		updateNode(u, L[l], R[l], cost[l]);
	else {
		build(l, t[u].mid, LCH(u));
		build(t[u].mid+1, t[u].r, RCH(u));
		pushUp(u);
	}
}

void init(int _n) {
	build(1, _n, 1);
}

void update(int pos, LL L_, LL R_, LL cost_, int u = 1) {
	if (t[u].l == t[u].r)
		updateNode(u, L_, R_, cost_);
	else {
		if (pos <= t[u].mid)
			update(pos, L_, R_, cost_, LCH(u));
		else
			update(pos, L_, R_, cost_, RCH(u));
		pushUp(u);
	}
}

Node query(int l, int r, int u = 1) {
	if (t[u].l == l && t[u].r == r)
		return t[u];
	if (l > t[u].mid)
		return query(l, r, RCH(u));
	if (r <= t[u].mid)
		return query(l, r, LCH(u));
	else {
		Node lch = query(l, t[u].mid, LCH(u));
		Node rch = query(t[u].mid+1, r, RCH(u));
		return merge(l, r, lch, rch);
	}
}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
			scanf("%lld", L + i);
		for (int i = 1; i <= n; i++)
			scanf("%lld", R + i);
		for (int i = 1; i < n; i++)
			scanf("%lld", cost + i);
		cost[n] = 0;
		init(n);
		scanf("%d", &q);
		while (q--) {
			int op, pos, l, r;
			LL LL, RR, w;
			scanf("%d", &op);
			if (op == 0) {
				scanf("%d%d", &l, &r);
				Node res = query(l, r);
				puts(res.earlist != -1 ? "Yes" : "No");
			}
			else if (op == 1) {
				scanf("%d%lld", &pos, &w);
				cost[pos] = w;
				update(pos, L[pos], R[pos], cost[pos]);
			}
			else {
				scanf("%d%lld%lld", &pos, &LL, &RR);
				L[pos] = LL, R[pos] = RR;
				update(pos, L[pos], R[pos], cost[pos]);
			}
		}
	}
	return 0;
}

留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了
  15. 2021团体程序设计天体赛(CCCC) 个人二等奖
  16. 2021 西电 miniL CTF 优胜奖
  17. 2021 西电ACM校赛 第9名 金牌
  18. 2021 西电数模校赛 二等奖
  19. 2021 第15届IEEE 第48名
  20. 2021 CCPC 桂林站 打星

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch