数据结构 - Page 18

「BZOJ3551」[ONTAK2010] Peaks加强版
Description「题目描述」同3545Input第一行三个数N，M，Q。第二行N个数，第i个数为h_i接下来M行，每行3个数abc，表示从a到b有一条困难值为c的双向路径。接下来Q行，每行三个数vxk，表示一组询问。v=vxorlastans，x=xxorlastans，k=kxorlastans。如果lastans=-1则不变。Output同3545HINT「数据范围」同3545题解本题强制在线。。。据出题人的做法。。。就是做最小生成树，但合并两结点x，y的时新建结点ext，把ext连向fa...
22014年8月30日9,433kruskal,主席树

「BZOJ3545」[ONTAK2010] Peaks
Description在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。Input第一行三个数N，M，Q。第二行N个数，第i个数为h_i接下来M行，每行3个数abc，表示从a到b有一条困难值为c的双向路径。接下来Q行，每行三个数vxk...
22014年8月26日7,526线段树,离线处理
「BZOJ2212」[POI2011] Tree Rotations
DescriptionByteasarthegardenerisgrowingararetreecalledRotatusInformatikus.Ithassomeinterestingfeatures:Thetreeconsistsofstraightbranches,bifurcationsandleaves.Thetrunkstemmingfromthegroundisalsoabranch.Eachbranchendswitheitherabifurcationoraleafonitstopend.Exactlytwobranchesforkoutfromabifurcationattheendofabranch-theleftbranchandtherightbranch.Eachleafofthetreeislabelledwithanintegerfro...
02014年8月25日6,098线段树
「BZOJ3224」JoyOI 1728 普通平衡树
Description您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：1.插入x数2.删除x数(若有多个相同的数，因只删除一个)3.查询x数的排名(若有多个相同的数，因输出最小的排名)4.查询排名为x的数5.求x的前驱(前驱定义为小于x，且最大的数)6.求x的后继(后继定义为大于x，且最小的数)Input第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)Output对于操作3,4,5,...
52014年8月23日24,020treap
「ch52」还教室
还教室还记得NOIP2012提高组Day2中的借教室吗?时光飞逝,光阴荏苒,两年过去了,曾经借教室的同学们纷纷归还自己当初租借的教室。请你来解决类似于借教室的另一个问题。「问题描述」在接受借教室请求的n天中,第i天剩余的教室为ai个。作为大学借教室服务的负责人,你需要完成如下三种操作共m次:1第l天到第r天,每天被归还d个教室。2询问第l天到第r天教室个数的平均数。3询问第l天到第r天教室个数的方差。「输入格式」第一行包括两个...
12014年8月18日4,570线段树
善良的hzwer
同公主的工作由于本题难度太高，善良的hzwer说：“为了方便旅客串门，还是将他们的房间安排为相邻的一排为好233。”对于每一天输出一行依次代表选取的房间高度,房间必须相邻,若不能安排则输出Impossible。(为了减少输出所需时间，只需输出第一个数即可)因为在做wulala的神模拟赛的时候题目看错了就出了这么一题TT做法是求出每个点为开头向后的连续上升序列长度然后可以搞一个答案数组TT，比如以字典序最小的数x1开头的长度为a...
02014年8月17日3,265贪心,单调栈
「NOIP模拟赛by wulala」公主的朋友
出题人说：正解分块。。。但是这不是和某次cf的dzylovescolor一样么TT修改的时候顺便查询，如果要修改的这一段宗教相同，打个标记并且统计答案后return否则递归复杂度我们可以这样想因为如果修改1-n,但是宗教都不同，这样是每个都要递归到最下面，这样一次修改就要nlogn但是这种情况并不会一直出现，询问完后1-n会被修改成同一种宗教，再把1-n变成不同的，又要额外修改n次也就是说，每次修改，最多让后面的查询多一个logn所以这样...
02014年8月16日2,970线段树
「BZOJ1058」[ZJOI2007] 报表统计
Description小Q的妈妈是一个出纳，经常需要做一些统计报表的工作。今天是妈妈的生日，小Q希望可以帮妈妈分担一些工作，作为她的生日礼物之一。经过仔细观察，小Q发现统计一张报表实际上是维护一个非负整数数列，并且进行一些查询操作。在最开始的时候，有一个长度为N的整数序列，并且有以下三种操作：INSERTik在原数列的第i个元素后面添加一个新元素k；如果原数列的第i个元素已经添加了若干元素，则添加在这些元素的最后...
12014年8月14日5,266STL
「BZOJ3192」[JLOI2013] 删除物品
Description箱子再分配问题需要解决如下问题：（1）一共有N个物品，堆成M堆。（2）所有物品都是一样的，但是它们有不同的优先级。（3）你只能够移动某堆中位于顶端的物品。（4）你可以把任意一堆中位于顶端的物品移动到其它某堆的顶端。若此物品是当前所有物品中优先级最高的，可以直接将之删除而不用移动。（5）求出将所有物品删除所需的最小步数。删除操作不计入步数之中。（6）只是一个比较难解决的问题，这里你只...
02014年8月13日3,222树状数组
「BZOJ3678」wangxz与OJ
Description某天，wangxz神犇来到了一个信息学在线评测系统(OnlineJudge)。由于他是一位哲♂学的神犇，所以他不打算做题。他发现这些题目呈线性排列，被标记为1~n号，每道题都有一个难度值(可以<=0)。他决定与这些题目玩♂耍。1、他可以在某个位置插♂入一些难度值特定的题目。2、他可以吃♂掉(删除)一段题目。3、他可以查询某个位置的题目的难度值。维护一个初始有n个元素的序列(标记为1~n号元素)，支持以下操作：0pab(0<...
32014年8月13日4,573STL
「BZOJ2594」[Wc2006] 水管局长数据加强版
DescriptionSC省MY市有着庞大的地下水管网络，嘟嘟是MY市的水管局长（就是管水管的啦），嘟嘟作为水管局长的工作就是：每天供水公司可能要将一定量的水从x处送往y处，嘟嘟需要为供水公司找到一条从A至B的水管的路径，接着通过信息化的控制中心通知路径上的水管进入准备送水状态，等到路径上每一条水管都准备好了，供水公司就可以开始送水了。嘟嘟一次只能处理一项送水任务，等到当前的送水任务完成了，才能处理下一项。在...
52014年8月13日8,434kruskal,离线处理,link cut tree
「BZOJ1014」[JSOI2008] 火星人prefix
Description火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。比方说，有这样一个字符串：madamimadam，我们将这个字符串的各个字符予以标号：序号：1234567891011字符madamimadam现在，火星人定义了一个函数LCQ(x,y)，表示：该字符串中第x个字符开始的字串，与该字符串中第y个字符开始的字串，两个字串的公共前缀的长度。比方说，LCQ(1,7)=5,LCQ(2,10)=1,LCQ(4,7)=0在研究LCQ函数的过程中，火星人发现了...
42014年8月12日10,437splay,二分法,哈希表