线段树 - Page 4

「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日6,738线段树,离线处理

「BZOJ2212」[POI2011] Tree Rotations
DescriptionByteasarthegardenerisgrowingararetreecalledRotatusInformatikus.Ithassomeinterestingfeatures:Thetreeconsistsofstraightbranches,bifurcationsandleaves.Thetrunkstemmingfromthegroundisalsoabranch.Eachbranchendswitheitherabifurcationoraleafonitstopend.Exactlytwobranchesforkoutfromabifurcationattheendofabranch-theleftbranchandtherightbranch.Eachleafofthetreeislabelledwithanintegerfro...
02014年8月25日5,034线段树
「ch52」还教室
还教室还记得NOIP2012提高组Day2中的借教室吗?时光飞逝,光阴荏苒,两年过去了,曾经借教室的同学们纷纷归还自己当初租借的教室。请你来解决类似于借教室的另一个问题。「问题描述」在接受借教室请求的n天中,第i天剩余的教室为ai个。作为大学借教室服务的负责人,你需要完成如下三种操作共m次:1第l天到第r天,每天被归还d个教室。2询问第l天到第r天教室个数的平均数。3询问第l天到第r天教室个数的方差。「输入格式」第一行包括两个...
12014年8月18日4,213线段树
「NOIP模拟赛by wulala」公主的朋友
出题人说：正解分块。。。但是这不是和某次cf的dzylovescolor一样么TT修改的时候顺便查询，如果要修改的这一段宗教相同，打个标记并且统计答案后return否则递归复杂度我们可以这样想因为如果修改1-n,但是宗教都不同，这样是每个都要递归到最下面，这样一次修改就要nlogn但是这种情况并不会一直出现，询问完后1-n会被修改成同一种宗教，再把1-n变成不同的，又要额外修改n次也就是说，每次修改，最多让后面的查询多一个logn所以这样...
02014年8月16日2,595线段树
「BZOJ1576」[Usaco2009 Jan] 安全路经Travel
DescriptionInput*第一行:两个空格分开的数,N和M*第2..M+1行:三个空格分开的数a_i,b_i,和t_iOutput*第1..N-1行:第i行包含一个数:从牛棚_1到牛棚_i+1并且避免从牛棚1到牛棚i+1最短路经上最后一条牛路的最少的时间.如果这样的路经不存在,输出-1.SampleInput45122132344321243输入解释:跟题中例子相同SampleOutput336输出解释:跟题中例子相同题解首先用dijkstra得出最短路径树然后我的做法是树链剖分+线段树对于一条不在最...
12014年8月7日6,362线段树,树链剖分
「BZOJ2304」[APIO2011] 寻路path
DescriptionTooDee是一块二维格子状的土地（就像著名的笛卡尔坐标系那样），在这里生活着很多可爱的Dee。Dee是像蜜蜂一样的小动物，它们只在二维活动，而且它们非常的文明开化。TooDee的蜂窝和正常世界的蜂窝也是很不一样的，它们是矩形的且它们的边平行于TooDee的地理坐标系，就是说矩形的边或者是东西走向，或者是南北走向。因为Dees是很高级的生物，它们有很多固定的飞行轨道，这些轨道由一些平行于坐标轴的线段组成，...
02014年8月5日6,723模拟,spfa,dijkstra,线段树
「POJ3321」Apple Tree
DescriptionThereisanappletreeoutsideofkaka'shouse.Everyautumn,alotofappleswillgrowinthetree.Kakalikesappleverymuch,sohehasbeencarefullynurturingthebigappletree.ThetreehasNforkswhichareconnectedbybranches.Kakanumberstheforksby1toNandtherootisalwaysnumberedby1.Appleswillgrowontheforksandtwoapplewon'tgrowonthesamefork.kakawantstoknowhowmanyapplesarethereinasub-tree,forhisstudyoftheproduceabi...
02014年8月1日6,466dfs序,线段树
NOI2007项链工厂
Description Input输入文件第一行包含两个整数N,c，分别表示项链包含的珠子数目以及颜色数目。第二行包含N个整数，x1,x2…,xn，表示从位置1到位置N的珠子的颜色，1≤xi≤c。第三行包含一个整数Q，表示命令数目。接下来的Q行每行一条命令，如上文所述。Output对于每一个C和CS命令，应输出一个整数代表相应的答案。SampleInput53123214CR2P552CS41SampleOutput41HINT 对于60%的数据，N≤1000，Q≤1000...
02014年7月31日5,132线段树
「BZOJ2733」[HNOI2012] 永无乡
Description永无乡包含n座岛，编号从1到n，每座岛都有自己的独一无二的重要度，按照重要度可以将这n座岛排名，名次用1到n来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛a出发经过若干座（含0座）桥可以到达岛b，则称岛a和岛b是连通的。现在有两种操作：Bxy表示在岛x与岛y之间修建一座新桥。Qxk表示询问当前与岛x连通的所有岛中第k重要的是哪座岛，即所有与岛x连通的岛中重要度排名第k小的岛是哪座...
12014年7月31日7,589线段树
「BZOJ1645」[Usaco2007 Open] City Horizon 城市地平线
DescriptionFarmerJohnhastakenhiscowsonatriptothecity!Asthesunsets,thecowsgazeatthecityhorizonandobservethebeautifulsilhouettesformedbytherectangularbuildings.TheentirehorizonisrepresentedbyanumberlinewithN(1<=N<=40,000)buildings.Buildingi'ssilhouettehasabasethatspanslocationsA_ithroughB_ialongthehorizon(1<=A_i<B_i<=1,000,000,000)andhasheightH_i(1<=H_i<=1,000,000,...
32014年7月28日4,597线段树
「BZOJ1672」[Usaco2005 Dec] Cleaning Shifts 清理牛棚
DescriptionFarmerJohn'scows,pamperedsincebirth,havereachednewheightsoffastidiousness.Theynowrequiretheirbarntobeimmaculate.FarmerJohn,themostobligingoffarmers,hasnochoicebuthiresomeofthecowstocleanthebarn.FarmerJohnhasN(1<=N<=10,000)cowswhoarewillingtodosomecleaning.Becausedustfallscontinuously,thecowsrequirethatthefarmbecontinuouslycleanedduringtheworkday,whichrunsfromsecondnumbe...
02014年7月28日4,917递推与动规,线段树
「CF444C」DZY Loves Colors
DZYlovescolors,andheenjoyspainting.Onacolorfulday,DZYgetsacolorfulribbon,whichconsistsof n units(theyarenumberedfrom 1 to n fromlefttoright).Thecolorofthe i-thunitoftheribbonis i atfirst.Itiscolorfulenough,butwestillconsiderthatthecolorfulnessofeachunitis 0 atfirst.DZYlovespainting,weknow.Hetakesupapaintbrushwithcolor x andusesittodrawalineontheribbon.Insuchacasesomecont...
02014年7月28日3,784线段树