树状数组 - Page 4

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

「BZOJ1878」[SDOI2009] HH的项链
DescriptionHH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。Input第一行：一个整数N，表示项链的长度。第二行：...
52014年5月13日9,353树状数组,离线处理
「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,793主席树,树状数组
「BZOJ1227」[SDOI2009] 虔诚的墓主人
题目描述 Description小W是一片新造公墓的管理人。公墓可以看成一块N×M的矩形，矩形的每个格点，要么种着一棵常青树，要么是一块还没有归属的墓地。当地的居民都是非常虔诚的基督徒，他们愿意提前为自己找一块合适墓地。为了体现自己对主的真诚，他们希望自己的墓地拥有着较高的虔诚度。一块墓地的虔诚度是指以这块墓地为中心的十字架的数目。一个十字架可以看成中间是墓地，墓地的正上、正下、正左、正右都有恰好k棵常青树。...
42014年3月11日7,265树状数组,排列组合
「BZOJ1818」[CQOI2010] 内部白点
Description无限大正方形网格里有n个黑色的顶点，所有其他顶点都是白色的（网格的顶点即坐标为整数的点，又称整点）。每秒钟，所有内部白点同时变黑，直到不存在内部白点为止。你的任务是统计最后网格中的黑点个数。内部白点的定义：一个白色的整点P(x,y)是内部白点当且仅当P在水平线的左边和右边各至少有一个黑点（即存在x1<x<x2使得(x1,y)和(x2,y)都是黑点），且在竖直线的上边和下边各至少有一个黑点（即存在y1<y&l...
12014年3月5日5,830树状数组
「CODEVS1080」线段树练习1(线段树 / 树状数组 / zkw线段树)
题目描述 Description一行N个方格，开始每个格子里都有一个整数。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子区间[a,b]中所有元素的和；修改的规则是指定某一个格子x，加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1≤N<100000，,提问和修改的总数m<10000条。输入描述 InputDescription输入文件第一行为一个整数N，接下来是n行n个整数，表示格子中原来的整数。接下一个正整...
22014年2月23日5,643线段树,树状数组
无聊写的A+B问题。。。
输入A,B输出A+B[crayon-6767f2bee0e6b556787301/]
42014年2月3日9,068kruskal,最小割,spfa,背包动规,floyd,线段树,树状数组
「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日4,951线段树,树状数组
「vijos1512」SuperBrother打鼹鼠
背景SuperBrother在机房里闲着没事干(再对比一下他的NOIP,真是讽刺啊......),于是便无聊地开始玩“打鼹鼠”......描述在这个“打鼹鼠”的游戏中，鼹鼠会不时地从洞中钻出来，不过不会从洞口钻进去（鼹鼠真胆大……）。洞口都在一个大小为n(n<=1024)的正方形中。这个正方形在一个平面直角坐标系中，左下角为(0,0)，右上角为(n-1,n-1)。洞口所在的位置都是整点，就是横纵坐标都为整数的点。而SuperBrother也不时地会想知道...
02013年12月30日3,867树状数组
树状数组入门
如果给定一个数组，要你求里面所有数的和，一般都会想到累加。但是当那个数组很大的时候，累加就显得太耗时了，时间复杂度为O(n)，并且采用累加的方法还有一个局限，那就是，当修改掉数组中的元素后，仍然要你求数组中某段元素的和，就显得麻烦了。所以我们就要用到树状数组，他的时间复杂度为O（lgn），相比之下就快得多。下面就讲一下什么是树状数组：一般讲到树状数组都会少不了下面这个图：下面来分析一下上面那个图看能得出...
42013年12月28日5,001树状数组