111qqz的小窝

老年咸鱼冲锋!

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(线段树求矩形面积并)

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

 

 

 

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)]

 

 

 

codeforces 61 E. Enemy is weak (离散化+线段树求逆序三元组)

题目链接
题意:给出n个数,求满足 i<j<k且a[i]>a[j]>a[k]的三元组有多少个。

思路:对于这种要求三个数满足条件的题目,老司机的经验是考虑中间那个数,这道题也不例外。

我们枚举j,通过求两次逆序对求出对于每个a[j],满足a[i]>a[j]的i的个数,以及满足a[j]>a[k]的个数。

两个个数的乘积就是j作为中间数满足的三元组的个数,这样把所有的j累加就是答案。

其他的就是,要离散化,以及最后答案可能会爆long long?

1A,好爽啊哈哈哈。

 

 

codeforces 19 D. Points (离散化+树套树(线段树+set))

题目链接

题意:

在二维坐标平面内进行n (1 ≤ n ≤ 2·105) 次操作。一共有三种类型操作。

1.add x,y 将点(x,y)加进坐标系。

2.remove x,y 将点(x,y)移除.

3.find x,y 找到点(x,y)右上角的点(xp>x,yp>y)。如果有多个输出x最小的。还是有多个输出y最小的。

x,y均为非负数。以上操作均合法。

思路:没有思路。。。不会啊。。。以为要二维线段树什么的。。。。总之是不会做。。。

大概从中午开始看题解。。。8个小时。。。。终于完全搞懂了orz

很巧妙得把二维问题转化成了一维问题。。。

我来说一下大概做法,具体的细节见代码注释:

在x轴方向维护一课线段树,线段树的数组tree[i]存储的信息是以i节点为根节点的子树所对应的区间能达到的最大的y值。线段树的叶子节点上是一个set,set[i]是横坐标为i时的纵坐标集合,也就是所谓的树套树。

由于x很大,但是n比较小,所以我们这里采用了stl+去重的办法离散化离散化的三种办法

对于添加和删除点的操作,我们更新完对应的set把相应的x(离散化后的)在线段树中更新就好(因为线段树的update操作是和set有关的)

对于find操作,我们首先从线段树中找到(下标大于x且最小且集合中存在大于y的元素的集合)的下标

这样我们确定了x,再upper_bound一下找到对应的集合中最小的y.

初始化由于没有插入y,所以tree可以初始化为-1,不用建树。。。(反正建了也都是-1)

 

whust 2016 warm up ||codeforces 682 B. Alyona and Mex (离散化)

cf682B题目链接

题意:给出n个数。。每个数可以任意减小到一个正整数。。。问进行恰当的操作后。。。最小的没有出现的正整数的最大可能取值。。

思路:傻逼题。。。直接离散化。。。。注意不能超过初始。。。

 

 

uva 120 Stacks of Flapjacks

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=56

题意:给出一个长度为n的序列(无重复元素),询问经过多少次flip(i)操作,使得序列升序排列。定义flip(i)为将1到n-i+1的元素反转…
思路:先离散化,然后注意读入….

codeforces 29 C. Mail Stamps

http://codeforces.com/contest/29/problem/C
题意:给出n个边的关系,保证可以构成一条链。正向或者反向输出这个链。
思路:由于下标很大(1E9),而关系个数只有1E5..需要离散化。。而且离散化的同时不能丢失边的关系。。。实际上。。直接用vector+map就好了。。。 map >e;即可。然后找到一个度为1的点。。做个dfs…

sgu 180 – Inversions (离散化+树状数组)

 – Inversions

Time Limit:250MS     Memory Limit:4096KB     64bit IO Format:%I64d & %I64u

Submit Status

Description

180. Inversions

time limit per test: 0.25 sec. 
memory limit per test: 4096 KB
input: standard 
output: standard

There are N integers (1<=N<=65537) A1, A2,.. AN (0<=Ai<=10^9). You need to find amount of such pairs (i, j) that 1<=iA[j].
Input
The first line of the input contains the number N. The second line contains N numbers A1…AN.
Output
Write amount of such pairs.
Sample test(s)
Input
 
 

2 3 1 5 4
 
 
Output
 
 
3
 
 
一直wa 2
后来发现是没处理相同元素(我好傻逼啊。。。。)
离散化的时候,很重要的一项,当然是相同的元素,离散化的之后也要变成相同的。。。
上道题过了纯粹是数据水。。。
 

poj 2299 Ultra-QuickSort (树状数组+离散化)

这道题可以总结的地方不少。

1:对于一组乱序数列,每次只能交换相邻元素,达到有序交换的次数就是原数列中你逆序对的个数。
  cf上好像总喜欢出这个题。。。我印象中就出现三次了。。。。。
2:原始数组a[i]和树状数组的t[i]的对应问题(???存在疑问。。。应该只是这道题,而不是一般规律!)
  这道题n是500000,如果直接开数组是可以开得下的,不需要离散化。但是树状数组的下标对应的是原始数组的值!也就是t[i]的下表最大可能为999,999,999 ! 显然存不下,需要离散化。
3:学习了离散化的又一种写法。

 

hdu 4022 Bombing (离散化)

wa了两次,原因是在同一个点可能有多个基地。。。
所以用set 是错误的,应该用multiset
然后因为这道题看到了map+set实现离散化的另外一种写法
我的代码:

hdu 5233 Gunner II (bc #42 B) (离散化)

Gunner II

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1433    Accepted Submission(s): 540

Problem Description

Long long ago, there was a gunner whose name is Jack. He likes to go hunting very much. One day he go to the grove. There are n birds and n trees. The i-th bird stands on the top of the i-th tree. The trees stand in straight line from left to the right. Every tree has its height. Jack stands on the left side of the left most tree. When Jack shots a bullet in height H to the right, the nearest bird which stands in the tree with height H will falls.

Jack will shot many times, he wants to know which bird will fall during each shot.

 

Input

There are multiple test cases (about 5), every case gives n, m in the first line, n indicates there are n trees and n birds, m means Jack will shot m times.

In the second line, there are n numbers h[1],h[2],h[3],…,h[n] which describes the height of the trees.

In the third line, there are m numbers q[1],q[2],q[3],…,q[m] which describes the height of the Jack’s shots.

Please process to the end of file.

[Technical Specification]

All input items are integers.

1<=n,m<=100000(10^5)

1<=h[i],q[i]<=1000000000(10^9)

 

Output

For each q[i], output an integer in a single line indicates the id of bird Jack shots down. If Jack can’t shot any bird, just output -1.

The id starts from 1.

 

Sample Input
5 5
1 2 3 4 1
1 3 1 4 2

 

Sample Output
1
3
5
4
2

Hint

Huge input, fast IO is recommended.

 

Source
因为一共才1E5的数据,而高度有1E9
所以考虑离散化
关于离散化的内容,这篇博客讲得很好。
http://blog.csdn.net/axuan_k/article/details/45954561
我是使用了第三种map+set的方法。。。
离散化大概是因为数据太大下表存不下。。。
然后map的key 值没有范围?所以实现了离散化(是这样嘛???)

还有一种写法,貌似要快一点,但是空间用的多一些: