范浩强_wc2012谈谈各种数据结构

——从大象讲起说说各种数据结构。范浩强自我介绍？●略吧。先从大象说起。●先不着急说数据结构的事。●先从大象那天说起。●23rdIOIDay2和动物在一起的一天。●鳄鱼crocodile●大象elephant●鹦鹉parrot“”最简单的鹦鹉。●“”为什么说是最简单呢？因为用到的数据结构只有数组。●“”为什么要给简单加引号呢？因为它并不简单。鹦鹉。●你有一群鹦鹉。每个鹦鹉可以记住8个二进制位，即，一个0～255之间的自然数。●你告诉了一些鹦鹉一些数，之后，让它们飞到另一个人那里。每个鹦鹉忠实地告诉了那个人（接收者）它记住的数是多少。●你想通过这个方法传递一个消息。但是，鹦鹉有个小问题，就是鹦鹉到达的顺序是随机的。鹦鹉。●例如：●你发送了3只鹦鹉：●1998●到达接收者那里很可能变成了：●9819●你要在这种状况下，通过发送最少个数的鹦鹉来传递消息。消息可以视作一个N位的二进制数。鹦鹉？●这题出得不错。。。但是，怎么做呢？●主要矛盾：乱序到达？●●想法1：每个鹦鹉记住自己是第几个（发送位置码）。●每个鹦鹉记住一个数4x+y，其中y表示一个2位的消息(0/1/2/3)，x表示这个消息在原文中的位置。鹦鹉。●0131●=051113●到达接收者那里之后●513011●接收者把它们从小到大排序●051113●之后分别模4●0131，很神奇吧。。。嗯，很和谐。●通过这种方法最长能发送多长的消息呢？●X的取值是[0,64)，能最多标记64个位置，每个位置2位，所以最长128位，即16字节。●如果要发送N个字节（8N位）的消息，要用4N个鹦鹉。●这么做有多少分？●子任务1，2：很水，一共32分。●子任务3（18分）●N=16●鹦鹉数不超过10N●哈哈，一共50分到手了！鹦鹉？。●子任务4（29分）●1=N=32●最多发送10N只鹦鹉。●这个怎么办？●如果延续上面的思路，能否不用6个位来标识位置，而是用使用更多/更少的位来编码位置信息？但是。●计算一下各种情况下发送的最大长度。●0个位置码，1*8=8●1个位置码，2*7=14●2个位置码，4*6=24●3个位置码，8*5=40●4个位置码，16*4=64●5个位置码，32*3=96●6个位置码，64*2=128●7个位置码，128*1=128（囧了！）鹦鹉！。●于是，要另辟蹊径。●重新想想，接收者得到的信息的本质是什么？●21330●接收者：我得到了1“只说0”的鹦鹉，1“只说1”的鹦鹉，1“只说2”的鹦鹉，2“只说3”的鹦鹉，没有其他的鹦鹉了。●-1112000...repeat252times...0●发送的信息的本质是一个unsignedint[256]！●使用的鹦鹉数=数组里的元素之和啊哈！●我有想法了。●把0~255视作256个频道。派出一个说x的鹦鹉-在频道x上发送1。●'ac'(0110000101100011)●-015681314●这样，不就可以发送256位的信息了？最多使用256只鹦鹉！相当和谐。●一共79分到手了。●还有哪里可以改进呢？●●●我干嘛在1个频道上只发送1只鹦鹉呢？相当和谐。●一共79分到手了。●还有哪里可以改进呢？●●●我干嘛在1个频道上只发送1只鹦鹉呢？鹦鹉！。●想象：在3个频道上发送2只鹦鹉，一共有10种方法。●000●100●010●001●200●020●002●110●101●011●鹦鹉。●每组频道可以表示一个10进制位，我一共可以用最多170只鹦鹉发送85组频道，即85个十进制位，即282个2进制位。●●很好！不光鹦鹉用得少，消息也传得长了。再接再厉！。●4个频道一组，每组发送最多7只鹦鹉●一组有330种方法，可以用来编码一个字节。●一共可以发送64字节，使用鹦鹉数是7N●●子任务4：●N=64P=鹦鹉数/N分数519618717(哈哈，98分了）1531-2P剩下2分怎么办？●8个频道一组，发送11只鹦鹉，一共75582种方法，编码16个位，鹦鹉数/N=5.5。可以用bfs来产生各种方法。●如何满分？●16个频道一组，发送20只鹦鹉，一共7307872110种方法，可以编码32位，鹦鹉数/N=5●但是，只能用动态规划来编码，没法bfs，来不及写了。。。●这样，我就得了99分。。。最牛可以做到多少？●在256个频道上发送261只鹦鹉，方法数是●14689679228817090027688619639369503254590081548750394350441345795303638440595551569047171502630421770738179391387144426481189233947735091485000102045969606●可以编码64个字节●鹦鹉数/N=4.078125●嗯，很好，很好。。。啊，鹦鹉可算做完了。●鳄鱼？●●一只阻拦你出去的鳄鱼，每次会智能地挡在你的一条出路上，让你到达出口的时间最长。鳄鱼嗯，这题是不是我们已经见过了？。●前一阵子的集训。。。●老虎的故事。。。●●解法简述：●扩展的Dijkstra，每个点记录最近的两条边，每次挑一个第2短路最短的进行扩展。●●程序很短。。。（感谢STL的priority_queue）主角登场了：大象！●你见过大象跳舞吗？（我在泰国见过。。。）●你见过N只大象在数轴上跳舞，有若干范围为L的摄像机拍摄它们吗？（这个真没有。。。）●你见过还有人想知道最少用多少个摄像机来覆盖所有的大象的吗？（只有题里有这种人。。。）吓一跳。●大象数有多少？●最多15万。●数轴有多长？●最长10亿（大象在整点上）。●●如果真有那么多大象在一起，这将是一场灾难。。。灾难？在后面。●可怕的是，这些大象还在移动！每个时刻，一个大象从一个位置x跑到位置y。●更可怕的是，有一个人，想知道：●每个时刻，最少用多少个摄像机来覆盖所有的大象？冷静一下●让我们先在那些可怕的大象面前做一个深呼吸。●如果大象不动，能否快速求出最小的覆盖数？●●啥？动态规划？动态规划？。。。●先把大象从左到右排序。●设，前i个大象最少用f[i]个摄像机覆盖。考察第i个大象的摄像机覆盖到哪里，有●f[i]=min(f[j]，大象i到大象j的距离不超过L)+1，dp看起来挺傻的。●为什么非要dp呢？●通过dp方程的分析，我们似乎得到了这样一个结论：可以贪心！●每次，找最靠左的没有被覆盖的大象，以它为左端点架一个摄像机。代码很简洁啊。●#A=大象们的位置●s,x=0,-1●foriinsorted(A):●ifix:●s,x=s+1,i+L●returns时间复杂度？●不算排序，时间复杂度是O(N)，常数很小。●如果每次移动都排序一遍，那么时间复杂度是O(NlogN*M)，M是移动次数●很显然，我们可以第一次的时候排序，以后每次移动的时候冒泡一下。●时间复杂度是O(NlogN+NM)●嗯，有多少分呢？26分。可怜啊。。。NMTask1（10分）2100Task2（16分）100100Task3（24分）5000050000Task4（47分）7000070000Task5（3分，这。。。）150000150000加油！！！●再把问题转化一下。●想想这段代码的意思：●foriinsorted(A):●ifix:●s,x=s+1,i+L●实际上，我们做的工作是：从最左边的大象开始，每次往右跳到L的距离以外最左边的那只大象。答案就是这个链的长度。可以这么搞吗？●multisetintA=大象们●ints=0;●for(multisetint::iteratori=A.begin();i!=A.end();){●s++;●i=A.upper_bound(*i+L);●}●很合理，尤其是当L很大的时候。●但是，不解决本质问题。L很小怎么办？大象？。●“”我们能否维护每个大象的后继呢？即，每个大象后面距离超过L的最近的大象。●似乎可以。●还可以在每个大象上记录它打头的链的长度。●●大象移动了，就去更新它涉及的链。●L很小的时候似乎可行。●但是，链的长度真的很难维护。矛盾啊。●修改：后继关系：L小点好。●查询：从最左边一直往后跳：L大点好。●●于是，我们有超级武器：分块！●●把连续的sqrt(N)个大象分成一组。我是一组大象！我是大象！我是一组大象！我是大象！我们要维护哪些量呢？。每个大象的位置。每个大象在组内的链的长度。每个大象在组内的链的末尾。我是一组大象！我是大象！查询是怎么回事？。从最左边的组的最左边的大象开始。在组内，利用记录的信息直接跳到组的末尾。到下一个组，通过二分查找来计算后继，之“”后接着跳。记录路过的大象的个数=答案。时间复杂度=sqrt(N)logN我是一组大象！我是大象！修改是怎么回事？修改=插入+删除找到大象所在的组。用线性的时间更新每个大象的后继，计算链长、链尾。问题是，组的大小不再是sqrt(N)了！怎么办？如果一个组的大小超过2sqrt(N)-分裂成两个。如果相邻两个组的大小和不超过sqrt(N)-合并成一个。可以证明，每个组的大小、组数都是O(sqrt(N))，而每sqrt(N)次操作才会引发一次合并/分裂。一次合并、分裂的时间复杂度是O(sqrt(N))，均摊下来就是O(1)。能不能不写分裂/合并？。●可以啊！●●每sqrt(N)次操作之后，销毁整个数据结构，重新构建一次！●●均摊-O(sqrt(N))总的时间复杂度●查找：O(logNsqrt(N))●更新：O(sqrt(N))●嗯，其实可以每sqrt(NlogN)个大象一段，这样时间复杂度可以更好。。。●●这就满分啦。●●但，这就结束了吗？一个想法。●我们能否做到O(logN)呢？●●这是一个很自然的想法。有了！。●我们要维护每个点往后L个距离的后继。●L的距离，后继，这两个关系放在一起就费劲了。●能否转化成要么是L的距离，要么是后继？●●要请鹦鹉来帮忙啦！我在每个大象后面L的位置设置一个鹦鹉。每个大象连一条边到它对应的鹦鹉。每只鹦鹉连一条边到它后面紧跟着的动物（可以是鹦鹉，也可以是大象）。最小摄像机数=最左边的大象所在的链内大象的个数。我在每个大象后面L的位置设置一个鹦鹉。每个大象连一条边到它对应的鹦鹉。每只鹦鹉连一条边到它后面紧跟着的动物（可以是鹦鹉，也可以是大象）。最小摄像机数=最左边的大象所在的链内大象的个数。一个2N个点，2N-1条边的图●树！。●没错，这些动物形成了一个树。还是一个有根树，从左边指向右边。●每次查询，我们的工作：●询问从一个点到树根的路径上大象的个数。●这。。。好熟悉的模型。先说说修改怎么办●修改=插入+删除●插入：●同时插入一对鹦鹉和大象。用一个set来维护所有的动物的位置。设置大象的后继为鹦鹉，利用lower_bound查找鹦鹉的后继，同时，看看它是否修改了其他鹦鹉的后继。●删除：●把一个大象变成鹦鹉即可！多来几只鹦鹉并无大碍！。树啊。●问题已经长到树上了。●●维护一个树，支持以下操作（O(logN)每次）。●插入一个点。●修改一个点的父亲。●修改一个点上的权值。●查询一个点到根的路径上的权值和。这好像叫：动态树！●啥是动态树？定义请自己google/baidu/bing●●有一种动态树的实现，叫link-cuttree。●●似乎以前已经有人讲过了吧？核心思想：把树剖分成若干个链。链与链之间通过父子关系相连。每个链用一个数据结构来维护，同时记录链上点的权值和。查询一个点：把这个点到根的路径用一条链连接起来，在链上查询（途中要进行链的拆分、连接）。修改一个点的权值：同理。修改一个点的父亲：把它所在的链断开，之后设置新的父亲。链？时间复杂度？。●用什么数据结构来维护链呢？。●不妨用splay吧。●时间复杂度呢？●有的论文说，是O(logN)。●●啥？你说这篇论文是错的？不能用splay来维护？●那你再换篇论文看看。●不管是不是真的O(logN)，反正我用了。嗯，要开始说数据结构了！●啥叫数据结构呢？●下定义是一个痛苦的事情。●●我们生活在数据结构的世界里。●随机存取线性表（数组,ve