• 【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日3,775树套树,线段树,树状数组
  • 【bzoj1103】[POI2007]大都市meg

    【bzoj1103】[POI2007]大都市meg

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

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

    NOIP2013火柴排队

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

    22014年5月30日2,998树状数组
  • 【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,197树状数组
  • 【bzoj1452】[JSOI2009]Count

    【bzoj1452】[JSOI2009]Count

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

    22014年5月29日1,806树状数组
  • 【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,104递推与动规,树状数组
  • 【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,031树状数组
  • 【bzoj2743】[HEOI2012]采花

    【bzoj2743】[HEOI2012]采花

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

    02014年5月14日1,874树状数组,离线处理
  • 【bzoj1878】[SDOI2009]HH的项链

    【bzoj1878】[SDOI2009]HH的项链

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

    52014年5月13日3,427树状数组,离线处理
  • 【bzoj1901】Zju2112 Dynamic Rankings

    【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≤...

    02014年4月28日3,550主席树,树状数组
  • 【bzoj1227】[SDOI2009]虔诚的墓主人

    【bzoj1227】[SDOI2009]虔诚的墓主人

    题目描述 Description小W是一片新造公墓的管理人。公墓可以看成一块N×M的矩形,矩形的每个格点,要么种着一棵常青树,要么是一块还没有归属的墓地。当地的居民都是非常虔诚的基督徒,他们愿意提前为自己找一块合适墓地。为了体现自己对主的真诚,他们希望自己的墓地拥有着较高的虔诚度。一块墓地的虔诚度是指以这块墓地为中心的十字架的数目。一个十字架可以看成中间是墓地,墓地的正上、正下、正左、正右都有恰好k棵常青树。...

    32014年3月11日2,865树状数组,排列组合
  • 【bzoj1818】[Cqoi2010]内部白点

    【bzoj1818】[Cqoi2010]内部白点

    Description无限大正方形网格里有n个黑色的顶点,所有其他顶点都是白色的(网格的顶点即坐标为整数的点,又称整点)。每秒钟,所有内部白点同时变黑,直到不存在内部白点为止。你的任务是统计最后网格中的黑点个数。内部白点的定义:一个白色的整点P(x,y)是内部白点当且仅当P在水平线的左边和右边各至少有一个黑点(即存在x1<x<x2使得(x1,y)和(x2,y)都是黑点),且在竖直线的上边和下边各至少有一个黑点(即存在y1<y&l...

    12014年3月5日1,890树状数组
  • 【codevs1080】线段树练习1(线段树/树状数组/zkw线段树)

    【codevs1080】线段树练习1(线段树/树状数组/zkw线段树)

    题目描述 Description一行N个方格,开始每个格子里都有一个整数。现在动态地提出一些问题和修改:提问的形式是求某一个特定的子区间[a,b]中所有元素的和;修改的规则是指定某一个格子x,加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1≤N<100000,,提问和修改的总数m<10000条。输入描述 InputDescription输入文件第一行为一个整数N,接下来是n行n个整数,表示格子中原来的整数。接下一个正整...

    22014年2月23日2,314线段树,树状数组