BZOJ 1230: [Usaco2008 Nov]lites 开关灯 (线段树区间修改,区间查询)

 

1230: [Usaco2008 Nov]lites 开关灯

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1676  Solved: 874
[Submit][Status][Discuss]

Description

Farmer John尝试通过和奶牛们玩益智玩具来保持他的奶牛们思维敏捷. 其中一个大型玩具是牛栏中的灯. N (2 <= N <= 100,000) 头奶牛中的每一头被连续的编号为1..N, 站在一个彩色的灯下面.刚到傍晚的时候, 所有的灯都是关闭的. 奶牛们通过N个按钮来控制灯的开关; 按第i个按钮可以改变第i个灯的状态.奶牛们执行M (1 <= M <= 100,000)条指令, 每个指令都是两个整数中的一个(0 <= 指令号 <= 1). 第1种指令(用0表示)包含两个数字S_i和E_i (1 <= S_i <= E_i <= N), 它们表示起始开关和终止开关. 奶牛们只需要把从S_i到E_i之间的按钮都按一次, 就可以完成这个指令. 第2种指令(用1表示)同样包含两个数字S_i和E_i (1 <= S_i <= E_i <= N), 不过这种指令是询问从S_i到E_i之间的灯有多少是亮着的. 帮助FJ确保他的奶牛们可以得到正确的答案.

Input

* 第 1 行: 用空格隔开的两个整数N和M

* 第 2..M+1 行: 每行表示一个操作, 有三个用空格分开的整数: 指令号, S_i 和 E_i

Output

第 1..询问的次数 行: 对于每一次询问, 输出询问的结果.

Sample Input

4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4
输入解释:
一共有4盏灯; 5个指令. 下面是执行的情况:

1 2 3 4
Init: O O O O O = 关 * = 开
0 1 2 -> * * O O 改变灯 1 和 2 的状态
0 2 4 -> * O * *
1 2 3 -> 1 输出在2..3的范围内有多少灯是亮的
0 2 4 -> * * O O 改变灯 2 ,3 和 4 的状态
1 1 4 -> 2 输出在1..4的范围内有多少灯是亮的

Sample Output

1
2
考虑一次翻转对区间[L,R]的贡献
开着的灯数等于当前区间长度减去之前区间[L,R]内开着的灯数
也就是tree[rt].sum = r-l+1-tree[rt].sum;
对于lazy标记,无非是从0变到1,从1变到0.
手误写错了一个地方,2A

 

hdu 3642 Get The Treasury (线段树+扫描线,求长方体体积交)

hdu3642题目链接

题意:给出若干个(1000)长方体,求至少交三次的空间的体积。

尺寸为[x1,x2],[y1,y2],[z1,z2],其中x,y的坐标的绝对值不超过1E6,Z的坐标的绝对值不超过1E9.

思路:

线段树+扫描线。

由于Z的坐标范围比较小,我们的做法是 利用“微分”的思想,将每个长方体,想成若干的高度为1的矩形(矩形片)

因此就转化成了求矩形至少交三次的面积

其中和矩形交,也就是矩形至少交2次的面积比较类似,只不过线段树多维护一个至少三次覆盖的长度的域。

 

假设我们有一个长为5,宽为6,高为7的长方体

那么我们就要将其拆成7个,长为5,宽为6的矩形

将所有长方体处理完之后,枚举高度,对于每一个高度,如果矩形大于等于三个,就做一个“矩形的三次面积交”操作,将答案累加。

2A,PushUp的时候写错了一句。。。即如果父亲节点已经覆盖了两次,那么父亲节点被覆盖三次的是从左右儿子被覆盖一次的情况得来的

 

 

 

hdu 1828 Picture (线段树+扫描线 求 矩形周长并)

题目链接

题意:

求矩形周长并。

思路:

线段树+扫描线。

和前面的求面积并比较类似,我们先考虑平行x轴的线段,考虑线段树,维护的一段区间中被矩形覆盖的次数cnt和至少覆盖一次的长度的len.

