线段树 - Page 7

NOIP2012借教室
题目描述在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。面对海量租借教室的信息，我们自然希望编程解决这个问题。我们需要处理接下来n天的借教室信息，其中第i天学校有ri个教室可供租借。共有m份订单，每份订单用三个正整数描述，分别为dj,sj,tj，表示某租借者需要从第sj天到第tj天租借教室（包括第sj天和第tj天...
42014年4月4日16,643二分法,线段树

「BZOJ3211」花神游历各国
Description Input Output每次x=1时，每行一个整数，表示这次旅行的开心度 SampleInput4 1100555112212112223114SampleOutput101 1111HINT对于100%的数据，n≤100000，m≤200000,data[i]非负且小于10^9题解同上帝造题的七分钟[crayon-676d5a42a8a72107047418/] ...
02014年3月17日6,259线段树
「POJ2828」Buy Tickets
DescriptionRailwayticketsweredifficulttobuyaroundtheLunarNewYearinChina,sowemustgetupearlyandjoinalongqueue…TheLunarNewYearwasapproaching,butunluckilytheLittleCatstillhadschedulesgoinghereandthere.Now,hehadtotravelbytraintoMianyang,SichuanProvinceforthewintercampselectionofthenationalteamofOlympiadinInformatics.Itwasoneo’clocka.m.anddarkoutside.Chillwindfromthenorthwestdidnot...
02014年3月1日4,315线段树,离线处理
「CODEVS1080」线段树练习1(线段树 / 树状数组 / zkw线段树)
题目描述 Description一行N个方格，开始每个格子里都有一个整数。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子区间[a,b]中所有元素的和；修改的规则是指定某一个格子x，加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1≤N<100000，,提问和修改的总数m<10000条。输入描述 InputDescription输入文件第一行为一个整数N，接下来是n行n个整数，表示格子中原来的整数。接下一个正整...
22014年2月23日5,650线段树,树状数组
「CODEVS2216」行星序列
题目描述 Description“神州“载人飞船的发射成功让小可可非常激动，他立志长大后要成为一名宇航员假期一始，他就报名参加了“小小宇航员夏令营”，在这里小可可不仅学到了丰富的宇航知识，还参与解决了一些模拟飞行中发现的问题，今天指导老师交给他一个任务，在这次模拟飞行的路线上有N个行星，暂且称它们为一个行星序列，并将他们从1至n标号，在宇宙未知力量的作用下这N个行星的质量是不断变化的，所以他们对飞船产生的引力...
22014年2月22日4,487线段树
「BZOJ1067」[SCOI2007] 降雨量
Description我们常常会说这样的话：“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年，且对于任意Y＜Z＜X，Z年的降雨量严格小于X年。例如2002，2003，2004和2005年的降雨量分别为4920，5901，2832和3890，则可以说“2005年是自2003年以来最多的”，但不能说“2005年是自2002年以来最多的”由于有些年份的降雨量未知，有的说法是可能正确也可以不正确的。Input输入仅一行包含一个正整数n，为已知的数据。...
32014年2月19日9,208线段树
「CODEVS1690」开关灯
题目描述Description YYX家门前的街上有N(2<=N<=100000)盏路灯，在晚上六点之前，这些路灯全是关着的，六点之后，会有M(2<=m<=100000)个人陆续按下开关，这些开关可以改变从第i盏灯到第j盏灯的状态，现在YYX想知道，从第x盏灯到第y盏灯中有多少是亮着的(1<=i,j,x,y<=N)输入描述InputDescription第1行:用空格隔开的两个整数N和M第2..M+1行:每行表示一个操作,有三个用空格分开的整数:指令号(0代...
02014年2月15日3,322线段树
「CODEVS1191」数轴染色
题目描述Description在一条数轴上有N个点，分别是1～N。一开始所有的点都被染成黑色。接着我们进行M次操作，第i次操作将[Li,Ri]这些点染成白色。请输出每个操作执行后剩余黑色点的个数。输入描述InputDescription输入一行为N和M。下面M行每行两个数Li、Ri输出描述OutputDescription输出M行，为每次操作后剩余黑色点的个数。样例输入SampleInput103335728样例输出SampleOutput963数据范围及提示DataSize&...
82014年2月15日3,514线段树
「fzyzoj1969」无敌的妹子2
Descriptionhttp://110.90.118.124/OnlineJudge/problem_show.php?id=1969 土豪无敌有很多相机，因为需要秀相机，所以需要拍很多妹纸，现在，无敌招募了n只妹纸，从1到n编号摆在架子上。现在无敌要给妹纸穿各种衣服来增加妹纸的美丽值（由于无敌很正直，他懒得把妹纸的衣服卸下来，只会不停地给妹纸穿衣服（妹纸：热出翔）他经常会把某个让他很不爽的区间内的妹纸全部替换掉；或者给某个区间内的妹纸都穿上某种...
02014年2月12日4,633线段树
无聊写的A+B问题。。。
输入A,B输出A+B[crayon-676d5a42abb27842942018/]
42014年2月3日9,081kruskal,spfa,最小割,背包动规,线段树,floyd,树状数组
「BZOJ3038」上帝造题的七分钟2
DescriptionXLk觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。"第一分钟，X说，要有数列，于是便给定了一个正整数数列。第二分钟，L说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。第三分钟，k说，要能查询，于是便有了求一段数的和的操作。第四分钟，彩虹喵说，要是NOIP难度，于是便有了数据范围。第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。第六分钟，和雪说，要省点事，于是...
02014年1月26日6,045线段树
「CODEVS1299」切水果
题目描述 Description简单的说,一共N个水果排成一排,切M次,每次切[L,R]区间的所有水果(可能有的水果被重复切),每切完一次输出剩下水果数量输入描述 InputDescription第1行共包括2个正整数，分别为N,M。接下来m行每行两个正整数L,R输出描述 OutputDescription一共输出M行,每行输出切完之后剩下水果数量样例输入 SampleInput103352815样例输出 SampleOutput732数据范围及提示 DataSize&Hint30%的数据...
02014年1月25日3,413线段树