数据结构 - Page 20

「BZOJ2002」[HNOI2010] Bounce 弹飞绵羊
Description某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任...
102014年7月30日16,340分块,link cut tree

NOI2005维修数列
DescriptionInput输入文件的第1行包含两个数N和M，N表示初始时数列中数的个数，M表示要进行的操作数目。第2行包含N个数字，描述初始时的数列。以下M行，每行一条命令，格式参见问题描述中的表格。Output对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。SampleInput982-6351-5-363GET-SUM54MAX-SUMINSERT83-572DELETE121MAKE-SAME...
252014年7月30日23,574splay
「BZOJ3626」[LNOI2014] LCA
Description给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。有q次询问，每次询问给出lrz，求sigma_{l<=i<=r}dep[LCA(i,z)]。（即，求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和）Input第一行2个整数nq。接下来n-1行，分别表示点1到点n-1的父节点编号。接下来q行，每行3个整数lrz。Output输出q行...
102014年7月28日11,819离线处理,树链剖分
「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,770线段树
「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日5,075递推与动规,线段树
「BZOJ1683」[Usaco2005 Nov] City skyline 城市地平线
DescriptionInput第1行：2个用空格隔开的整数N和W.第2到N+1行：每行包括2个用空格隔开的整数x,y，其意义如题中所述．输入中的x严格递增，并且第一个z总是x．Output输出一个整数，表示城市中最少包含的建筑物数量．SampleInput10261122516381110152173202221INPUTDETAILS:ThecasementionedaboveSampleOutput6题解同1628[crayon-6743dd6898421883116156/] ...
02014年7月28日3,448单调栈
「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日4,189线段树
「BZOJ2325」[ZJOI2011] 道馆之战
Description口袋妖怪(又名神奇宝贝或宠物小精灵)红/蓝/绿宝石中的水系道馆需要经过三个冰地才能到达馆主的面前，冰地中的每一个冰块都只能经过一次。当一个冰地上的所有冰块都被经过之后，到下一个冰地的楼梯才会被打开。三个冰地分别如下：当走出第三个冰地之后，就可以与馆主进行道馆战了。馆主发现这个难度太小，导致经常有挑战者能通过，为了加大难度，将道馆分成了n个房间，每个房间中是两个冰块或障碍，表示一列冰地。任意两...
22014年7月26日6,492线段树,树链剖分
「BZOJ2141」排队
Description排排坐，吃果果，生果甜嗦嗦，大家笑呵呵。你一个，我一个，大的分给你，小的留给我，吃完果果唱支歌，大家乐和和。红星幼儿园的小朋友们排起了长长地队伍，准备吃果果。不过因为小朋友们的身高有所区别，排成的队伍高低错乱，极不美观。设第i个小朋友的身高为hi，我们定义一个序列的杂乱程度为：满足ihj的(i,j)数量。幼儿园阿姨每次会选出两个小朋友，交换他们的位置，请你帮忙计算出每次交换后，序列的杂乱程度。为方...
42014年7月26日18,000分块
「BZOJ3702」「FJ互测」二叉树
Description(tree.c/.cpp/.pas)现在有一棵二叉树，所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有n个叶子节点，满足这些权值为1..n的一个排列)。可以任意交换每个非叶子节点的左右孩子。要求进行一系列交换，使得最终所有叶子节点的权值按照中序遍历写出来，逆序对个数最少。InputFormat(tree.in)第一行n下面每行，一个数x如果x==0，表示这个节点非叶子节点，递归地向下读入其左孩子和右孩子的信息，如果x!=0，表示...
12014年7月24日4,611模拟,线段树
「BZOJ3693」「FJ2014集训」圆桌会议
问题描述有n组人要一起开一个圆桌会议（编号为0~n-1），会议的圆桌上有m个位置（编号为0~m-1）。每个组有ai个人，他们需要被安排在（li，(li+1)%m，(li+2)%m，…，ri）的座位范围内。每个座位只能安排一个人就坐，并且每个人都需要被安排一个座位。现在你需要判断是否存在满足条件的座位安排。输入格式输入包含不超过10组数据。第一行有一个数字T，表示数据组数。接下来有T组数据，每组数据第一行包含两个数n，m，表示有多少组的...
02014年7月23日5,053线段树
「BZOJ1628」[Usaco2007 Demo] City skyline
DescriptionThebestpartofthedayforFarmerJohn'scowsiswhenthesunsets.Theycanseetheskylineofthedistantcity.Bessiewondershowmanybuildingsthecityhas.Writeaprogramthatassiststhecowsincalculatingtheminimumnumberofbuildingsinthecity,givenaprofileofitsskyline.Thecityinprofileisquitedullarchitecturally,featuringonlybox-shapedbuildings.Theskylineofacityonthehorizonissomewherebetween1andWunitswide(1&...
02014年7月23日3,299单调栈