只不过我们这次求的是每条扫描线的长度对周长的贡献,因此不需要乘高度。

 

需要注意的是,每条扫描线对周长的贡献,是目前扫描线的长度,与上一次扫描线长度的差的绝对值。(不是与上一次答案的差的绝对值!)

演示x轴求长度和的部分  图片来自 lwt聚聚的博客
这里写图片描述

以及一个小细节是,求面积的时候,最后一条扫描线对答案是没有贡献的(因为每次是求当前扫描线与下一条扫描线之间的面积)

但是求周长的时候,最后一条扫描线是一定会对答案有贡献的。

 

hdu 1255 覆盖的面积 (扫描线+线段树 求矩形面积交)

题目链接

题意:

求n(1000)个矩形的面积交,也就是至少有2个矩形覆盖的区域的面积

思路:

矩形面积并_hdu1542解题报告    类似

面积并问题中,线段树len维护的是至少覆盖一次的区域的长度

在面积交的问题中,我们需要多维护一个”至少覆盖两次的区域的长度”的域(设为double two;)

同时也要维护至少覆盖一次的区域的长度(设为double one;),是因为至少覆盖两次的区域的长度可以由至少覆盖一次的区域长度得到(好像是废话)

PushUp的时候要格外注意当前节点被完整覆盖一次的情况。

此时tree[rt].two 可以由两个子区间的one的情况想加得到

因为rt节点被完整覆盖了至少一次,那么如果rt儿子区间中被覆盖了至少一次,对于rt区间中被rt<<1和rt<<1|1覆盖至少一次的区间在对于rt区间就已经覆盖了至少2次

 

以及要注意题意说得不够清楚。最后保留2位小数是四舍五入。

读入的实际上是左下角和右上角的点。。。。

 

 

 

hdu 1542 Atlantis (线段树+扫描线求矩形面积并,模板题)

hdu1542题目链接

题意:

求n(100)个矩形的面积并。

思路:

扫描线+线段树

题目是2000年中欧区域赛的题目,虽然年代久远,但是有好几个点还是很值得学习的。

 

首先是离散化的适用范围:

之前比较常用的是将比较大的整数值离散化,常常是因为数值太大无法作为下标。

那么其实,浮点数有的时候也需要进行离散化,比如作为数组的下标,比如用来枚举。

做法上是和将较大的整数值离散化没有区别,因为遇到的题目不多,所以特意记录一下。

 

第二点是扫描线的思想:

其实扫描线的思想很早就接触过,noip2011的时候,tyvj上有一道类似的题目,不过是一唯的,当时印象深刻的是@Ocean 兄的那个比喻:

一段公路上右很多区间要收不同的费用,区间的开始给一个标记,表示该段区间对答案有贡献,区间的结束拿走该标记,表示该段区间对答案的贡献结束。

这就是扫描线的思想。

 

第三个是处理线段覆盖问题的一般做法:

通常线段树的节点处理的都是点,处理线段的时候就会比较麻烦。

  另外很重要的一点就是, 线段树都是维护一个点集, 但是对于边的问题就会变得很麻烦,  我们可以按照区间左端点建立线段树, 那么一个点表示的就不是点了, 而是起点在这个点的一个线段。  这样的话, 右区间就要相应的-1, 例如更新区间[1, 4], 就相当于更新标号为[1, 3]的线段。

这也是处理线段覆盖问题的通用方法。

对于上面引用中提到的例子中“更新[1,4],就相当于更新标号为[1,3]的线段”,是因为标号为1的节点代表区间[1,2],标号为2的节点代表区间[2,3],标号为3的节点代表期间[3,4]

 

接下来具体讨论这道题目的做法:

将矩形按平行x轴方形构建扫描线(只是思想,不用实际构造),

每个矩形2条平行x轴的边分类{上边,下边}2类,如果我们从下往上“扫描”线,那么[下边]就表示了对答案贡献的开始,[下边]就表示了对答案贡献的结束。

  • 扫描线扫描的过程(建议配合代码模拟)

    以下图转载自@kk303的博客

