数据结构 - Page 21

「BZOJ3223」JoyOI 1729 文艺平衡树
Description您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1Input第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=nOutput输出一行n个数字，表示原始序列经过m次变换后的结果SampleInput53131314...
262014年7月22日17,559splay

「BZOJ1251」序列终结者
Description网上有许多题，就是给定一个序列，要你支持几种操作：A、B、C、D。一看另一道题，又是一个序列要支持几种操作：D、C、B、A。尤其是我们这里的某人，出模拟试题，居然还出了一道这样的，真是没技术含量……这样我也出一道题，我出这一道的目的是为了让大家以后做这种题目有一个“库”可以依靠，没有什么其他的意思。这道题目就叫序列终结者吧。「问题描述」给定一个长度为N的序列，每个序列的元素是一个整数（...
172014年7月21日8,437splay
「BZOJ3694」「FJ2014集训」最短路
题目描述给出一个n个点m条边的无向图，n个点的编号从1~n，定义源点为1。定义最短路树如下：从源点1经过边集T到任意一点i有且仅有一条路径，且这条路径是整个图1到i的最短路径，边集T构成最短路树。给出最短路树，求对于除了源点1外的每个点i，求最短路，要求不经过给出的最短路树上的1到i的路径的最后一条边。输入格式第一行包含两个数n和m，表示图中有n个点和m条边。接下来m行，每行有四个数ai，bi，li，ti，表示图中第i条边连接...
02014年7月20日5,219线段树,树链剖分
「FJ2014集训」信心题
「题目描述」在二维平面上有若干个多边形，每个多边形都覆盖了一定的区域，它们之间有可能重叠，请求出这些多边形遮住了多大的平面区域。即，求多边形的面积并。「输入格式」本题为提交答案题，共有10个输入，分别是cover1.in∼cover10.in。每个文件第一行，一个整数，表示这个输入文件的序号(1∼10)。接下来一行，一个整数n，表示这组数据中有n个多边形。接下来n行，每行第一个整数Pi，表示这个多边形有Pi个点，接下来有Pi组整...
02014年7月20日3,524线段树,几何
「czy系列赛」czy的后宫3
czy的后宫3「题目描述」上次czy在机房妥善安排了他的后宫之后，他发现可以将他的妹子分为c种，他经常会考虑这样一个问题：在[l,r]的妹子中间，能挑选出多少不同类型的妹子呢？注意：由于czy非常丧尸，所以他要求在所挑选的妹子类型在[l,r]中出现次数为正偶数，你懂得。问题简述:n个数，m次询问，每次问[l,r]区间有多少个数恰好出现正偶数次「输入格式」第一行3个整数，表示n,c,m第二行n个数，每个数Ai在[1,c]之间，表示一个Ai类型...
42014年7月19日10,094树状数组,离线处理,莫队算法
「BZOJ2821」作诗(Poetize)
Description神犇SJY虐完HEOI之后给傻×LYD出了一题：SHY是T国的公主，平时的一大爱好是作诗。由于时间紧迫，SHY作完诗之后还要虐OI，于是SHY找来一篇长度为N的文章，阅读M次，每次只阅读其中连续的一段[l,r]，从这一段中选出一些汉字构成诗。因为SHY喜欢对偶，所以SHY规定最后选出的每个汉字都必须在[l,r]里出现了正偶数次。而且SHY认为选出的汉字的种类数（两个一样的汉字称为同一种）越多越好...
32014年7月19日8,159分块
「BZOJ3688」「FJ2014集训」折线统计
「题目描述」二维平面上有n个点(xi,yi)，现在这些点中取若干点构成一个集合S，对它们按照x坐标排序，顺次连接，将会构成一些连续上升、下降的折线，设其数量为f(S)。如下图中，1->2,2->3,3->5,5->6（数字为下图中从左到右的点编号），将折线分为了4部分，每部分连续上升、下降。现给定k，求满足f(S)=k的S集合个数。「输入格式」第一行两个整数n和k，以下n行每行两个数(xi,yi)表示第i个点的坐标。所有点的坐标值都在...
02014年7月13日4,410递推与动规,树状数组
「BZOJ2724」[Violet 6] 蒲公英
Description Input修正一下l=(l_0+x-1)modn+1,r=(r_0+x-1)modn+1OutputHINT修正下：n<=40000,m<=50000题解在线区间众数的分块做法比较多，这里提供一个思路：首先离散化一下比较方便。最初可能会有一个想法，是不是众数只可能是完整的块的众数，或者不完整的块出现的数呢？显然很容易得出反例。应该是完整的所有块的众数，和不完整块中出现的数。所以我们可以预处理f(i,j)表示第i块到第j块的众数（枚举i开个桶扫...
32014年7月6日12,707分块
「BZOJ3262」陌上花开
Description有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。Input第一行为N,K(1<=N<=100,000,1<=K<=200,000),分别表示花的数量和最大属性值。以下N行，每行三个整数...
02014年6月19日9,472树套树,treap,树状数组
「CODEVS3044」矩形面积求并
题目描述Description输入n个矩形，求他们总共占地面积（也就是求一下面积的并）输入描述InputDescription可能有多组数据，读到n=0为止(不超过15组)每组数据第一行一个数n，表示矩形个数(n<=100)接下来n行每行4个实数x1,y1,x2,y1(0<=x1<x2<=100000;0<=y1<y2<=100000)，表示矩形的左下角坐标和右上角坐标输出描述OutputDescription每组数据输出一行表示答案样例输入SampleInput[crayon-6743dd1e2b39a981...
52014年6月18日12,057线段树
「BZOJ1006」[HNOI2008] 神奇的国度
DescriptionK国是一个热衷三角形的国度,连人的交往也只喜欢三角原则.他们认为三角关系:即AB相互认识,BC相互认识,CA相互认识,是简洁高效的.为了巩固三角关系,K国禁止四边关系,五边关系等等的存在.所谓N边关系,是指N个人A1A2...An之间仅存在N对认识关系:(A1A2)(A2A3)...(AnA1),而没有其它认识关系.比如四边关系指ABCD四个人AB,BC,CD,DA相互认识,而AC,BD不认识.全民比赛时,为了防止做弊，规定任...
72014年6月17日8,348STL
「BZOJ3295」[CQOI2011] 动态逆序对
Description对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。Input输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。Output输出包含m行，依次为删除每个元素之前，逆序对...
42014年6月17日8,277树套树,线段树,树状数组