离散化

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·10^5) 次操作。一共有三种类型操作。 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 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.

这道题可以总结的地方不少。 １：对于一组乱序数列，每次只能交换相邻元素，达到有序交换的次数就是原数列中你逆序对的个数。 cf上好像总喜欢出这个题。。。我印象中就出现三次了。。。。。

wa了两次，原因是在同一个点可能有多个基地。。。 所以用set 是错误的，应该用multiset 然后因为这道题看到了map+set实现离散化的另外一种写法 我的代码： 代码实现 1/************************************************************************* 2 > File Name: code/hdoj/4022.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: 2015年08月01日 星期六 04时37分20秒 6 ************************************************************************/ 7 8#include<iostream> 9#include<iomanip> 10#include<cstdio> 11#include<algorithm> 12#include<cmath> 13#include<cstring> 14#include<string> 15#include<map> 16#include<set> 17#include<queue> 18#include<vector> 19#include<stack> 20#define y0 abc111qqz 21#define y1 hust111qqz 22#define yn hez111qqz 23#define j1 cute111qqz 24#define tm crazy111qqz 25#define lr dying111qqz 26using namespace std; 27#define REP(i, n) for (int i=0;i<int(n);++i) 28typedef long long LL; 29typedef unsigned long long ULL; 30const int N=2E5+7; 31const int inf = 0x7fffffff; 32 33map<int,int>xmap,ymap; 34multiset<int>x[N]; 35multiset<int>y[N]; 36int main() 37{ 38 int n,m; 39 while (scanf("%d %d",&n,&m)!=EOF) 40 { 41 if (n==0&&m==0) break; 42 for ( int i = 1 ; i <= n ; i++) 43 { 44 x[i].clear(); 45 y[i].clear(); 46 } 47 xmap.clear(); 48 ymap.clear(); 49 int tx,ty; 50 int cntx=0,cnty=0; 51 for ( int i = 1 ; i <= n ; i++ ) 52 { 53 scanf("%d %d",&tx,&ty); 54 if (!xmap[tx]) xmap[tx]=++cntx; 55 if (!ymap[ty]) ymap[ty]=++cnty; 56 x[xmap[tx]].insert(ymap[ty]); 57 y[ymap[ty]].insert(xmap[tx]); 58 } 59 int c,d; 60 set<int>::iterator it; 61 for ( int i = 1; i <= m ; i++ ) 62 { 63 scanf("%d %d",&c,&d); 64 if (c==0) 65 { 66 cout<<x[xmap[d]].size()<<endl; 67 for ( it = x[xmap[d]].begin();it!=x[xmap[d]].end();it++) 68 { 69 y[*it].erase(xmap[d]); 70 } 71 x[xmap[d]].clear(); 72 } 73 else 74 { 75 cout<<y[ymap[d]].size()<<endl; 76 for ( it =y[ymap[d]].begin();it!=y[ymap[d]].end();it++) 77 { 78 x[*it].erase(ymap[d]); 79 80 } 81 y[ymap[d]].clear(); 82 } 83 } 84 printf("\n"); 85 } 86 87 return 0; 88}

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.