线段树 - Page 6

「BZOJ3585」mex
Description　　有一个长度为n的数组{a1,a2,...,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。Input　　第一行n,m。第二行为n个数。从第三行开始，每行一个询问l,r。Output　　一行一个数，表示每个询问的答案。SampleInput55210213323241235SampleOutput12303HINT数据规模和约定对于100%的数据：1<=n,m<=2000000<=ai<=1091<=l<=r<=n对于30%的数据：1<=n,m<=1000Source此题为...
02014年5月18日7,156线段树,离线处理

「BZOJ3339」Rmq Problem
DescriptionInputOutputSampleInput7502101321323143627SampleOutput30324HINT题解这一题在线似乎比较麻烦至于离线。。首先按照左端点将询问排序然后一般可以这样考虑首先如何得到1-i的sg值呢这个可以一开始扫一遍完成接着考虑l-r和l+1-r的答案有何不同显然是l-next[l]-1这一段所有sg值大于a[l]的变为a[l]这一步如果暴力修改的话只有30分但是修改区间我们可以想到线段树，这样就能a了[crayon-676d57efdc809175980219/]&...
12014年5月17日8,586线段树,离线处理
「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,147treap,树套树,主席树,线段树
「BZOJ1593」[Usaco2008 Feb] Hotel 旅馆
Description奶牛们最近的旅游计划，是到苏必利尔湖畔，享受那里的湖光山色，以及明媚的阳光。作为整个旅游的策划者和负责人，贝茜选择在湖边的一家著名的旅馆住宿。这个巨大的旅馆一共有N(1<=N<=50,000)间客房，它们在同一层楼中顺次一字排开，在任何一个房间里，只需要拉开窗帘，就能见到波光粼粼的湖面。贝茜一行，以及其他慕名而来的旅游者，都是一批批地来到旅馆的服务台，希望能订到D_i(1<=D_i<=N)间连续的...
12014年5月6日5,410线段树
「BZOJ3212」Pku3468 A Simple Problem with Integers
DescriptionYouhaveNintegers,A1,A2,...,AN.Youneedtodealwithtwokindsofoperations.Onetypeofoperationistoaddsomegivennumbertoeachnumberinagiveninterval.Theotheristoaskforthesumofnumbersinagiveninterval. InputThefirstlinecontainstwonumbersNandQ.1≤N,Q≤100000.ThesecondlinecontainsNnumbers,theinitialvaluesofA1,A2,...,AN.-1000000000≤Ai≤1000000000.EachofthenextQlinesreprese...
32014年4月30日4,173线段树
「BZOJ1858」[SCOI2010] 序列操作
Descriptionlxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作：0ab把[a,b]区间内的所有数全变成01ab把[a,b]区间内的所有数全变成12ab把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成03ab询问[a,b]区间内总共有多少个14ab询问[a,b]区间内最多有多少个连续的1对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗...
02014年4月29日5,259线段树
「BZOJ1984」月下“毛景树”
Description毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬~~毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~~~“毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数：Changekw：将第k条树枝上毛毛果的...
02014年4月29日6,169线段树,树链剖分
「CF413E」Maze 2D
ThelastproductoftheR2companyinthe2Dgames'fieldisanewrevolutionaryalgorithmofsearchingfortheshortestpathina 2 × nmaze.Imagineamazethatlookslikea 2 × n rectangle,dividedintounitsquares.Eachunitsquareiseitheranemptycelloranobstacle.Inoneunitoftime,apersoncanmovefromanemptycellofthemazetoanyside-adjacentemptycell.Theshortestpathproblemisformulatedasfollows.Giventwofreemazecells,younee...
42014年4月24日4,469线段树
「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,425treap,树套树,线段树
「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,634树套树,treap,线段树
「BZOJ2243」[SDOI2011] 染色
Description给定一棵有n个节点的无根树和m个操作，操作有2类：1、将节点a到节点b路径上所有点都染成颜色c；2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。请你写一个程序依次完成这m个操作。 Input第一行包含2个整数n和m，分别表示节点数和操作数；第二行包含n个正整数表示n个节点的初始颜色下面行每行包含两个整数x和y，表示x和y之间有一条无向...
12014年4月8日9,294线段树,树链剖分
「BZOJ1036」[ZJOI2008] 树的统计Count
Description一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作：I.CHANGEut:把结点u的权值改为tII.QMAXuv:询问从点u到点v的路径上的节点的最大权值III.QSUMuv:询问从点u到点v的路径上的节点的权值和注意：从点u到点v的路径上的节点包括u和v本身Input输入的第一行为一个整数n，表示节点的个数。接下来n–1行，每行2个整数a和b，表示节点a和节点b之...
272014年4月6日39,528线段树,树链剖分,link cut tree