数据结构 - Page 24

「BZOJ2743」[HEOI2012] 采花
Description萧芸斓是Z国的公主，平时的一大爱好是采花。今天天气晴朗，阳光明媚，公主清晨便去了皇宫中新建的花园采花。花园足够大，容纳了n朵花，花有c种颜色（用整数1-c表示），且花是排成一排的，以便于公主采花。公主每次采花后会统计采到的花的颜色数，颜色数越多她会越高兴！同时，她有一癖好，她不允许最后自己采到的花中，某一颜色的花只有一朵。为此，公主每采一朵花，要么此前已采到此颜色的花，要么有相当正确的直觉告...
02014年5月14日5,197树状数组,离线处理

「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日8,599treap,树套树,主席树,线段树
「BZOJ1878」[SDOI2009] HH的项链
DescriptionHH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。Input第一行：一个整数N，表示项链的长度。第二行：...
52014年5月13日8,887树状数组,离线处理
「BZOJ1293」[SCOI2009] 生日礼物
Description小西有一条很长的彩带，彩带上挂着各式各样的彩珠。已知彩珠有N个，分为K种。简单的说，可以将彩带考虑为x轴，每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠，但多个彩珠也可以出现在同一个位置上。小布生日快到了，于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮，小西希望这一段彩带中能包含所有种类的彩珠。同时，为了方便，小西希望这段彩带尽可能短，你能帮助小西计算这个最短的长度么...
12014年5月12日5,923单调队列
「BZOJ1150」[CTSC2007] 数据备份Backup
Description Input输入的第一行包含整数n和k，其中n（2≤n≤100000）表示办公楼的数目，k（1≤k≤n/2）表示可利用的网络电缆的数目。接下来的n行每行仅包含一个整数（0≤s≤1000000000）,表示每个办公楼到大街起点处的距离。这些整数将按照从小到大的顺序依次出现。Output输出应由一个正整数组成，给出将2K个相异的办公楼连成k对所需的网络电缆的最小总长度。SampleInput52134612SampleOutput4HINT上面的样例输入给出...
02014年5月7日7,375贪心,堆,链表
「BZOJ2288」「POJ Challenge」生日礼物
Descriptionftiasch18岁生日的时候，lqp18_31给她看了一个神奇的序列 A1, A2,..., AN.她被允许选择不超过 M 个连续的部分作为自己的生日礼物。自然地，ftiasch想要知道选择元素之和的最大值。你能帮助她吗？Input第1行，两个整数 N (1≤ N ≤105)和 M (0≤ M ≤105),序列的长度和可以选择的部分。第2行， N 个整数 A1, A2,..., AN (0≤|Ai|≤104),序列。Output一个整数，最大的和。SampleI...
12014年5月7日6,923堆,贪心,链表
「BZOJ1593」[Usaco2008 Feb] Hotel 旅馆
Description奶牛们最近的旅游计划，是到苏必利尔湖畔，享受那里的湖光山色，以及明媚的阳光。作为整个旅游的策划者和负责人，贝茜选择在湖边的一家著名的旅馆住宿。这个巨大的旅馆一共有N(1<=N<=50,000)间客房，它们在同一层楼中顺次一字排开，在任何一个房间里，只需要拉开窗帘，就能见到波光粼粼的湖面。贝茜一行，以及其他慕名而来的旅游者，都是一批批地来到旅馆的服务台，希望能订到D_i(1<=D_i<=N)间连续的...
12014年5月6日5,220线段树
「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日3,813线段树
「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,100线段树
「BZOJ1984」月下“毛景树”
Description毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬~~毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~~~“毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数：Changekw：将第k条树枝上毛毛果的...
02014年4月29日5,966线段树,树链剖分
「BZOJ1901」Zju2112 Dynamic Rankings
Description给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序，从输入文件中读入序列a，然后读入一系列的指令，包括询问指令和修改指令。对于每一个询问指令，你必须输出正确的回答。第一行有两个正整数n(1≤n≤...
12014年4月28日8,482主席树,树状数组
「BZOJ2120」数颜色
Description墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令：1、QLR代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。2、RPCol把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？Input第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。第...
12014年4月26日7,829分块,二分法