• 「czy系列赛」czy的后宫3

    「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日4,658树状数组,离线处理,莫队算法
  • 「BZOJ3688」「FJ2014集训」折线统计

    「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日1,888递推与动规,树状数组
  • 「BZOJ3262」陌上花开

    「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日5,717treap,树套树,树状数组
  • 「BZOJ3295」[CQOI2011] 动态逆序对

    「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日5,618树套树,线段树,树状数组
  • 「BZOJ1103」[POI2007] 大都市meg

    「BZOJ1103」[POI2007] 大都市meg

    Description在经济全球化浪潮的影响下,习惯于漫步在清晨的乡间小路的邮递员BlueMary也开始骑着摩托车传递邮件了。不过,她经常回忆起以前在乡间漫步的情景。昔日,乡下有依次编号为1..n的n个小村庄,某些村庄之间有一些双向的土路。从每个村庄都恰好有一条路径到达村庄1(即比特堡)。并且,对于每个村庄,它到比特堡的路径恰好只经过编号比它的编号小的村庄。另外,对于所有道路而言,它们都不在除村庄以外的其他地点相遇。在这...

    22014年6月15日4,207dfs序,树状数组
  • NOIP2013火柴排队

    NOIP2013火柴排队

    描述涵涵有两盒火柴,每盒装有n根火柴,每根火柴都有一个高度。现在将每盒中的火柴各自排成一列,同一列火柴的高度互不相同,两列火柴之间的距离定义为:∑ i=1 n (a i −b i ) 2  ,其中a i  表示第一列火柴中第i个火柴的高度,b i  表示第二列火柴中第i个火柴的高度。每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离,最少需要交换多少次?如果这个数...

    22014年5月30日3,956树状数组
  • 「BZOJ3155」Preprefix sum

    「BZOJ3155」Preprefix sum

    DescriptionInput第一行有两个整数N和M,分别表示序列长度和操作个数。接下来的一行有N个整数,即给定的序列a1,a2….an。接下来有M行,每行对应一个操作,格式见题目描述。Output对于每个询问操作,输出一行,表示所询问的SSi的值。SampleInput5312345Query5Modify32Query5SampleOutput3532HINT1<=N,M<=100000,且在任意时刻0<=Ai<=100000题解开俩个树状数组,第一个维护a[i]前缀和第二个维护(n...

    22014年5月29日1,966树状数组
  • 「BZOJ1452」[JSOI2009] Count

    「BZOJ1452」[JSOI2009] Count

    DescriptionInputOutputSampleInputSampleOutput12HINT题解发现第一次写二维树状数组妈蛋就是多了一层for。。。对于每种颜色开一个二维树状数组水过。。。[crayon-5ade7f0209aa3561119554/] ...

    22014年5月29日2,828树状数组
  • 「BZOJ1537」[POI2005] Aut – The Bus

    「BZOJ1537」[POI2005] Aut -  The Bus

    DescriptionByteCity的街道形成了一个标准的棋盘网络–他们要么是北南走向要么就是西东走向.北南走向的路口从1到n编号,西东走向的路从1到m编号.每个路口用两个数(i,j)表示(1<=i<=n,1<=j<=m).ByteCity里有一条公交线,在某一些路口设置了公交站点.公交车从(1,1)发车,在(n,m)结束.公交车只能往北或往东走.现在有一些乘客在某些站点等车.公交车司机希望在路线中能接到尽量多的乘客.帮他想想怎么才能接到最多的乘客.I...

    02014年5月28日1,659递推与动规,树状数组
  • 「BZOJ1782」[Usaco2010 Feb] slowdown慢慢游

    「BZOJ1782」[Usaco2010 Feb] slowdown慢慢游

    Description每天FarmerJohn的N头奶牛(1<=N<=100000,编号1…N)从粮仓走向他的自己的牧场。牧场构成了一棵树,粮仓在1号牧场。恰好有N-1条道路直接连接着牧场,使得牧场之间都恰好有一条路径相连。第i条路连接着A_i,B_i,(1<=A_i<=N;1<=B_i<=N)。奶牛们每人有一个私人牧场P_i(1<=P_i<=N)。粮仓的门每次只能让一只奶牛离开。耐心的奶牛们会等到他们的前面的朋友们到达了自己的私人牧场后才...

    02014年5月18日1,572树状数组
  • 「BZOJ2743」[HEOI2012] 采花

    「BZOJ2743」[HEOI2012] 采花

    Description萧芸斓是Z国的公主,平时的一大爱好是采花。今天天气晴朗,阳光明媚,公主清晨便去了皇宫中新建的花园采花。花园足够大,容纳了n朵花,花有c种颜色(用整数1-c表示),且花是排成一排的,以便于公主采花。公主每次采花后会统计采到的花的颜色数,颜色数越多她会越高兴!同时,她有一癖好,她不允许最后自己采到的花中,某一颜色的花只有一朵。为此,公主每采一朵花,要么此前已采到此颜色的花,要么有相当正确的直觉告...

    02014年5月14日3,054树状数组,离线处理
  • 「BZOJ1878」[SDOI2009] HH的项链

    「BZOJ1878」[SDOI2009] HH的项链

    DescriptionHH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH不断地收集新的贝壳,因此,他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?这个问题很难回答。。。因为项链实在是太长了。于是,他只好求助睿智的你,来解决这个问题。Input第一行:一个整数N,表示项链的长度。第二行:...

    52014年5月13日5,695树状数组,离线处理