洛谷4314 cpu监控

首先我们可以想到一个显而易见的思路:每个节点维护$\mathrm{add,set}$的$tag$,维护最大值$max$和历史最大值$Max$,然后像正常的线段树一样维护

然后你惊讶的发现你只拿到二十分(只有$Q$的部分分)

为什么呢?我们发现有些$tag$,他还没有来得及被更新就被覆盖了..而这些$tag$本来能改变世界更新答案

所以我们可以维护两个$tag$:$\mathrm{Add,Set}$表示该节点从上次下放到目前的最大$add$和$set$值

然后我们就可以快乐的用这些$tag$来维护答案了

CF86D Powerful array

怎么2700的题这么简单啊QAQ

莫队+$bitset$优化

「算法笔记」 莫队

前言

莫队,可是传说中能够解决所有离线区间问题的神奇算法

洛谷 P3950 部落冲突

link-cut tree 板子题

思路:莫队+分块

子树上的查询问题可以通过$DFS$序转换为序列问题

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×