• 「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日5,882主席树,树状数组
  • 「BZOJ1227」[SDOI2009] 虔诚的墓主人

    「BZOJ1227」[SDOI2009] 虔诚的墓主人

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

    42014年3月11日4,350树状数组,排列组合
  • 「BZOJ1818」[CQOI2010] 内部白点

    「BZOJ1818」[CQOI2010] 内部白点

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

    12014年3月5日2,926树状数组
  • 「CODEVS1080」线段树练习1(线段树 / 树状数组 / zkw线段树)

    「CODEVS1080」线段树练习1(线段树 / 树状数组 / zkw线段树)

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

    22014年2月23日3,268线段树,树状数组
  • 无聊写的A+B问题。。。

    无聊写的A+B问题。。。

    输入A,B输出A+B[crayon-5ade7eee9f989395391401/] 

  • 「CODEVS1081」线段树练习 2(线段树 / 树状数组)

    「CODEVS1081」线段树练习 2(线段树 / 树状数组)

    题目描述 Description给你N个数,有两种操作1:给区间[a,b]的所有数都增加X2:询问第i个数是什么?输入描述 InputDescription第一行一个正整数n,接下来n行n个整数,再接下来一个正整数Q,表示操作的个数.接下来Q行每行若干个整数。如果第一个数是1,后接3个正整数a,b,X,表示在区间[a,b]内每个数增加X,如果是2,后面跟1个整数i,表示询问第i个位置的数是多少。输出描述 OutputDescription对于每个询问输出一行一个答...

    02014年1月17日2,494线段树,树状数组
  • 「vijos1512」SuperBrother打鼹鼠

    「vijos1512」SuperBrother打鼹鼠

    背景SuperBrother在机房里闲着没事干(再对比一下他的NOIP,真是讽刺啊......),于是便无聊地开始玩“打鼹鼠”......描述在这个“打鼹鼠”的游戏中,鼹鼠会不时地从洞中钻出来,不过不会从洞口钻进去(鼹鼠真胆大……)。洞口都在一个大小为n(n<=1024)的正方形中。这个正方形在一个平面直角坐标系中,左下角为(0,0),右上角为(n-1,n-1)。洞口所在的位置都是整点,就是横纵坐标都为整数的点。而SuperBrother也不时地会想知道...

    02013年12月30日1,754树状数组
  • 树状数组入门

    树状数组入门

    如果给定一个数组,要你求里面所有数的和,一般都会想到累加。但是当那个数组很大的时候,累加就显得太耗时了,时间复杂度为O(n),并且采用累加的方法还有一个局限,那就是,当修改掉数组中的元素后,仍然要你求数组中某段元素的和,就显得麻烦了。所以我们就要用到树状数组,他的时间复杂度为O(lgn),相比之下就快得多。下面就讲一下什么是树状数组:一般讲到树状数组都会少不了下面这个图:下面来分析一下上面那个图看能得出...

    42013年12月28日2,303树状数组
4 / 4 « 上一页 1 2 3 4