some exercise of persistent data structures

在我CTSC滚粗了之后,本来想天天喝点小酒消消愁的,结果发现还得去ZJOI day2,讲课也已经排好推不掉了…

于是我讲的是可持久化数据结构…

正好把以前想的一些例题贴出来:

1.QTREE的可持久化版本:修改一条边,询问2点间边的最大值,回到第i个操作结束的时候.必须在线

2.n*n的矩阵,每次询问一个子矩形内部第k大的数,n<=100,询问数<=1kw,时限5s.必须在线.

3.SUBSTRING的可持久化版本:给一个串,支持往后+个字符,询问一个串出现次数,回到第i个操作结束的时候,必须在线.
总长度<=20w,操作数<=10w,时限3s.
4.BZOJ 2787

嘛…有时间可以先看看…反正也很sb…到时候也会讲…

13 thoughts on “some exercise of persistent data structures

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>