hdu1542题目链接

题意：

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

思路：

扫描线+线段树

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

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

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

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

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

第二点是扫描线的思想：

题目链接

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

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

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

题目链接

题意：

在二维坐标平面内进行_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最小的。

阅读更多

cf682B题目链接

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

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

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的元素反转... 思路：先离散化，然后注意读入....

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

• 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 …

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

１：对于一组乱序数列，每次只能交换相邻元素，达到有序交换的次数就是原数列中你逆序对的个数。

　　cf上好像总喜欢出这个题。。。我印象中就出现三次了。。。。。

wa了两次，原因是在同一个点可能有多个基地。。。

所以用set 是错误的，应该用multiset

然后因为这道题看到了map+set实现离散化的另外一种写法