数据结构 - Page 25

「BZOJ2453」维护队列
Description你小时候玩过弹珠吗？小朋友A有一些弹珠，A喜欢把它们排成队列，从左到右编号为1到N。为了整个队列鲜艳美观，小朋友想知道某一段连续弹珠中，不同颜色的弹珠有多少。当然，A有时候会依据个人喜好，替换队列中某个弹珠的颜色。但是A还没有学过编程，且觉得头脑风暴太浪费脑力了，所以向你来寻求帮助。Input输入文件第一行包含两个整数N和M。第二行N个整数，表示初始队列中弹珠的颜色。接下来M行，每行的形式为...
52014年4月26日7,530分块,二分法

「BZOJ3343」教主的魔法
Description教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为1、2、……、N。每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R]（1≤L≤R≤N）内的英雄的身高全部加上一个整数W。（虽然L=R时并不符合区间的书写规范，但我们可以认为是单独增加第L（R）个英雄的身高）CYZ、光哥...
22014年4月26日8,983二分法,分块
「BZOJ2038」[2009国家集训队] 小Z的袜子(hose)
Description作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。你的任务便是告诉小Z，他有多大的概率抽到两只颜色...
212014年4月26日31,178莫队算法
「CF413E」Maze 2D
ThelastproductoftheR2companyinthe2Dgames'fieldisanewrevolutionaryalgorithmofsearchingfortheshortestpathina 2 × nmaze.Imagineamazethatlookslikea 2 × n rectangle,dividedintounitsquares.Eachunitsquareiseitheranemptycelloranobstacle.Inoneunitoftime,apersoncanmovefromanemptycellofthemazetoanyside-adjacentemptycell.Theshortestpathproblemisformulatedasfollows.Giventwofreemazecells,younee...
42014年4月24日4,446线段树
「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,354树套树,treap,线段树
「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,592树套树,treap,线段树
「BZOJ3524 / 2223」[POI2014] Couriers
Description给一个长度为n的序列a。1≤a[i]≤n。m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。Input第一行两个数n，m。第二行n个数，a[i]。接下来m行，每行两个数l,r，表示询问[l,r]这个区间。Outputm行，每行对应一个答案。SampleInput7511323431314371766SampleOutput10304HINT「数据范围」n,m≤500000SourceByDzy题解coolinging：可持久化...
32014年4月19日7,200主席树
「BZOJ1579」[Usaco2009 Feb] Revamping Trails 道路升级
Description每天,农夫John需要经过一些道路去检查牛棚N里面的牛.农场上有M(1<=M<=50,000)条双向泥土道路,编号为1..M.道路i连接牛棚P1_i和P2_i(1<=P1_i<=N;1<=P2_i<=N).John需要T_i(1<=T_i<=1,000,000)时间单位用道路i从P1_i走到P2_i或者从P2_i走到P１_i他想更新一些路经来减少每天花在路上的时间.具体地说,他想更新K(1<=K<=20)条路经，将它们所须时间减为０．帮助FJ选择哪些...
02014年4月12日5,086堆,dijkstra
「BZOJ1657」[Usaco2006 Mar] Mooo 奶牛的歌声
DescriptionFarmerJohn'sN(1<=N<=50,000)cowsarestandinginaverystraightrowandmooing.Eachcowhasauniqueheighthintherange1..2,000,000,000nanometers(FJreallyisasticklerforprecision).Eachcowmoosatsomevolumevintherange1..10,000.This"moo"travelsacrosstherowofcowsinbothdirections(exceptfortheendcows,obviously).Curiously,itisheardonlybytheclosestcowineachdirectionwhoseheightisstrictlylargerth...
02014年4月10日3,373单调栈
「BZOJ1455」罗马游戏
Description罗马皇帝很喜欢玩杀人游戏。他的军队里面有n个人，每个人都是一个独立的团。最近举行了一次平面几何测试，每个人都得到了一个分数。皇帝很喜欢平面几何，他对那些得分很低的人嗤之以鼻。他决定玩这样一个游戏。它可以发两种命令：1.Merger(i,j)。把i所在的团和j所在的团合并成一个团。如果i,j有一个人是死人，那么就忽略该命令。2.Kill(i)。把i所在的团里面得分最低的人杀死。如果i这个人已经死了，这条命令就忽略。...
32014年4月8日5,336可并堆
「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,220线段树,树链剖分
「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,433线段树,树链剖分,link cut tree