惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
J
Java Code Geeks
I
InfoQ
V
Visual Studio Blog
M
MIT News - Artificial intelligence
H
Help Net Security
博客园_首页
Blog — PlanetScale
Blog — PlanetScale
F
Fortinet All Blogs
Apple Machine Learning Research
Apple Machine Learning Research
人人都是产品经理
人人都是产品经理
G
Google Developers Blog
A
About on SuperTechFans
腾讯CDC
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com
Last Week in AI
Last Week in AI
小众软件
小众软件
aimingoo的专栏
aimingoo的专栏
罗磊的独立博客
大猫的无限游戏
大猫的无限游戏
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
云风的 BLOG
云风的 BLOG
S
SegmentFault 最新的问题
WordPress大学
WordPress大学

某岛

AtCoder Beginner Contest 409 Luogu P5325. 【模板】Min_25 筛 UOJ #188. 【UR #13】Sanrd AtCoder Beginner Contest 371 AtCoder Beginner Contest 369 RPGMaker 2k3 百科 OneShot 的考古 2024“开创拓芯”游戏创享节的相关记录 CJ 回来后的戒断反应 Luogu P10221. [省选联考 2024] 重塑时光 Luogu P5308 [COCI2018-2019#4] Akvizna wqs 二分 歌唱王国 Lean 相关 BZOJ 3153. Sone1 The 2023 ICPC World Finals Luxor 新巴别塔 Sora 的想象与思考 Facebook Hacker Cup 2023 Round 1 AtCoder Beginner Contest 322 LLaMA 2 相关 HuggingFace AI Game Jam ACL 2023 Trans 相关… Luogu P2053. [SCOI2007] 修车 Luogu P1973. [NOI2011] NOI 嘉年华 Luogu P1933. [NOI2010] 旅行路线 Luogu P1954. [NOI2010] 航空管制 Luogu P2048. [NOI2010] 超级钢琴 Luogu P2046. [NOI2010] 海拔
Luogu P4314. CPU 监控
2025-03-14 · via 某岛

March 14, 2025

https://www.luogu.com.cn/problem/P4314

先不考虑赋值操作,先拿个 20 分。

再考虑赋值操作对标记的影响,显然我们不能对每个状态开一个 vector 记录所有历史操作,但我们发现赋值操作可以清空前面的所有历史操作,且之后的加减操作可以和这个赋值操作合并。
因此我们只需要 (a, b) 两个数表示先加再赋值即可描述标记。
再讨论操作,对于加减操作,如果之前存在赋值,我们转化成赋值操作即可。

手写下放标记思路是比较清晰的。
https://www.luogu.com.cn/record/207893466
难点主要是分情况讨论,赋值存在和不存在的情况,如果开 LL 的话还可以用哨兵少开一个数组!

当然我们发现强行套 atc 模板双半群填空大法也是可以的!
https://www.luogu.com.cn/record/208212684

后来经过这个题的启发,我们发现直接用 checkMax 去模拟赋值可能是更好的选择?
https://www.luogu.com.cn/record/208211497

这个写法果然和模板相性更好,不仅不用分情况讨论,合并操作更简洁减少犯错的机会,
而且 checkMax 能模拟 set,反过来却不能,应用范围也更广更强大!

还有一个细节是 op 和 mapp 里是不需要 checkMax(b, a) 的,因为维护标记的过程就隐含了这层逻辑。

Posted by xiaodao
Category: 日常