树状数组 - Page 3

「BZOJ3192」[JLOI2013] 删除物品
Description箱子再分配问题需要解决如下问题：（1）一共有N个物品，堆成M堆。（2）所有物品都是一样的，但是它们有不同的优先级。（3）你只能够移动某堆中位于顶端的物品。（4）你可以把任意一堆中位于顶端的物品移动到其它某堆的顶端。若此物品是当前所有物品中优先级最高的，可以直接将之删除而不用移动。（5）求出将所有物品删除所需的最小步数。删除操作不计入步数之中。（6）只是一个比较难解决的问题，这里你只...
02014年8月13日2,989树状数组

「BZOJ1935」[SHOI2007] Tree 园丁的烦恼
Description很久很久以前，在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园艺爱好者，在他的皇家花园里种植着各种奇花异草。有一天国王漫步在花园里，若有所思，他问一个园丁道：“最近我在思索一个问题，如果我们把花坛摆成六个六角形，那么……”“那么本质上它是一个深度优先搜索，陛下”，园丁深深地向国王鞠了一躬。“嗯……我听说有一种怪物叫九头蛇，它非常贪吃苹果树……”“是的，显然这是一道经典的...
22014年8月6日5,581树状数组,离线处理
「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,081树状数组,离线处理,莫队算法
「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,401递推与动规,树状数组
「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,468treap,树套树,树状数组
「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,262树套树,线段树,树状数组
「BZOJ1103」[POI2007] 大都市meg
Description在经济全球化浪潮的影响下,习惯于漫步在清晨的乡间小路的邮递员BlueMary也开始骑着摩托车传递邮件了。不过，她经常回忆起以前在乡间漫步的情景。昔日，乡下有依次编号为1..n的n个小村庄，某些村庄之间有一些双向的土路。从每个村庄都恰好有一条路径到达村庄1（即比特堡）。并且，对于每个村庄，它到比特堡的路径恰好只经过编号比它的编号小的村庄。另外，对于所有道路而言，它们都不在除村庄以外的其他地点相遇。在这...
22014年6月15日7,443dfs序,树状数组
NOIP2013火柴排队
描述涵涵有两盒火柴，每盒装有n根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：∑ i=1 n (a i −b i ) 2 ，其中a i 表示第一列火柴中第i个火柴的高度，b i 表示第二列火柴中第i个火柴的高度。每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数...
22014年5月30日6,488树状数组
「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日4,223树状数组
「BZOJ1452」[JSOI2009] Count
DescriptionInputOutputSampleInputSampleOutput12HINT题解发现第一次写二维树状数组妈蛋就是多了一层for。。。对于每种颜色开一个二维树状数组水过。。。[crayon-67401e7342dde376426975/] ...
22014年5月29日5,069树状数组
「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日3,694递推与动规,树状数组
「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日2,880树状数组