主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
题解：CF1371F Raging Thunder
最后更新于 2025-08-28 09:10:58
作者
2huk
分类
题解
题解
CF1371F
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
MX-C day1 T3。 ### 题意 [太长了回去看吧](https://mna.wang/contest/1242/problem/3)。 ### 做法 我们给每个空隙一个属性： $$ a_i = \left\{ \begin{matrix} 1&, s_i = \texttt {//} \\ -1 &,s_i = \texttt{\\\\} \\ +\infty&,s_i = \texttt{/\\}\\ -\infty&,s_i = \texttt{\\/}\end{matrix}\right. $$ 其中 $s_i$ 表示与空袭 $i$ 相邻的两个边的状态。 模拟一下可以发现，如果要反转边 $[l, r]$，首先我们可以分类讨论出 $a_l$ 和 $a_{r+1}$ 的变化，其次 $a_{l+1}\dots a_r$ 都会变成它的相反数。 考虑询问。如果在两个相邻的山峰（$a_i=+\infty,s_i = \texttt{/\\}$）间扔球，那么这些球都有相同的归宿。所以答案为 $[l-1, r]$ 中相邻的两个 $+\infty$ 的下标差的最大值。 写一颗 5KB 线段树即可。 在查询之前我们可以先将 $a_{l-1}$ 和 $a_r$ 设成 $+\infty$。显然现在我不知道当时我这么写的原因了，反正这样写能烧掉很多特判。
正在渲染内容...
点赞
0
收藏
0