初始状态

初始状态

这里写图片描述

扫到最下边的线, 点13更新为1

这里写图片描述

扫到第二根线, 此时S=lcnt!=0h线, 得到绿色的面积, 加到答案中去, 随后更新计数

这里写图片描述

同上, 将黄色的面积加到答案中去

这里写图片描述

同上, 将灰色的面积加到答案中去

这里写图片描述

同上, 将紫色的面积加到答案中去

这里写图片描述

 

 

 

参考资料:

HDU 1542 Atlantis(线段树:扫描线)

HDU 1542 Atlantis(线段树求矩形面积并)

矩形面积并、矩形面积交、矩形周长并(线段树、扫描线总结)

 

 

 

zoj 3606 Lazy Salesgirl (线段树,单点更新,区间合并)

zoj3606题目链接

题意:有个小女孩卖火柴,有n个人会来买,分别在时间t[i],以价格p[i],买的火柴个数为1+(k-1)%3,其中k为这是小女孩第几次卖火柴。 如果有大于w的时间没人来买火柴,小女孩就会睡着。小女孩睡着后如果有人来买火柴,那小女孩就会醒过来,但是不会卖给这个人火柴。现在问使营业额最大的基础上最小的时间间隔w。

思路: 显然,w应该是某2个顾客的来访时间只差(而不是什么任意值).

因此我们可以通过枚举相邻访问时间的顾客的访问之间之差。

我们可以从小到大枚举w,这样就可以保证得到的最大营业额的对应w最小。

构造一颗线段树,维护4个域,cnt表示区间中,确实购买了火柴的顾客的人数,sum[i] (i属于0..2) 表示一个区间中最左边的顾客购买了i+1根火柴后,该区间的最大利润。

所以其实这道题类似hdu4288解题报告           

维护sum[i]的时候,右一点绕,需要注意对于tree[rt].sum[i],我们只是说该区间的最左边的人买了(i+1)根火柴,该区间的其他人买了几根火柴无所谓,我们只想知道该区间的利润。

wa了一次。。因为虽然我们分析出w一定是某2个连续的时间的差值,一定是整数值,但是为了迷惑人。。题目还是要以6位小数输出。

 

 

 

hdu 4288 Coder (离散化, 线段树,单点更新,区间合并)

题目链接

题意:n(1E5)个操作,分为三种,add x表示将x加到集合中(保证集合中之前没有x),del x表示从集合中删掉x(保证集合中一定右x),sum表示求集合中所有元素按从小到大排列后,所有的下标中满足i%5=3的a[i]的和。1=<x<=1E9

思路:很容易想到的是,由于插入和删除元素造成的位置改变是剧烈的,因此要分别维护i%5==k,k属于0..4的元素的和。

这道题的核心点在于,由于只有1E5个操作,我们可以将元素离散化,这样做的目的是,将每个数和位置一一对应,每个位置用1或者0,表示该位置对应的元素是否在集合中。

考虑线段树,维护6个域,1个是区间中,在集合中的元素个数,剩下5个域,分别表示以该区间的端点为位置1,位置x%i=k的元素的和(k属于0..4)。因此每个叶子节点都是位置1.

考虑PushUp, 区间元素和之间累加,难点在于其他5个域的维护。

假设当前区间为rt,那么对于sum[0..4] (sum代表的就是上面说的要维护的5个域),显然区间rt<<1的答案可以直接贡献给rt.

对于rt<<1|1的答案,考虑rt<<1|1中位置为%5==x的元素和,rt<<1中的元素个数为len个,那么rt<<1|1中sum[x]对 rt中的sum[(x+len)%5]有贡献。

反推出对rt 中 sum[i]有贡献的是rt<<1|1中的sum[(i-len+5)%5)]

 

 

 

BZOJ 1012: [JSOI2008]最大数maxnumber (线段树,,单点更新)

1012: [JSOI2008]最大数maxnumber

