- 博客(170)
- 收藏
- 关注
RSS订阅
原创 [博客搬迁]本博客搬迁至Hexo独立博客+Coding Pages
感谢大家对我的支持，本博客不再使用，全面搬迁至Coding Pages（Hexo搭建），传送门。
2017-11-26 12:40:15
1041
转载 csdn获取积分
CSDN博客获取积分方法及积分系统介绍博客积分是衡量博客水平的重要标准，博客的排名也将按照积分排列。积分规则具体如下：1、每发布一篇原创或者翻译文章：可获得10分2、每发布一篇转载文章：可获得2分3、博主的文章每被评论一次：可获得1分4、每发表一次评论：可获得1分（自己给自己评论、博主回复别人对自己博文的评论不获得积分）5、每篇博文阅读次数每超过100次：可获得1分，阅读加分最高加到100分，即每篇文章点击上万次截止6、文章被投票：顶1票加1分，踩1票减1分7、文章被管理员或博主本人删除，相
2020-08-07 17:48:47
328
4
原创 [洛谷1265] 公路修建 - prim
题目描述某国有n个城市，它们互相之间没有公路相通，因此交通十分不便。为解决这一“行路难”的问题，政府决定修建公路。修建公路的任务由各城市共同完成。修建工程分若干轮完成。在每一轮中，每个城市选择一个与它最近的城市，申请修建通往该城市的公路。政府负责审批这些申请以决定是否同意修建。政府审批的规则如下：（1）如果两个或以上城市申请修建同一条公路，则让它们共同修建；（2）如果三个或以上的城市申请修建的公路成
2017-02-08 00:11:45
604
原创 [SDOI2008] 立方体覆盖 - 矩形切割（立方体切割）
题目描述 A君近日为准备省队选拔，特意进行了数据结构的专项训练。训练过程中就遇到了“矩形面积并”这道经典问题，即：给出N个各边与坐标轴平行(垂直)的矩形，求矩形覆盖的面积之和。A君按纵坐标建立线段树后按横坐标扫描计算，轻易AC了这道题，时间复杂度为O(NlogN)。 为了强化训练，A君将问题推广到三维空间中，即：给出N个各棱与坐标轴平行(垂直)的立方体，求立方体覆盖的体积之和。为了简化问题，
2017-02-08 00:04:26
2435
原创 [2010福建] 五元组问题 - 树状数组
题目描述给定n个数字，组成数字串 A1, A2, …, An。 五元组{ i, j, k, s, t }满足以下两个条件： a) 1 ≤ i < j < k < s < t ≤ n b) Ai < Aj < Ak < As < At 例如，数字串{2, 1, 3, 4, 5, 7, 6}中，包含以下4个五元组{1, 3, 4, 5, 6}, {2, 3, 4, 5, 6}, {1,
2017-02-08 00:01:05
1206
原创 [HAOI2004] 数列 - 树状数组
题目描述一个简单的数列问题：给定一个长度为n的数列，求这样的三个元素ai, aj, ak的个数，满足ai < aj > ak，且i < j < k。输入格式第一行是一个整数n(n <= 50000)。 第二行n个整数ai(0 <= ai <= 50000)。输出格式一个数，满足ai < aj > ak (i < j < k)的个数。样例数据样例输入5 1 2 3 4 1样例输出6题目分析用树状数
2017-02-07 23:47:42
678
原创 [ZJOI2003] 密码机 - 树状数组
题目描述 一台密码机按照以下的方式产生密码：首先往机器中输入一系列数，然后取出其中一部分数，将它们异或以后得到一个新数作为密码。现在请你模拟这样一台密码机的运行情况，用户通过输入控制命令来产生密码。密码机中存放了一个数列，初始时为空。密码机的控制命令共有3种： ADD < Number > 把< Number >到数列的最后。 REMOVE < Number > 在数
2017-02-07 23:44:39
518
原创 [POJ3468] 区间操作 - 树状数组
题目描述给你N个整数A[1], A[2], … , A[N]。你需要处理两类问题： “C a b c”表示给A[a], A[a+1], … , A[b]之间的每个数都加上c(-10000≤c≤10000)。 “Q a b”求A[a], A[a+1], … , A[b]之间数字的总和；输入格式输入的第一行包含两个整数N和Q(1≤N,Q≤100000)； 第二行包含N个整数Ai(-10^9≤Ai≤
2017-02-07 23:41:07
921
原创 [HDU3584] Cube - 三维树状数组
题目描述给定一个体积为N*N*N立方体，每个单位小立方体A[x,y,z]里有一个值，初始值全部为0，我们可以对立方体进行一下两种操作： 操作“Not”：改变A[i,j,k]=!A[i,j,k]。意思是改变A[i,j,k]的值，从0->1或者1->0。 (x1<=i<=x2,y1<=j<=y2,z1<=k<=z2)。 操作“Query”：询问A[i,j,k]的值。输入格式多组测试数据。对于每组测试
2017-02-07 23:36:37
473
原创 [HDU1556] Color the ball - 树状数组
题目描述N个气球排成一排，从左到右依次编号为1,2,3….N。每次给定2个整数a和b(a<=b)，lele便为骑上他的“小飞鸽”牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第i个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？输入格式每个测试实例第一行为一个整数N(N<=100000)。接下来的N行，每行包括2个整数a b(1<=a<=b<=N)
2017-02-07 23:33:18
419
原创 [POJ3321] Apple Tree 苹果树 - 树状数组
题目描述有一棵N个结点的树，一开始每个结点上都有一个苹果，每次有两种操作： （1）C x：如果x结点上有一个苹果，那么摘下它，否则x节点上会再生出一个苹果； （2）Q x：询问以x结点为根的子树中苹果的个数； 你要对于每个Q操作，输出对应的答案。 输入格式第一行为一个数N，表示树的结点个数，默认以1为根； 接下来N-1行，每行两个数Ui,Vi，表示一条树边； 然后一行是一个数
2017-02-07 22:37:24
575
原创 [POJ3067] Japan - 逆序对
题目描述Japan plans to welcome the ACM ICPC World Finals and a lot of roads must be built for the venue. Japan is tall island with N cities on the East coast and M cities on the West coast (M <= 1000, N <=
2017-02-07 22:30:45
285
原创 [POJ2299] Ultra-QuickSort - 逆序对
题目描述In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorte
2017-02-07 22:26:47
361
原创 [POJ2481] cows - 树状数组
题目描述 农民约翰的奶牛们已经发现，越来越多的草沿山脊(看成是一个数轴)长的特别好。约翰有N头牛(编号从1到N)。每头奶牛都特别喜欢吃一定范围内的草(可能重叠)。这个范围可以看成是一个闭区间[S,E]。 例如两头牛cowi和cowj，它们喜欢吃草的范围分别为[Si,Ei]和[Sj,Ej]。如果Si<=Sj，Ej <= Ei且Ei-Si > Ej-Sj，我们就是cowi比cowj强壮。对于每头
2017-02-07 22:23:28
420
原创 [POJ2352] Stars 夜空星辰 - 树状数组
题目描述夜空中有N颗恒星（N≤100000），每颗恒星具有其坐标(x, y)（0≤x, y≤100000）。现在，天文学家要对这些恒星进行分类，分类的标准如下：对于任意一颗恒星S(x,y)，如果存在k颗恒星，其x, y坐标均不大于S，则恒星S属于k类星。 如下图所示：第5颗恒星为3类星，这是由1、2、4三颗恒星均在其左下方而得出的，类似地第2、4两颗恒星为1类星，第3颗恒星为2类星。因此在这幅图中
2017-02-07 22:16:51
814
原创 [POJ2886] 谁得到最多糖果 - 反质数+线段树
题目描述有N个孩子顺时针坐成一个圆圈且从1到N编号，每个孩子手中有一张标有非零整数的卡片。第K个孩子先出圈，如果他手中卡片上的数字A大于零，下一个出圈的是顺时针第A个孩子。否则，下一个出圈的是逆时针第(-A)个孩子。第p个出圈的孩子会得到F(p)个糖果，F(p)为p的因子数。求得到糖果数最多的是哪个孩子及得到多少糖果。输入格式输入包含多组测试数据，每组测试数据的第一行为两个整数N(0 < N ≤ 5
2017-02-07 00:30:28
470
原创 [POJ2750] 最大连续和 - 线段树
题目描述给出一个含有N个结点的环，编号分别为1..N，环上的点带有权值（可正可负），现要动态的修改某个点的权值，求每次修改后环上的最大连续和，但不能是整个序列的和。输入格式第一行为一个整数N(4<=N<=100000)； 第二行为N个用空格分开的整数； 第三行为一个整数M(4<=M<=100000)，表示修改的次数(绝对值小于等于1000)； 接下来M行，每行两个整数A和B(-1000<=B<
2017-02-07 00:20:56
1050
原创 [POJ2777] 统计颜色 - 线段树
题目描述有一个长度为L厘米板，L是一个正整数，所以我们可以把它均匀地划分成L个部分，分别从左到右编号为1，2……L，每一个部分长度都为1厘米。现在我们必须给每个部分涂色，一个部分一种颜色，要求完成以下两种操作： 1.“C A B C1”：表示从A部分到B部分涂上C1颜色。 2.“P A B”：表示从A部分到B部分涂了几种颜色。 在我们的日常生活中，我们有非常少几种颜色（红色，绿
2017-02-06 23:57:51
669
原创 [USACO5.3.2] 窗体面积 - 矩形切割
题目描述你刚刚接手一项窗体界面工程。窗体界面还算简单，而且幸运的是，你不必显示实际的窗体。有 5 种基本操作： 创建一个新窗体 将窗体置顶 将窗体置底 删除一个窗体 输出窗体可见部分的百分比（就是，不被其它窗体覆盖的部分）。 在输入文件中，操作以如下的格式出现。 创建一个新窗体：w(I,x,y,X,Y) 将窗体置顶： t(I) 将窗体置底： b
2017-02-06 21:45:22
914
原创 [NOI97] 卫星覆盖 - 矩形切割（立方体切割）
题目描述SERCOI（Space-Earth Resource Cover-Observe lnstitute）是一个致力于利用卫星技术对空间和地球资源进行覆盖观测的组织。现在他们研制成功一种新型资源观测卫星-SERCOI-308。这种卫星可以覆盖空间直角坐标系中一定大小的立方体空间，卫星处于该立方体的中心。 其中（x,y,z）为立方体的中心点坐标，r为此中心点到立方体各个面的距离（即r为立方
2017-02-06 21:39:37
1493
原创 [codevs3235] 战争 - 矩形切割
题目描述2050年，人类与外星人之间的战争已趋于白热化。就在这时，人类发明出一种超级武器，这种武器能够同时对相邻的多个目标进行攻击。凡是防御力小于或等于这种武器攻击力的外星人遭到它的攻击，就会被消灭。然而，拥有超级武器是远远不够的，人们还需要一个战地统计系统时刻反馈外星人部队的信息。这个艰巨的任务落在你的身上。请你尽快设计出这样一套系统。 这套系统需要具备能够处理如下2类信息的能力： 1.外
2017-02-06 21:37:09
605
原创 [POJ1151] Atlantis - 矩形切割
题目描述给出n个矩形，求这些矩形面积的并。输入格式输入包含多组测试数据； 每组数据的第一行包含一个整数n(1<=n<=1000)，表示矩形的个数。 接下来n行，每行四个数(不一定是整数)x1,y1,x2,y2 (0<=x1最后一行以0作为文件的结束。输出格式对于每组测试数据，输出两行； 第一行是“Test case #k”，k是组数 (开始为1)； 第二行为“Total explored a
2017-02-06 21:33:27
357
原创 [IOI 2001] 移动电话 - 二维树状数组
题目描述 假设第四代移动电话的收发站是这样运行。整个区域被分割成很小的方格。所有的方格组成了一个S*S的矩阵，行和列从0~S-1编号。每个小方格都包含一个收发站。每个方格内的开机的移动电话数量可以不断改变，因为手机用户在各个方格之间移动，也有用户开机或者关机。一旦某个方格里面开机的移动电话数量发生了变化，该方格里的收发站就会向总部发送一条信息说明这个改变量。 总部要你写一个程序，用来管理
2017-02-06 21:31:02
692
原创 [POJ2155] Matrix - 二维树状数组
题目描述给一个N*N的矩阵A，其中元素是0或1。A[i][j]表示在第i行第j列的数。最初时，A[i][j]=0(1<=i,j<=N)。我们以以下方式来改变矩阵，给定一个矩形的左上角为(x1,y1)和右下角为(x2,y2)，我们对这个矩形范围内的所有元素进行“非”操作（如果它是一个’0’，那么变化为’1’，否则它变为’0’）。请你编写一个程序完成以下两种操作： 1. C x1 y1 x2 y2 (
2017-02-06 21:27:15
317
原创 [USACO3.1.4] 形成的区域 - 线段树/矩形切割
题目描述N 个不同的颜色的不透明的长方形 ( 1 <= N <= 100 ) 被放置在一张宽为：A、 长为：B 的白纸上。这些长方形被放置时，保证了它们的边于白纸的边缘平行。所有的长方形都放置在白纸内，所以我们会看到不同形状的各种颜色。坐标系统的原点 ( 0，0 ) 设在这张白纸的左下角，而坐标轴则平行于边缘。输入格式按顺序输入放置长方形的方法。第一行输入的是那个放在底的长方形(即白纸)。 第 1
2017-02-06 21:24:21
715
原创 [USACO 2007 Open Silver] City Horizon - 离散化+线段树
题目描述输入格式输出格式样例数据样例输入4 2 5 1 9 10 4 6 8 2 4 6 3样例输出16样例说明题目分析离散化+线段树（维护最大值） 事先拍一遍序，以免出蜜汁错误源代码#include<algorithm>#include<iostream>#include<iomanip>#include<cstring>#include<cstdlib>#include<ve
2017-02-06 21:19:13
364
原创 [AHOI2009] 行星序列 - 线段树双懒标记
题目描述“神州“载人飞船的发射成功让小可可非常激动，他立志长大后要成为一名宇航员假期一始，他就报名参加了“小小宇航员夏令营”，在这里小可可不仅学到了丰富的宇航知识，还参与解决了一些模拟飞行中发现的问题，今天指导老师交给他一个任务，在这次模拟飞行的路线上有N个行星，暂且称它们为一个行星序列，并将他们从1至n标号，在宇宙未知力量的作用下这N个行星的质量是不断变化的，所以他们对飞船产生的引力也会不断变化，
2017-02-06 00:10:10
583
原创 [线段树练习5] 线段的条数 - 统计点重复标记数
题目描述X轴上从下向上依次叠放一定长度某种颜色的线段。问在某个单位区间上一共叠放了多少条线段？输入格式第1行：2个整数XC，N。XC表示X轴的颜色，1<=N<=100000，表示线段的条数。 接下来N行，每行3个整数L，R，C，-100000 <=L<=R<= 100000，表示一线段的左、右端点；1<=C<=100000，表示线段的颜色。 最后1行：1个整数P，表示单位区间的起点。-10000
2017-02-05 23:39:06
726
原创 [线段树练习4] 线段颜色条数 - 统计标记总数
题目描述X轴上从下向上依次叠放一定长度的某种颜色的线段。问从上向下看X轴，它被分成了不同颜色的多少段？输入格式第1行：2个整数XC，N。XC表示X轴的颜色，1<=N<=100000，表示线段的条数，其中X轴的范围为[-100000,100000]。。 接下来N行，每行3个整数L，R，C，-100000 <=L<=R<= 100000，表示一线段的左、右端点；1<=C<=100000，表示线段的颜色
2017-02-05 23:36:38
1018
原创 [线段树练习3] 盒子的个数 - 统计标记种类
题目描述桌子上零散地按照后先后顺序放着若干个盒子，盒子都平行于墙。桌子的后方是一堵墙。如图所示。问从桌子前方可以看到多少个盒子？假设人站得足够远。输入格式第1行：3个整数L，R，N。-100000 <=L<=R<= 100000，表示墙所在的区间；1<=N<=100000，表示盒子的个数 接下来N行，每行2个整数BL, BR，-100000 <=BL<=BR<= 100000，表示一个盒子的左、右
2017-02-05 23:24:53
742
原创 [线段树练习2] 影子的宽度 - 统计标记个数
题目描述桌子上零散地放着若干个盒子，盒子都平行于墙。桌子的后方是一堵墙。如图所示。现在从桌子的前方射来一束平行光，把盒子的影子投射到了墙上。问影子的总宽度是多少？输入格式第1行：3个整数L，R，N。-100000 <=L<=R<= 100000，表示墙所在的区间；1<=N<=100000，表示盒子的个数 接下来N行，每行2个整数BL, BR，-100000 <=BL<=BR<= 100000，表示
2017-02-05 23:21:49
665
1
原创 [COGS247] 售票系统 - 线段树懒标记
题目描述某次列车经C个城市，城市编号依次为1到C，列车上共有S个座位，铁路局规定售出的车票只能是坐票，即车上所有的旅客都有座。售票系统是由计算机执行的，每一个售票申请包含三个参数，分别用O,D,N表示，O为起始，D为目的地站，N为车票张数。售票系统对该售票申请作出受理和不受理的决定，只有在从O到D的区段内列车上都有N个和N个以上的空座位时该售票申请才被受理。 请你写一个程序，实现这个自动售票系统。
2017-02-05 23:18:02
866
原创 [线段树练习1] 线段统计 - 线段树懒标记
题目描述在数轴上进行一系列操作。每次操作有两种类型，一种是在线段[a,b]上涂上颜色，另一种将[a,b]上的颜色擦去。问经过一系列的操作后，有多少条单位线段[k,k+1]被涂上了颜色。输入格式第1行：2个整数n（0<=n<=60000）和m（1<=m<=60000）分别表示数轴长度和进行操作的次数。 接下来m行，每行3个整数i，a，b， 0 <=a<=b<=60000，若i=1表示给线段[a,b]
2017-02-05 23:14:33
2768
1
原创 [CQOI2006] 简单题 - 线段树/树状数组
题目描述有一个n个元素的数组，每个元素初始均为0。有m条指令，要么让其中一段连续序列数字反转——0变1，1变0（操作1），要么询问某个元素的值（操作2）。例如当n=20时，10条指令如下： 输入格式第一行包含两个整数n，m，表示数组的长度和指令的条数，以下m行，每行的第一个数t表示操作的种类。若t=1，则接下来有两个数L, R (L<=R)，表示区间[L, R]的每个数均反转；若t=2，则接下来只
2017-02-05 18:29:21
913
原创 [bsoj2521] 序列和 - 线段树/树状数组
题目描述给定一个初始值都为0的序列，动态地修改一些位置上的数字,加上一个数,减去一个数,然后动态地提出问题,问题的形式是求出一段数字的和。 规定： Add i d 表示将序列第i个数加上d； Sub i d 表示将序列中第i数减去d； Ask i j 询问序列i到j的所有数的和；输入格式输入文件的第一行两个整数：n m，分别表示序列的长度和有m条指令；第2行到第m+1行，都是上面
2017-02-05 18:23:22
400
原创 [bzoj3437] 小P的牧场
题目描述小P是个特么喜欢玩MC的孩纸。。。小P 在MC 里有n 个牧场，自西向东呈一字形排列（自西向东用1…n 编号），于是他就烦恼了：为了控制这n 个牧场，他需要在某些牧场上面建立控制站，每个牧场上只能建立一个控制站，每个控制站控制的牧场是它所在的牧场一直到它西边第一个控制站的所有牧场（它西边第一个控制站所在的牧场不被控制）（如果它西边不存在控制站，那么它控制西边所有的牧场），每个牧场被控制都需要
2017-02-04 23:34:12
695
原创 [APIO2010] 特别行动队
题目描述 你有一支由n名预备役士兵组成的部队，士兵从1到n编号，要将他们拆分成若干特别行动队调入战场。出于默契考虑，同一支特别行动队中队员的编号应该连续，即为形如（i，i+1，…，i+k）的序列。 编号为i的士兵的初始战斗力为xi，一支特别运动队的初始战斗力x为队内士兵初始战斗力之和，即x=（xi）+（xi+1）+…+（xi+k）。 通过长期的观察，你总结出一支特别行动队的初始战斗力x
2017-02-04 23:15:24
813
原创 [USACO 2008 March Gold] 土地购买
题目描述 农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. 如果FJ买一块3x5的地和一块5x3的地,则他需
2017-02-04 17:00:46
981
原创 [vijos1245] 座位的争执
题目描述还记得Matrix67的“非常男女”计划吗？由Matrix67策划的学校大型男女配对活动将在大礼堂隆重举行，学校里许多人即将前来捧场。大礼堂一共有n个座位，为了方便管理，Matrix67对它们从1到n顺序编号。售票工作已经完成，经统计，共有k个人拿到了入场券。由于k< n，因此大礼堂的座位完全足够。每张入场券上都印有座位号，入场者凭入场券对号入座。在这k个人即将陆续入场时，Matrix67发
2017-02-04 16:06:14
582
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人