关键词：
今天偶然遇到了一个有点意思的问题，将它转化成了题目，有点令人怀念：
有一张活动排期表，表上有n组活动的排期。其中，每组活动都会开启若干次，每个活动都有一个唯一id和一个开启时间a，关闭时间b。同组活动不能在相同时间内开启两个及以上。如果同组活动同时开启，则会产生冲突，活动开启失败。问：当前活动表内是否存在冲突？如果存在，是哪几个冲突？（如果活动表中id为x的活动和id为y的活动冲突，且x<y，则y是冲突的活动）
输入：只有一组数据，数据分为若干行，每行数据包含本次活动的唯一id，这个活动所属组号i，活动开启时间a，活动关闭时间b。每组数据内部每个参数用制表符" "分隔。各行唯一id保证从小到大排列。
输出：首行输出“Success”或“Failed”，表示活动表排期成功或失败。
如果失败，接下来输出所有冲突的活动。输出格式为“Error: 唯一id”。每个错误占一行。
不同组的错误按照组号从小到大输出。
ps：需保证id小的活动不产生冲突。比如，当x>y>z时，x与z冲突，y与z冲突，且x和y不冲突，则只输出一次“Error: z”。而如果x与y冲突，x与z也冲突，则y与z都需要输出，输出:
“Error: y”
“Error: z”
输入样例：
1 1 1 10
2 2 1 10
3 1 12 15
4 1 5 11
输出样例：
Failed
Error: 4
看到这个题目，很容易想到，首先将这些输入数据按照活动组号分组，比如输入样例1,3,4行为一组，第2行为一组。
然后在组内进行两两比较，第1行和第3行比较，因为1-10和12-15没有重合，所以第1行和第3行不冲突。第1行和第4行比较，因为5>=1且5<=10，所以1-10和5-11有重合，这两行冲突了。然后第3行和第4行比较，这两行没冲突。
这种方法花费的时间与输入样例中活动的组数和每组活动的行数有关，为∑((ai)^2)/2。i为每组数据的组号，ai为每组数据包含的行数。估算时间复杂度为O(n^2)，n为行数。
由于“ps”里的内容，可以使用一种优化——当前数据和前面的数据产生冲突时，记录Error然后直接返回。比如第4行数据和第1行数据比较后，不再和第3行数据比较。
这是我想起来的第一种算法。这种算法的优点是简单明了，一个一个比较就好。缺点是当每组数据规模巨大时，消耗的时间成平方增长。
我好不容易遇到一个有点意思的问题，怎么能这样放弃？于是我稍微思考了一会儿。想出了一个新办法：
之后只针对每组数据组内的处理进行描述，因为组与组之间没有关联，不需要额外处理。
我们设置一个bool型数组，初始全部置为0。每取一行数据，就以这组数据开始时间到结束时间之间的所有数字为下标，遍历数组内这些下标的值，如果存在一个值为1，则记录这行数据为error，否则将数组内这些下标的值置为1。
第一组数据，初始有一个数组flag=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]。
读入第1行后，置为flag=[1,1,1,1,1,1,1,1,1,1,0,0,0,0,0]。
读入第3行后，置为flag=[1,1,1,1,1,1,1,1,1,1,0,1,1,1,1]。
读入第4行时，因为5-11中，flag[5-10]都已经为1了，所以产生冲突。
使用这种方法，处理每组数据花费的时间为组内每行数据的(结束时间-开始时间+1)之和，所有组的时间为∑(bi-ai+1)。估算时间复杂度为O(n*(b-a))，n为行数。
只需要(b-a)<n，这种算法消耗的时间就极有可能小于第一种算法。
但这就结束了吗？
当然还没有结束！
沿着这条思路走下去，我们的需求已经很明确了！“区间修改”+“区间查询”！没错，就是它——线段树！
使用线段树，可以使单次区间修改和查询的时间复杂度变为O(log(b-a)),那么最后这个算法的总时间复杂度为O(n*log(b-a))！
几乎可以肯定，这种算法消耗的时间一定小于前两种！
我选择了第一种算法。
写第一种算法连1分钟都不需要，写线段树保守估计一个小时起，毕竟已经好久没写过了。可需要处理的数据量只有几百条。无论哪种算法都可以在0.01秒之内解决。
而且，这次用的是python，我从没用python写过复杂的数据结构——确切的说，我之前连python自带数据结构都不清楚，语言功底极差。
最后我花了一个小时弄明白了python自带的数据结构，花了5分钟写完了全部代码，然后调通代码又花了1个小时。
代码（因需求与题目描述有少许不同，所以有些差异）——
1 #!/usr/bin/python 2 # -*- encoding:utf8 -*- 3 import sys, os, io 4 import string 5 import commands 6 import time, datetime 7 8 actArr = 9 errArr = 10 11 def checkactivity(): 12 file = open(‘activity.txt‘) 13 14 errCnt = 0 15 linenum = 0 16 for fileLine in file: 17 18 19 linenum += 1 20 if (linenum <= 3): 21 continue 22 23 id = int(fileLine.strip(‘ ‘).split(‘ ‘)[0]) 24 enable = int(fileLine.strip(‘ ‘).split(‘ ‘)[2]) 25 group = int(fileLine.strip(‘ ‘).split(‘ ‘)[3]) 26 starttime = fileLine.strip(‘ ‘).split(‘ ‘)[4] 27 endtime = fileLine.strip(‘ ‘).split(‘ ‘)[5] 28 29 timeArray = time.strptime(fileLine.strip(‘ ‘).split(‘ ‘)[4], "%Y-%m-%d-%H:%M:%S") 30 starttime = int(time.mktime(timeArray)) 31 timeArray = time.strptime(fileLine.strip(‘ ‘).split(‘ ‘)[5], "%Y-%m-%d-%H:%M:%S") 32 endtime = int(time.mktime(timeArray)) 33 34 # print enable,group,starttime,endtime 35 if(enable == 0): 36 continue 37 38 tmpArr = [id, enable, group, starttime, endtime] 39 40 actArrTmp = [] 41 if(group in actArr): 42 for arrLine in actArr[group]: 43 44 45 if( (arrLine[3] <= starttime and arrLine[4] >= starttime) or ( arrLine[3] <= endtime and arrLine[4] >= endtime ) ): 46 errArr[errCnt] = [0, arrLine[0], enable, group, arrLine[3], arrLine[4]] 47 errCnt = errCnt+1 48 errArr[errCnt] = [1, id, enable, group, starttime, endtime] 49 errCnt = errCnt+1 50 break 51 actArrTmp = actArr[group] 52 53 actArrTmp.append(tmpArr) 54 actArr[group] = actArrTmp 55 #print actArr[group] 56 57 for errIndex in errArr: 58 print ‘error id: ‘,errArr[errIndex][1] 59 60 if(errCnt == 0): 61 print "Success!" 62 63 file.close() 64 65 checkactivity()
rmq类问题利器：线段树(代码片段)
...的区间修改与查询1、修改2、查询五、离散化线段树六、算法练习[LeetCode307单点修改问题](https://leetcode.cn/problems/range-sum-query-mutable/)[LeetCode732区间修改问题](https://leetcode.cn/problems/ 查看详情
10.25算法训练——裸线段树(代码片段)
题目大意：对N（1<=N<=50000）个数进行连续进行M（1<=M<=200000）次询问：问1-N之间任意连续区间最大值和最小值之差。之前学过线段树，学的是模版题，求解的问题是在一段区间内任意加减，然后再询问任意一段之区间的... 查看详情
rmq类问题利器：线段树(代码片段)
...2、查询四、线段树的区间修改与查询1、修改2、查询五、算法练习[LeetCode307单点修改问题](https://leetcode.cn/problems/range-sum-query-mutable/)[LeetCode732区间修改问题](https://leetcode.cn/problems/my-calen 查看详情
算法xio讲堂#2--线段树(代码片段)
...段树个人理解和运用时，认为这个是一个比较实用的优化算法。这个东西和区间树有点相似，是一棵二叉搜索树，也就是查找节点和节点所带值的一种算法。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时... 查看详情
算法模板-线段树(代码片段)
本文为CSDN博主「maplezys」的原创文章，本文转载自https://blog.csdn.net/qq_41006629/article/details/124131368。简介线段树（SegmentTree）是稍高级一点的数据结构，它一般用于维护区间信息。线段树是一棵平衡二叉树，其根... 查看详情
算法模板-线段树(代码片段)
本文为CSDN博主「maplezys」的原创文章，本文转载自https://blog.csdn.net/qq_41006629/article/details/124131368。简介线段树（SegmentTree）是稍高级一点的数据结构，它一般用于维护区间信息。线段树是一棵平衡二叉树，其根... 查看详情
解析·优化zkw线段树(代码片段)
...效率极高，代码也极短，成为了OI比赛中极为实用的优化算法之一。虽然ZKW线段树无法处理有运算优先级的线段树问题，但是在一般的问题上和常数偏大的问题上总能带来极强的游戏体验。ZKW线段树的建树普 查看详情
一般线段树与权值线段树(代码片段)
目录一般线段树与权值线段树1.算法分析1.1一般线段树1.2权值线段树2.板子2.1线段树入门2.1.1单点修改+区间查询2.1.2区间修改+区间查询2.1.3区间加乘操作2.1.4区间染色2.2权值线段树2.2.1求第k大、前驱、后继等3.例题3.1线段树入门3.2... 查看详情
主席树（可持久化线段树）(代码片段)
...e主席的大大在写一道题时因为不会划分树就临时yy出一个算法，于是，这算法就这么诞生了。作用对区间求(kth)思想思考优化策略一列数，可以对于每个点i都建一棵权值线段树，维护1~i这些数，每个不同的数出现的个数（权值线... 查看详情
线段树合并浅谈(代码片段)
...至是加上历史化版本的查询,我们就不得不求助于其他的算法,本篇将对线段树合并进行讲解线段树合并一般用于对子树的统计,一般的套路就是对树的每一个节点都开上一颗动态开点线段树,然后统计子树信息时,合并所有儿子信息,... 查看详情
线段树入门到自闭(代码片段)
算法介绍线段树是一种二叉树，也就是对于一个线段，我们会用一个二叉树来表示。可以进行一些区间的修改和查询。算法详解线段树通用的build方法voidbuild(intk,intl,intr) if(l==r) sum1[k]=tree[l];//求和或者最值 sum2[k]=tree[l]*tree[l];//... 查看详情
线段树数据结构详解(代码片段)
...顾名思义，是一种树形数据结构，适用于各种求区间统一算法的动静两平衡的数据结构。这里什么是统一算法？（自己口胡的统一算法）比如求最大值or最小值、区间求和，一样的区间都是一样的算法，这也是和动态dp不同的地... 查看详情
线段树合并(代码片段)
（鸽王归来）算法简介线段树合并可以将2个权值线段树合并为一个。实现很简单，我们的操作如下：2棵线段树都有的节点，把它们的值合并。只有一颗线段树有节点，那么合并出来的线段树节点的值就是这个节点的值。依次递... 查看详情
acm常见算法考点_线段树(代码片段)
功能：区间查询和单点修改。线段树的本质就是采用空间换取时间的方式，将数组的每一个可能的区间的结果都存储到一个树里面，这样在查询是就很快。因为采用二叉树的形式存储，所以修改区间内一个值的也... 查看详情
扫描线算法的介绍与论证(代码片段)
扫描线算法的介绍与论证引言：笔者看过几篇网上的扫描线算法教程，但是总觉得网上的博客讲的有疏漏。有一些性质博客作者认为它们显然成立，忽略了它们，而读者不明白这些性质的原理，被蒙在鼓里。扫描线算法的核心在... 查看详情
非原创codeforces1070ccloudcomputing线段树&树状数组(代码片段)
...天，维护当前天K个cpu的最小花费。具体方法是维护两个线段树（树状数组也可以），维护每一天可以使用的cpu数和价格*cpu数的前缀和。注意数组下标是价格（1e6的数组。（不明白的话可以看代码，代码思路很清晰附学习博客的 查看详情
《算法竞赛进阶指南》0x43线段树扫描线算法poj2482(代码片段)
...每个点框定的区域，求区域叠加的最大值，可以通过如下算法：将每个可行点都标记，记录这些点上的权值，维护一个叶结点是一个权值点的线段树，更新的时候注意，由于所有的点都是可行点，所以右边界要在最后删除，遇到... 查看详情
线段树延迟更新(代码片段)
title:线段树延迟更新date:2018-10-1018:50:49tags:acm算法categories:ACM-线段树概述暑假集训的时候好多东西只学了个皮毛，，，对付模板题还能试试，，，但是一看一些稍难的一些题时，，，肯定单纯的套模板是不行得了，，，那样多没... 查看详情