Time Limit: 3 Sec  Memory Limit: 162 MB
Submit: 9717  Solved: 4244
[Submit][Status][Discuss]

Description

  现在请求你维护一个数列,要求提供以下两种操作:1、 查询操作。语法:Q L 功能:查询当前数列中末尾L
个数中的最大的数,并输出这个数的值。限制:L不超过当前数列的长度。2、 插入操作。语法:A n 功能:将n加
上t,其中t是最近一次查询操作的答案(如果还未执行过查询操作,则t=0),并将所得结果对一个固定的常数D取
模,将所得答案插入到数列的末尾。限制:n是非负整数并且在长整范围内。注意:初始时数列是空的,没有一个
数。

Input

  第一行两个整数,M和D,其中M表示操作的个数(M <= 200,000),D如上文中所述,满足D在longint内。接下来
M行,查询操作或者插入操作。

Output

  对于每一个询问操作,输出一行。该行只有一个数,即序列中最后L个数的最大数。

Sample Input

5 100
A 96
Q 1
A 97
Q 1
Q 2

Sample Output

96
93
96
思路:线段树即可….
只是为了回忆一下..发现线段树还是没有忘记的23333

 

codeforces #381 div2 E. Alyona and towers (线段树 区间合并)

e:题意:那个数,定义hill为一段连续的区间,满足该区间为严格单峰。现在有若干操作,每个操作是对某段区间的数同时增加一个数,问每次操作后,所有的hill中,宽度最大的(区间长度最大)的是多少。

思路:同时增加一个数很线段树。。。但是要维护什么呢。。。?

猜测:肯定要维护一个区间中hill的最大宽度…

但是合并的时候要怎么办呢。。。

考虑两个方向的合并。。。

所以还要维护一个区间中,包含右端点的向左单调减延伸的长度,以及左端点的值。

同理,要维护一个区间中,包含左端点的向右单调增延伸的长度,以及右端点的值。

那么每次pushup的时候,就是两个区间hill的最大值,以及两个方向合并的最大值中取最大。。。

。。。上面是我口胡的。。。

upd:

口胡的还是有点靠谱的(并没有2333,还是漏了情况)

具体题解见代码注释

以及,为了过这道题先过了在岛老师空间题解中提到的两道题目:

hdu 3308 题目链接

hdu 5367题目链接

 

 

 

hdu 5367 digger(动态线段树,区间合并)

题目链接

题意:

思路:线段树,要维护的域蛮多的。

下面高山脉简称”HM”

sum:区间中HM的总长度。

lsum,rsum,区间中包含左端点,右端点的高度相同的山的长度。

lh,rh:区间中包含左端点,包含右端点的的高度相同的山的高度。

llh,rrh:从左端点向右,从有段点向左的,第一个高度不相同的山的高度。

由于这道题n有1E9,没办法像以前的办法build 线段树,因此我们采用动态线段树的技巧。

官方题解:

对于求“高山脉”长度,可以利用线段树。树节点中保存左高度连续长度,左高度连续区间的高度,左高度连续区间的状态(即是否高于第一个高度不同的山),右高度连续长度,右高度连续区间的高度,右高度连续区间的状态,每段区间内的“高山脉”数量。每次更新时更新高度即可,在pushup过程中去计算新产生的“高山脉”。写起来难度不是很大,然后对于n很大且必须在线做这个条件只需对于线段树动态建立节点去维护即可

 

关于动态线段树:

平时我们做的线段树,假设区间为[1,n],那我们通常都是直接以 1 号点表示区间【1,n】,以 i*2 号点表示 i 节点代表区间的左半区间,以 i*2+1 号点表示 i 节点多代表区间的右半区间,一半空间长度都定义为4*n。
        在本题中,n比较大,直接将所有线段树中的所有节点定义出来不现实,那我们注意到,这道题实际上是对区间进行的一系列操作,那么就可能存在一个区间【l,r】,在所有处理过程中,该区间都可以被当做一个整体来看待。   如果是这样的话,我们定义出与该区间的子区间相对应的节点就没有意义了。
        动态生成线段树就是:假设对某一节点 p (代表区间【l,r】)进行处理时,并不是对整个区间[l,r]进行处理,而是对其某个子区间进行处理,那这个时候,该区间就不能一直被当做一个整体来看待,所以生成两个初始子节点lp、rp(节点之均为初始值),表示该区间的左半部分与右半部分,然后父节点 p 在对两个新生成的子节点进行更新。

 

 

