UOJ Logo wangyisong1996的博客

博客

想要找到最快的模板吗?欢迎来体验评测鸭在线!

2018-07-16 14:42:23 By wangyisong1996

值此NOI来临之际,我们优化了评测鸭在线 https://duck.ac/ 的各方面体验:

  • 支持了多个测试点的传统题评测,包括测试点等分和子任务模式。
  • 测试点太多?现在加入了多台评测鸭,可以同时对一个提交记录进行评测。
  • 新增了若干传统题和模板题,更多的题目也在路上了。感谢UOJ对评测鸭的大力支持!
  • 想找到一份跑得最快的模板吗?来围观各个题目的排行榜吧!我们的测量最高精确到微秒
  • 加入NOI2017的全部题目(真的吗?)
  • 想背笔试却不知怎么办?来体验被鄙视(划掉)笔试的小功能吧!

鼓掌熊

欢迎积极到评测鸭用户群(群号 781384211)反馈使用体验,你的一份支持将是我们最大的动力!也欢迎来 GitHub 围观我们的开源仓库,提提 Issue 和 PR,详见 https://github.com/JudgeDuck

妈妈我终于会DFT和FFT了!(雾)

2017-11-24 19:41:05 By wangyisong1996

UNR #1 火车管理 的一个简单做法

2016-07-18 17:29:00 By wangyisong1996

题面:http://uoj.ac/contest/32/problem/218

题意

有$n$个栈,区间压数,单点弹栈,求区间栈顶和。

线段树

看到此类区间修改,区间询问的题目,我们很容易想到线段树这样的数据结构。

我们可以通过对线段树打标记来实现区间修改。在访问线段树的每个结点时,我们还需要进行标记下传

这种做法要求标记能快速合并,并且有结合律

标记

这题的修改操作为“区间压数”,即对区间的每个栈压一个数进去。 所以我们可以考虑用一个序列来表示标记,该标记的意思为对于这个线段树区间里的每个栈,都要将这个序列按顺序压进去。 于是合并两个标记的时候就只要将这两个序列连接(join)。

在区间压数操作中,我们找到对应的区间后,给该区间打上一个只有一个元素的序列的标记。

在单点弹栈操作中,我们将跟该点有关的标记全部下传之后,需要将该点的标记里的序列中第一个数删掉(即“弹栈”),并更新该点的答案。

由于有询问区间和的操作,我们在线段树上还需要维护区间和,只要在标记下传的时候维护即可。

“序列”

除了需要维护一个“序列”以外,线段树上所有操作的复杂度都是$O(\log n)$的。

这个序列需要支持:

  1. 生成一个只有一个元素的序列;
  2. 将两个序列连接;
  3. 删除某个序列的第一个元素。

以上操作都要求完全可持久化

在一次题目的操作中,会有至多$\lceil 2 \log n \rceil$次序列连接操作,和至多一次生成序列或者删除第一个元素的操作。

平衡树

我们可以使用可持久化平衡树(如AVL或treap)来维护这些序列,复杂度为严格或期望$O(\log n)$单次序列操作。

这样题目中每次操作的复杂度为$O(\log ^ 2 n)$,并不是很优美,而且平衡树常数很大,代码也很难写……

二叉树

我们可以用一种不知名的二叉树来维护这个序列。

对于一个长度为$k$的序列,对应的二叉树上有$2k-1$个结点,其中根节点的值为该序列的第一个元素的值。

我们可以这样递归定义这种二叉树以及其连接操作:

  1. 基础:$k = 1$时,二叉树上只有一个结点,该结点的值为序列中唯一一个元素的值。
  2. 归纳:将两个长度分别为$n$和$m$的序列$a$和$b$连接起来时,我们新建一个结点,该结点的值为$a$中第一个元素的值(即,$a$对应二叉树的根节点的值),左儿子和右儿子分别为$a$和$b$对应二叉树的根节点。

可以证明这样构造的二叉树满足其定义。

在序列中删除第一个元素的时候,我们从根开始,一直向左走直到叶结点,则这个叶结点一定表示序列中第一个元素。

我们将这个叶结点的父结点替换为这个叶结点的父结点的右儿子,并更新父结点到根路径上的每个结点的值。

对于该叶结点没有父结点的情况,说明是只有一个元素的序列,直接返回空树即可。

复杂度分析:

生成序列、序列连接都是$O(1)$的,删除第一个元素是$O(表示序列中第一个元素的结点的深度)$的。

注意到在线段树上,打标记会使该深度变为1或2,每次标记下传会使该深度加一。

由于线段树的深度不超过$\lceil \log n \rceil$,所以该深度不会超过$\lceil \log n \rceil + 1$。

另外注意到每个元素的深度可以单独分析,于是在删除了第一个元素后,第二个元素的深度也满足上述条件

所以删除第一个元素的复杂度为$O(\log n)$。

综上,这个做法在题目中单次操作的复杂度为$O(\log n)$,可以AC此题。

总结

用带标记的线段树这一经典数据结构和二叉树的有关知识,给出了一个简单的算法, 然后通过观察线段树标记下传的性质,证明该算法的复杂度为每次操作$O(\log n)$。

祝大家新年快乐!

2016-01-01 07:04:37 By wangyisong1996

...妈妈我终于会做未来程序·改了

2015-06-17 23:39:41 By wangyisong1996

...妈妈我终于会做未来程序·改了!

$ $

然而代码有102557B,交不上来

UPD: RE了,大家再见

UPD: A掉辣

http://uoj.ac/submission/20545

wangyisong1996 Avatar