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

hdu3642题目链接

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

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

思路:

线段树+扫描线。

由于Z的坐标范围比较小,我们的做法是 利用“微分”的[……]

Read more

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

题目链接

题意:

求矩形周长并。

思路:

线段树+扫描线。

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

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

 

需要注[……]

Read more

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

题目链接

题意:

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

思路:

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

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

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

Read more

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

hdu1542题目链接

题意:

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

思路:

扫描线+线段树

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

 

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

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

[……]

Read more

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

zoj3606题目链接

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

Read more

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

题目链接

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

思路:很容易想到的是,由于[……]

Read more

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

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

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

猜测:肯定要维护一个区间中hill的[……]

Read more

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

题目链接

题意:

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

下面高山脉简称”HM”

sum:区间中HM的总长度。

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

lh,rh:区间中包含左端[……]

Read more

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

题目链接

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

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

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

lm:[……]

Read more

codeforces 240 F. TorCoder (线段树)

题目链接

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

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

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

每次统计询问区间中每[……]

Read more

codeforces 558 E. A Simple Task (线段树优化计数排序)

题目链接

题意:给出一个字符串,仅由小写字母组成。现在给出q个操作,每个操作l,r,k三个参数,k=1表示把区间[l,r]变为升序排列,k=0表示把区间[l,r]变为降序排列。

思路:首先,最重要的一点是,由于只有26个字母,联想到计数排序。

对于字符集数目比较小情况,一定要想到计[……]

Read more

codeforces 145 E. Lucky Queries (线段树lazy标记)

题目链接

题意:给出一串只由数字’4’和’7’组成的串。两种操作,一种是询问整个串中最长非下降子序列的长度,另一种给出区间[l,r],将区间中的没个数反转,反转的定义为,4变成7,7变成4.

思路:线段树lazy标记。

线段树的域记录5个信息,c4,c7,c47,c74,flip,[……]

Read more