hdu 3308 LCIS (线段树单点更新,区间合并)

题目链接

题意:长度为n的序列,单点更新,或者询问某一个区间中最长连续严格递增序列的长度是多少。(此处的连续为位置连续,并非数值连续,也就是3,5,7,9,这样的就是满足题意的长度为4的序列)

思路:线段树区间合并。维护三个域。

mx:区间中最长连续严格递增序列的长度

lm:包含区间左端点的最长连续严格递增序列的长度。

rm:包含区间右端点的最长连续严格递增序列的长度。

PushUp的时候,一个区间的答案显然可以从左右两个子区间的最大值得到。

还有一种可能是左右区间各取一部分,此时必须满足左区间的右端点值严格小于右区间的左端点值。

需要注意的是,如果某区间的最长连续严格递增子序列的长度等于区间长度,那么该区间可以向相应方向延伸。

查询的时候也是如此,要记得查询的时候,某一段区间对答案贡献不会超过区间长度。。

hdu有点坑。。。函数名不能命名为update…update2也不行2333

 

 

hdu 4747 Mex (线段树lazy标记)

题目连接

题意:给出n(n<=200000)个数,问所有区间[l,r]中mex的和。 (一个区间mex的定义为,这个区间中没有出现的最小的非负数)

思路:我们观察到mex(1,i)随着i增大,是不减的。(单调是线段树查询区间的时候非常好用的东西,这也是次题的突破口)

mex(1,i)可以O(n)维护出

现在我们考虑左端点向右移动对答案的影响。

当i移动到i+1时,此时序列中少了a[i],设r为最小的x,满足a[x]=a[i],那么当右断点在区间[r+1,n],mex值是没有改变的。

当右端点属于[i+1,r-1]时,mex大于a[i]的会变成a[i]。

由于我们知道从1到某区间的mex值是单调的,那么mex大于a[i]的点必然是连续的一段。

我们可以知道最左边的q,满足mex(1,q)大于a[i],然后将区间[q,r-1]成段更新为a[i]

因此整理思路,我们需要做两件事。

一个是每次区间求和,一个是找到最左边的q满足mex(1,q)大于a[i].

线段树维护三个域,max域,表示该区间中mex(1,i)的最大值;

sum域,表示该区间中mex(1,i)的和

lazy域,表示延迟标记。

可以预处理出nxt数组,表示位置i上的数下次出现最近是在nxt[i]

 

 

 

 

 

 

codeforces 240 F. TorCoder (线段树)

题目链接

题意:给一个仅由小写字母组成的字符串,然后m个操作,每个操作一个区间,要求把区间中排列成字典序最小的回文串,如果不能形成回文串,就忽略该操作。

思路:和上一道线段树优化计数排序的题目很像,几乎是一样的。

同样的,26棵线段树,每种字母对应一棵。

每次统计询问区间中每种字母的个数。

然后先判断是否能形成回文(奇数长度只有一个个数为奇数的,偶数长度不能出现个数为奇数的)

能的话重置区间,然后前后分别覆盖。

注意如果是奇数长度的话,记得先覆盖中间点。

需要注意这道题的输入输出方式不是标准的。。。而是要加文件。。。不然会MLE 1

然而Tle 19….Tle了好久。。。

2016-10-05-17-43-28-%e7%9a%84%e5%b1%8f%e5%b9%95%e6%88%aa%e5%9b%be

最后换了种线段树的写法就过了。。。

然而后面这种写法就一定好么。。。。好像也不是。。。

总之是个挺玄学的东西。。。。不管了。。。