线段覆盖问题

线段覆盖问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 引例 线段覆盖问题 有一根长度为L的白色条状物。有两种操作: 用一条长度为T的黑布盖住条状物的[a, a+T]这个区间(0<=a, T<=L)。 把某条黑布拿走。 输入L和n次操作，要你输出每次操作之后: 条状物上有多少个黑区间。 条状物上黑区间的总长度。 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 1—线性表 见上图示，我们可以用一个数组来保存木板的状态。 Count : array[0 .. L+1] of Integer; 一开始Count数组的所有元素置0。 如果要添加一根布条(a, T)，那么: for i ? a to a+T-1 do Count[i]?Count[i]+1 如果要撤掉一根布条(a, T)，那么: for i ? a to a+T-1 do Count[i]?Count[i]-1 每次要输有多少个黑色区间可以这样做: Count[L+1]?0 Interval?0 for i?1 to L do if (Count[i]>0) and (Count[i+1]==0) then Interval ? Interval+1 Writeln(Interval) 每次要输出黑色区间的总长度: Sum?0 for i?0 to L-1 if Count[i]>0 then Sum?Sum+1 Writeln(Sum) 这种直观的做法是对白色条状物被黑布覆盖情况的忠实模拟。虽然编程复杂度和思维复杂度都很低，但是时间复杂度过高——O(nL)。当n和L达到100000的规模是，算法就无能为力了。下面我们来看另一种思路。 分析2—线段树 整个条状物可以看作是一条长度为L的线段。建立一棵树: 根节点是[0,L]，代表整条线段。然后从根节点开始，递归的将每个节点分成尽量等长的两段，作为左右子树;直到节点变成[a,a+1]的形式为止。 这显然是一颗平衡树，深度为O(Log2L)，节点总数为O(n)(也就是说空间复杂度为O(n)，建树的复杂度也是O(n))。 对于任意一条线段，我们都可以将其分解成为树中一些线段来表示: 设根节点是Root，节点X的左孩子是LChild(x)、右孩子是RChild(x)，节点X代表的线段区间是[L(x)..R(x)]。那么添加一条黑布[a,b]可以这么进行: procedure Add(Root, a, b); begin if Root = NIL then Exit; if (a<=L(Root))and(b>=R(Root)) then {[a,b]完全包含该线段} Count[Root] ? Count[Root] + 1 {因为Root代表的线段被覆盖了，所以将其标记} else if (b<=L(Root)or(a>=R(Root)) then {[a,b]和该线段不相交} Exit {不执行任何操作} else {[a,b]和Root代表的线段有交集，但是却不完全包含} begin Add(LChild(Root), a, b); Add(RChild(Root), a, b); end; end; 撤掉一条黑布可以类似的操作，只要把Count[Root]?Count[Rotot]+1改成Count[Root]?Count[Root]-1即可。 那么上面过程的时间复杂度是多少呢, 我们用f(Root)表示执行Add(Root, a, b)的时间复杂度。下面我们证明f(Root)~O(Log2n)。 如果(a<=L(Root))and(b>=R(Root))，也就是说[a,b]完全包含了Root代表的线段，那么f(Root)=1。 否则如果(b<=L(Root)or(a>=R(Root))，也就是说[a,b]和Root代表的线段完全没有交集，那么f(Root)=1。 2009-10-30 10:16 回复 帝王攻 gyz113 97位粉丝 2楼 如果以上两项都不满足，那么[a,b]和Root代表的线段有交集，并且不是完全包含。假设[a,b]和Root的交集是[x,y]。 令m=(L(Root)+R(Root))/2，也就是说LChild(Root)代表的线段是[L(Root)..m]，RChild(Root)代表的线段是[m..R(Root)]。 首先我们归纳证明，当x=LChild(Root)或者y=RChild(Root)时，f(Root)<=Log2n成立。(这个我们称之为引理)其中n=R(Root)-L(Root)，我们对n进行归纳。 f(Root)=f(LChild(Root))+f(RChild(Root)) 1.如果x=L(Root) 如果y<=m，那么f(RChild(Root))=0，所以f(Root)=f(LChild(Root))。根据归纳假设f(LChild(Root))<=Log2n。所以f(Root)<=Log2n 如果y>m，那么: f(Root)=f(LChild(Root))+f(RChild(Root)) 此时[a,b]完全覆盖LChild(Root)，所以f(LChild(Root))=1;因为L(RChild(Root))=m，而[a,b]和RChild(Root)的交集是[m,y]，根据引理的归纳假设f(RChild(Root))<=log2(n/2)。 也就是说: f(Root)= 1+f(RChild(Root))<=1+ log2(n/2)=log2n 2.如果y=R(Root) 和x=L(Root)类似。 以上两点综合可以证明，当[a,b]和Root线段的交集在Root的左边界或者右边界重合时，f(Root)=log2n。(n=R(Root)-L(Root)) 接下来我们归纳证明对于一般情况f(Root)<=2log2n。(还是对n归纳。n=R(Root)-L(Root)) [a,b]和Root线段的交集还是设为[x,y]。m是Root线段的中点。 1.如果[x,y]完全包含于[L(Root)..m]之内，则f(RChild(Root))=0，所以: f(Root)=f(LChild(Root)) 根据归纳假设f(LChild(Root))<=2log2n。 2.如果[x,y]完全包含于[m..R(Root)]之内，则f(LChild(Root))=0。和1类似。 3.如果1., 2.都不满足，那么必然有L(Root)<=x<=m，m<=y<=R(Root)。 那么f(LChild(Root))和f(RChild(Root))就都落入了引理的研究范围，即f(LChild(Root)), f(RChild(Root))都满足<=log2n/2。 所以f(Root)= f(LChild(Root))+f(RChild(Root))<=2log2n/2<=2log2n。 综上所述，总有f(Root)<=2log2n。即f(Root)~O(log2n)。 这就是说我们插入或者拿走一根黑布的时间复杂度是O(logn)。 回到原来的题目。如何输出有黑色区间的总长度, 给每个节点加入一个属性Len，用Len(Root)表示。Len(Root)的意义就是:把以Root为根的子树中所有的黑布条叠加起来，被染黑区间的总长度。 如果Count(Root)>0，则Len(Root)=R(Root)-L(Root)。 否则Len(Root)=Len(LChild(Root))+Len(RChild(Root))。 因为每次添加/去掉布条只要改动树中至多2log2n个节点，所以也只有这2log2n个节点的Len值会出现变动，及时更新即可，时间复杂度O(log2n)。 每次添加删除布条后直接输出Len(Root)即可。新的Add过程如下: procedure Add(Root, a, b); begin if Root = NIL then Exit; if (a<=L(Root))and(b>=R(Root)) then {[a,b]完全包含该线段} Count[Root] ? Count[Root] + 1 {因为Root代表的线段被覆盖了，所以将其标记} else if (b<=L(Root)or(a>=R(Root)) then {[a,b]和该线段不相交} Exit {不执行任何操作} else {[a,b]和Root代表的线段有交集，但是却不完全包含} begin Add(LChild(Root), a, b); Add(RChild(Root), a, b); end; if Count[Root]>0 then Len[Root]=R(Root)-L(Root) 2009-10-30 10:16 回复 帝王攻 gyz113 97位粉丝 3楼 Else Len[Root]=Len(LChild(Root))+Len(RChild(Root)) end; 接下来考虑每次操作后要输出黑色区间的个数。 类似的定义Interval(Root)，表示把以Root为根的子树中的黑布条全部叠加起来，有多少个黑区间。 如果Count[Root]>0，则显然Interval(Root)=1。 否则Interval(Root)=Interval(LChild(Root))+Interval(RChild(Root))-Connect(Root) 这里Connect(Root)是关于Root的一个函数。如果LChild(Root)的右边界被染黑了、并且RChild(Root)的左边界被染黑了，那么Connect(Root)=1，否则Connect(Root)=0。 为了计算Connect(Root)我们必须对每个节点X都保存两个变量: 1. CoverLeft?{True, False}代表X的左边界有没有被黑色覆盖。 2. CoverRight?{True, False}代表X的右边界有没有被黑色覆盖。 关于CoverLeft的计算:如果Count(Root)>0，则CoverLeft(Root)?True;否则CoverLeft(Root)?CoverLeft(LChild(Root))。 关于CoverRight的计算:如果Count(Root)>0，则CoverRight(Root)?True;否则CoverRight((Root)?CoverRight(RChild(Root))。 因为每次添加/去掉黑布条只会涉及到2log2n个节点的修改，所以即时更新CoverLeft, CoverRight, Connect和Interval的时间复杂度也是O(log2n)。 整个问题解决了。时间复杂度被优化到了O(nlog2L)。 我们从两个角度分析了同一个试题。读者可以在比较中学习两种算法。 第二种算法高效的原因是采用了高级数据结构——线段树。线段树的最重要特点就是把有共同点的零散信息整合到一起。比如插入的线段如果是[0,L]，在第一个算法中就需要把0~L的每一个数组元素都访问一次，而第二个算法只要对根节点的Count值加一即可。 11.1.2 关于线段树一个更复杂的应用 上一节我们介绍了线段树的一个简单应用。 一般来说，线段树的每个节点代表一个区间。根节点代表整条线段，我们从根节点开始递归的把每个节点代表的线段分成均等的两份，作为左右儿子，直到线段被分解成为长度等于一的单位线段为止，就得到了一棵线段树(有的书上称之为区间树)。 对于每个节点要记录什么信息要根据具体题目而定。下面我们来考察一个更复杂的例子。(IOI1998的Picture) Picture A number of rectangular posters, photographs and other pictures of the same shape are pasted on a wall. Their sides are all vertical or horizontal. Each rectangle can be partially or totally covered by the others. The length of the boundary of the union of all rectangles is called the perimeter. Task Write a program to calculate the perimeter. An example with 7 rectangles is shown in Figure 1. Figure 1. A set of 7 rectanglesThe corresponding boundary is the whole set of line segments drawn in Figure 2. Figure 2. The boundary of the set of rectanglesThe vertices of all rectangles have integer coordinates.Input Data The first line of the file PICTURE.IN contains the number of rectangles pasted on the wall. In each of the subsequent lines, one can find the integer coordinates of the lower left vertex and 2009-10-30 10:16 回复 帝王攻 gyz113 97位粉丝 4楼 the upper right vertex of each rectangle. The values of those coordinates are given as ordered pairs consisting of an x-coordinate followed by a y-coordinate.Sample Input: 7 -15 0 5 10 -5 8 20 25 15 -4 24 14 0 -6 16 4 2 15 10 22 30 10 36 20 34 0 40 16 This corresponds to the example of Figure 1.Output Data The file PICTURE.OUT must contain a single line with a non-negative integer which corresponds to the perimeter for the input rectangles.Sample Output: 228 This is the contents of the output file for the example above.Constraints 0 , number of rectangles < 5000 All coordinates are in the range [-10000,10000] and any existing rectangle has a positive area. The numeric value of the result may need a 32-bit signed representation.以下是翻 译: 图片 墙上贴了一些矩形的张贴画和照片。他们的边都是垂直或者水平的。每个矩形可以部分后者全部被其他的矩形覆盖。把这些矩形看作一个整体，他们的边界长度就是他们的轮廓长度。任务 写一个程序计算轮廓长度。所有矩形的顶点坐标都是整数。输入数据 PICTURE.IN的第一行包含一个整数n，代表墙上贴了多少个矩形。在接下来的第i行描述第i个矩形，包括四个整数，分别表示矩形的左下角X坐标、左下角Y坐标、右上角X坐标和右上角Y坐标。样例输入 7 -15 0 5 10 -5 8 20 25 15 -4 24 14 0 -6 16 4 2 15 10 22 30 10 36 20 34 0 40 16 该样例对应于图1。输出数据 PICTURE.OUT包含一个非负整数，轮廓长度。样例输出 228限制 0 , n < 5000 所有的坐标都在[-10000,10000]的范围之内，所有的矩形的面积都大于0。 结果可能需要32位带符号变量保存。 分析: 这是一道国际竞赛的试题，从当时的角度来看还是很难的。不难想出O(n2)的算法。因为n<5000，所以O(n2)的时间复杂度也能胜任。但是如果n的范围扩大到100000呢,实际上利用线段树，我们可以 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 出一个时间复杂度O(nlogn)的高效算法。 比如只有两个矩形，，如下图3所示。我们根据他们的垂直边界进行“离散化”。(也就是划出很多竖线将整个图形分成很多条形区域)建立一棵空的线段树。 图3 两个矩形被“离散”成三个区域 我们从左到右依次考察每个离散区间。 如上，考察第一个离散区间。蓝色的线段显然要算入最后的“轮廓长度”。我们把蓝色线段插入线段树。 在第二个区间我们加入了另一个矩形的左边界，如上图蓝色线段。把这条线段加入到线段树中。但是用圆形圈起来的部分不应该算到“轮廓长度”里面去。究其原因，因为圆形圈起来的部分和之前已经插入的线段重合了。也就是说每插入一条新线段，只有不和之前已插入线段重合的部分才应该被算到“轮廓长度”里面去。 2009-10-30 10:16 回复 帝王攻 gyz113 97位粉丝 5楼 归纳起来:假设插入该线段前，线段树中的线段总长度是X，插入后的总长度是Y，那么对于这条线段而言就有长度为Y-X的部分要算入轮廓中。 接着考察第三个区间，我们面对的是一个矩形的右边界，如上图蓝色线段所示。在最开始的时候我们把绿色的线段插入到了线段树中，而这里蓝色线段是绿色线段的右边界、也就是终结。从此以后，绿色的线段就对结果没有任何影响了。因此我们要把绿色险段从树中删除。(实际上在线段树中，蓝色和绿色线段是同一条线段) 上图的蓝色线段中，圆形圈起来的部分不算到轮廓里面去。究其原来，是因为这个部分和除被删除线段之外的线段有交集。 归纳起来:假设删除该线段前，线段树中的线段总长度是X，删除后的总长度是Y，那么对于这条线段而言就有长度为X-Y的部分要算入轮廓中。 考察最后一个区间，又是一条右边界，把它从线段树中删除即可。因为它不和当前线段树中的任何部分重合，所以整条线段都要算入轮廓长度。 如上扫描了所有区间后，被算入轮廓的线段如下: 也就是说所有垂直的边我们都考察完毕了。接着只要把图形旋转90度，用同样的方法处理一次即可把水平的边也考察完毕。以上算法可以归纳为: 根据X坐标离散。从左到右扫描。 碰到左边界就插线段。 碰到右边界就删线段。 每次插入/删除操作之前，线段树中线段覆盖的总长度是X;之后的总长度是Y。那么应该算入轮廓的长度就是|X-Y|。(也就是Res?Res+|X-Y|) 关于如何动态维护线段树中“线段覆盖的总长度”在上一节中已经介绍了。这里不再赘述。 整个算法的时间复杂度是O(nlogn)的。实际上我们并不需要先处理垂直边，把图形旋转90度，再处理水平边。可以利用“线段树中有多少个不相交的区间”(也就是上一节例题中要求输出的第一个值)，来直接计算水平边的轮廓长度。读者可以自己思考。 通过这个例子读者可以感觉到，线段树的难度并不在它本身的操作多么复杂，而在于如何去应用它，也在于在什么情况下我们想到要去应用它。一般来说对于这种查找、统计类的题目，与区间、线段挂钩的，我们都可以考虑线段树。线段树的节点一般包含“线段总覆盖长度”和“线段覆盖的不相交区间数”这两个属性。 2 树状数组及其应用 11.2.1 引子 线段树是时空效率都非常高——时间复杂度O(logn)，空间复杂度O(n);但是系数却很大。比如线段树的每个节点都要存两个指针，指向左右孩子，等等。对于长度为n的线段，线段树有2n个节点。种种这些都加重了内存的负担。如果题目的空间限制很严格，那么使用线段树就很有可能会丢分。 下面介绍一种特殊的高效数据结构:树状数组。这种数据结构的时空复杂度都和线段树类似，但是它的系数要小得多。但是读者不要对这种数据结构抱有太大的期望，因为受限于它的结构特殊性，树状数组的应用范围并不广泛。11.2.2 定义和复杂度分析 引例2 假设有一列数{Ai}(1?i?n)，支持如下两种操作: 将Ak的值加D。(k, D是输入的数) 输出As+As+1+„+At。(s, t都是输入的数，S?T)分析1——线段树 建立一棵线段树(线段长度1~n)。一开始所有节点的Count值等于0。 对于操作1，如果把Ak的值加D，则把所有覆盖了Ak的线段的Count值加D。只有log2n条线段会受到影响，因此时间复杂度是O(log2n)。 每条线段[X..Y]的Count值实际上就是Ax+Ax+1+„+Ay的值。 对于操作2，实际上就是把[S..T]这条线段分解成为线段树中的节点线段，然后把所有的节点线段的Count值相加。类似上一节介绍的Add过程。时间复杂度也是O(log2n)。分析2——树状数组 首先定义: l(x)—x的二进制最后有多少个0 p(x)—x-2l(x) 读者可能对l(x), p(x)没有感性认识。直观的说l(x)表示x里面含有多少个2因子，比如4含有两个2，8含有三个2，12含有两个2。p(x)表示把x的二进制中最后一个1改成0之后得到的数。比如12=(1100)2，最后一个1用红色标出了，所以p(12)=(1000)2=8。又比如44=(101100)2，所以p(44)=(101000)2=40。 2009-10-30 10:16 回复 帝王攻 gyz113 97位粉丝 6楼 为了描述方便，我们还定义: S(x)—A1+A2+„+Ax(特别的S(0)=0) S(x..y)—S(y)-S(x-1)(也就是Ax+Ax+1+„+Ay) 下面我们定义树状数组: F(x)=S(p(x)+1..x) 比如F(12)=S(p(12)+1..12)=S(8+1..12)=S(9..12)=A9+A10+A11+A12。 F(x)就称之为{Ai}数列的树状数组。操作1:Ak?Ak+D。 我们必须对集合S={x | p(x)k}中的每一个元素x都执行一次F(x)?F(x)+D。另外还要对F(k)也执行F(k)?F(k)+D。 下面考虑每一个x(x>k)如何满足p(x)av(v是满足此条件的最大值):必然有bv=1, av=0。 如果bv不是x二进制表示中最后一个1，那么p(x)必然是形如(btbt-1..bvXXXX)2的形式(X表示任意数:0或者1)。因为(atat-1..av-1)2=(btbt-1..bv-1)2，bv>av，所以p(x)>k。此时的x不属于集合S。 所以bv必然是x二进制表示中的最后一个1。因为(atat-1..av-1)2=(btbt-1..bv-1)2，而且p(x)=( btbt-1..bv-100..0)2，必然有p(x)?k。如果av, av-1, „ a0这些数位全部都是0的话，那么就有p(x)=k，不满足p(x)= 0 do begin Sum ? Sum + F[x]; X ? p(x); End; 此过程正确性显然。 p(x)可以预处理。所以操作2的时间复杂度也是O(log2n)。11.2.3 树状数组的实战应用 下面是一道IOI2001的试题。 Mobile phones PROBLEMSuppose that the fourth generation mobile phone base stations in the Tampere area operate as follows. The area is divided into squares. The squares form an S′ S matrix with the rows and columns numbered from 0 to S-1. Each square contains a base station. The number of active mobile phones inside a square can change because a phone is moved from a square to another or a phone is switched on or off. At times, each base station reports the change in the number of active phones to the main base station along with the row and the column of the matrix.Write a program, which receives these reports and answers queries about the current total number of active mobile phones in any rectangle-shaped area.INPUT AND OUTPUTThe input is read from standard input as integers and the answers to the queries are written to standard output as integers. The input is encoded as follows. Each input comes on a separate line, and consists of one instruction integer and a number of parameter integers according to the following table. 2009-10-30 10:16 回复 帝王攻 gyz113 97位粉丝 7楼 Instruction Parameters Meaning 0 S Initialize the matrix size to S′S containing all zeros. This instruction is given only once and it will be the first instruction. 1 X Y A Add A to the number of active phones in table square (X, Y). A may be positive or negative. 2 L B R T Query the current sum of numbers of active mobile phones in squares (X,Y), where L , X , R, B , Y , T 3 Terminate program. This instruction is given only once and it will be the last instruction. The values will always be in range, so there is no need to check them. In particular, if A is negative, it can be assumed that it will not reduce the square value below zero. The indexing starts at 0, e.g. for a table of size 4′4, we have 0 , X , 3 and 0 , Y , 3.Your program should not answer anything to lines with an instruction other than 2. If the instruction is 2, then your program is expected to answer the query by writing the answer as a single line containing a single integer to standard output.PROGRAMMING INSTRUCTIONSIn the examples below, the integer last is the last one to be read from a line, and answer is the integer variable containing your answer.If you program in C++ and use iostreams, you should use the following implementation for reading standard input and writing to standard output:cin>>last; cout< 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 输入读入整数，向标准输出写入你对老板问题的回答。 2009-10-30 10:16 回复 帝王攻 gyz113 97位粉丝 9楼 输入数据的 格式 pdf格式笔记格式下载页码格式下载公文格式下载简报格式下载 如下:每个输入独立成一行。一个输入包括一个指示数和一些参数，见下表: 指示数 参数 意义 0 S 初始指令。整个区域由S*S个小格子组成。这个指令只会在一开始出现一次。 1 X Y A 方格(X,Y)内的开机移动电话量增加了A。A可能是正数也可能是负数。 2 L B R T 询问在矩形区域(L,B)—(R,T)内有多少部开机的移动电话。矩形区域(L,B)—(R,T)包括所有的格子(X,Y)满足L , X , R, B , Y , T。 3 终止程序。这个指示只会在最后出现一次。 所有的数据总是在给定的范围内，你不需要查错。特别的，如果A是负数，你可以认为该操作不会让该格子的开机移动电话数变成负数。格子是从0开始编号的，比如一个4*4的区域，所有的格子(X,Y)应该表示为0 , X , 3, 0 , Y , 3。对于除了2之外的指示，你的程序不应该输出任何东西。如果指示是2，那么你的程序应该向标准输出写入一个整数。编程指示在下面的例子中，整数Last是你从一行中读入的最后一个数;整数answer是你的答案。如果你使用C++语言，而且使用iostreams， 你应该用下面的实现方法来访问标准输入/舒出:cin>>last; cout<