树套树 - hzwer.com

「省选模拟赛」小奇的花园
原题：「泉七培训-刘定峰」花园「题目背景」小奇在家中的花园漫步时，总是会思考一些奇怪的问题。「问题描述」小奇的花园有n个温室，标号为1到n，温室以及以及温室间的双向道路形成一棵树。每个温室都种植着一种花，随着季节的变换，温室里的花的种类也在不断发生着变化。小奇想知道从温室x走到温室y的路径中(包括两个端点),第t种花出现的次数。「输入格式」第一行为两个整数n，q，表示温室的数目和操作的数目。第二行有n个整数T1...
62015年12月19日9,718treap,STL,树套树,线段树,树链剖分

「BZOJ3110」[ZJOI2013] K大数查询
Description有N个位置，M个操作。操作有两种，每次操作如果是1abc的形式表示在第a个位置到第b个位置，每个位置加入一个数c如果是2abc形式，表示询问从第a个位置到第b个位置，第C大的数是多少。Input第一行N，M接下来M行，每行形如1abc或2abcOutput输出每个询问的结果SampleInput2511211122211221112123SampleOutput121HINTN,M<=50000,N,M<=50000a<=b<=N1操作中abs(c)<=N2操作中abs(c)<=M...
272014年10月8日24,700树套树,线段树
「BZOJ3065」带插入区间K小值
Description从前有n只跳蚤排成一行做早操，每只跳蚤都有自己的一个弹跳力a[i]。跳蚤国王看着这些跳蚤国欣欣向荣的情景，感到非常高兴。这时跳蚤国王决定理性愉悦一下，查询区间k小值。他每次向它的随从伏特提出这样的问题:从左往右第x个到第y个跳蚤中，a[i]第k小的值是多少。这可难不倒伏特，他在脑袋里使用函数式线段树前缀和的方法水掉了跳蚤国王的询问。这时伏特发现有些跳蚤跳久了弹跳力会有变化，有的会增大，有的会减少。这...
142014年9月30日28,795树套树,可持久化线段树,替罪羊树
「BZOJ3262」陌上花开
Description有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。Input第一行为N,K(1<=N<=100,000,1<=K<=200,000),分别表示花的数量和最大属性值。以下N行，每行三个整数...
02014年6月19日9,468树套树,treap,树状数组
「BZOJ3295」[CQOI2011] 动态逆序对
Description对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。Input输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。Output输出包含m行，依次为删除每个元素之前，逆序对...
42014年6月17日8,262树套树,线段树,树状数组
「BZOJ1146」[CTSC2008] 网络管理Network
DescriptionM公司是一个非常庞大的跨国公司，在许多国家都设有它的下属分支机构或部门。为了让分布在世界各地的N个部门之间协同工作，公司搭建了一个连接整个公司的通信网络。该网络的结构由N个路由器和N-1条高速光缆组成。每个部门都有一个专属的路由器，部门局域网内的所有机器都联向这个路由器，然后再通过这个通信子网与其他部门进行通信联络。该网络结构保证网络中的任意两个路由器之间都存在一条直接或间接路径以进行通...
22014年6月13日7,679treap,树套树,二分法,线段树,树链剖分
「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,070树套树,treap,主席树,线段树
「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,345treap,树套树,线段树
「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,588树套树,treap,线段树