treap - Page 2 - hzwer.com

「BZOJ1112」[POI2008] 砖块Klo
DescriptionN柱砖,希望有连续K柱的高度是一样的.你可以选择以下两个动作1:从某柱砖的顶端拿一块砖出来,丢掉不要了.2:从仓库中拿出一块砖,放到另一柱.仓库无限大.现在希望用最小次数的动作完成任务.Input第一行给出N,K.(1≤k≤n≤100000),下面N行,每行代表这柱砖的高度.0≤hi≤1000000Output最小的动作次数SampleInput5339231SampleOutput2HINT原题还要求输出结束状态时,每柱砖的高度.本题略去.题解据说有很多做法，...
32014年5月27日6,073treap

「JoyOI1360」Imperishable Shooting
背景Background如果您不想看这个扯淡的背景，可以直接移步Hint，有简洁版。。。一天，蓬莱の魚の形误闯了迷途森林，于是光荣地迷路了。。此时，一个白发红眼的少女出现了。。少女：你迷路了吗？蓬莱の魚の形：。。是。。少女：你叫什么名字？蓬莱の魚の形：蓬莱の魚の形。。少女（仔细打量其一番）：本来还准备帮你的，但是一想到一个妖怪鱼有这个名字。。。就让我看看你有多大本事吧！（突然从背后扇动出熊熊燃烧的翅膀）「Imp...
02014年5月25日5,202treap,几何
「POJ2104」K – th Number
DescriptionYouareworkingforMacrohardcompanyindatastructuresdepartment.Afterfailingyourprevioustaskaboutkeyinsertionyouwereaskedtowriteanewdatastructurethatwouldbeabletoreturnquicklyk-thorderstatisticsinthearraysegment.Thatis,givenanarraya[1...n]ofdifferentintegernumbers,yourprogrammustansweraseriesofquestionsQ(i,j,k)intheform:"Whatwouldbethek-thnumberina[i...j]segment,ifthissegmentwassorted...
02014年5月14日9,133treap,树套树,主席树,线段树
「BZOJ3196」JoyOI 1730 二逼平衡树
Description您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：1.查询k在区间内的排名2.查询区间内排名为k的值3.修改某一位值上的数值4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)5.查询k在区间内的后继(后继定义为大于x，且最小的数)Input第一行两个数n,m表示长度为n的有序序列和m个操作第二行有n个数，表示有序序列下面有m行，opt表示操作标号若opt=1则为操作1，之后有三个数l,r,k表...
02014年4月20日11,415treap,树套树,线段树
「zoj2112」Dynamic Rankings
TheCompanyDynamicRankingshasdevelopedanewkindofcomputerthatisnolongersatisfiedwiththequeryliketosimplyfindthek-thsmallestnumberofthegivenNnumbers.TheyhavedevelopedamorepowerfulsystemsuchthatforNnumbersa[1],a[2],...,a[N],youcanaskitlike:whatisthek-thsmallestnumberofa[i],a[i+1],...,a[j]?(Forsomei<=j,0<k<=j+1-ithatyouhavegiventoit).Morepowerful,youcanevenchangethevalueofsomea[i],an...
52014年4月20日6,626树套树,treap,线段树
「BZOJ1691」[Usaco2007 Dec] 挑剔的美食家
Description与很多奶牛一样，FarmerJohn那群养尊处优的奶牛们对食物越来越挑剔，随便拿堆草就能打发她们午饭的日子自然是一去不返了。现在，FarmerJohn不得不去牧草专供商那里购买大量美味多汁的牧草，来满足他那N(1<=N<=100,000)头挑剔的奶牛。所有奶牛都对FJ提出了她对牧草的要求：第i头奶牛要求她的食物每份的价钱不低于A_i(1<=A_i<=1,000,000,000)，并且鲜嫩程度不能低于B_i(1<=B_i<=1,000,000...
02014年4月3日4,938treap
「BZOJ1588」[HNOI2002] 营业额统计
Description营业额统计Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理...
32014年3月28日8,587treap,splay,链表
「BZOJ1862 / 1056」GameZ游戏排名系统
DescriptionGameZ为他们最新推出的游戏开通了一个网站。世界各地的玩家都可以将自己的游戏得分上传到网站上。这样就可以看到自己在世界上的排名。得分越高，排名就越靠前。当两个玩家的名次相同时，先上传记录者优先。由于新游戏的火爆，网站服务器已经难堪重负。为此GameZ雇用了你来帮他们重新开发一套新的核心。排名系统通常要应付三种请求：上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当...
02014年2月25日5,974treap,哈希表
NOI2004郁闷的出纳员
输入描述 InputDescription第一行有两个非负整数n和min。n表示下面有多少条命令，min表示工资下界。接下来的n行，每行表示一条命令。命令可以是以下四种之一：名称格式作用I命令I_k新建一个工资档案，初始工资为k。如果某员工的初始工资低于工资下界，他将立刻离开公司。A命令A_k把每位员工的工资加上kS命令S_k把每位员工的工资扣除kF命令F_k查询第k多的工资_（下划线）表示一个空格，I命令、A命令、S命令中的k是一个...
82013年12月26日13,520treap,splay,线段树
「POJ2892」Tunnel Warfare
DescriptionDuringtheWarofResistanceAgainstJapan,tunnelwarfarewascarriedoutextensivelyinthevastareasofnorthChinaPlain.Generallyspeaking,villagesconnectedbytunnelslayinaline.Exceptthetwoattheends,everyvillagewasdirectlyconnectedwithtwoneighboringones.Frequentlytheinvaderslaunchedattackonsomeofthevillagesanddestroyedthepartsoftunnelsinthem.TheEighthRouteArmycommandersrequestedthelatest...
02013年12月25日4,300treap