知识点DAY3 \Huge
今天学了两个知识点，二分是复习，离散化是新知识点。
知识点1：离散化
离散化在很多数据较大的题目中都有应用，离散化就是将一个数组通过某种方式简化空间和时间复杂度，离散化后的数组与原数组的区别如下
对于原数组a，进行离散化后变为数组b,对于任意i, j满足以下条件：
1.若 a_i = b_i，则 b_i = b_j
2.若 a_i > a_j，则 b_i > b_j
可以证明有唯一解。
那么，我们来分析一波
样例：
5 10 25 10 30
答案：
1 2 3 2 4
样例是如何变为答案的呢
样例的数轴
0——5—————10———————25————30
把5变成1，把10变成2，把25变成3，把30变成4；
0—1—2—3—4
然后在按原数组顺序输出：
12324
发现了没有？实际上离散化就是把原数组排了个序，然后把重复的去掉，再把下标和数对应起来，最后按原数组的顺序输出。
总结一下：
排序，去重，存哈希表，输出
看一看代码
sort(a, a+n); // 排序
ll len=unique(a, a+n)-(a); // unique给数组去重，返回数组的去重后的长度
for(ll i=0;i<len;i++){
mp[a[i]]=i+1; // 存入哈希表
}
for(ll i=0;i<n;i++){
cout << mp[b[i]] << " "; // 输出
}
（hihi，今天学了个新名词叫哈希表，说起来好专业的感觉）
知识点2：二分
今天复习了一下二分，感觉对二分更熟悉了，之前二分就是纯凭感觉弄，现在老师教了一个非常实用的二分模版，上代码！！
ll query_id(ll x){
return lower_bound(ch.begin(), ch.end(), x)-ch.begin()+1;
}
额。。。等等，上错了，这个是二分函数二次封存的函数，虽然也能实现部分二分的功能，但是有一个非常致命的的缺点——二分答案！所以我要介绍另一种好记的二分方法
ll l=0;
ll r=n+1; // 左开右开
while(l+1<r){
ll mid=(l+r)/2;
if(符合条件){
r=mid;
}
else{
l=mid;
}
}
cout << r;
这个二分模版只要把二分条件改一下就可以在二分答案里面用了
而且非常好几
今天全班第二（比冯俊潇高4名，开心开心(^▽^)）
给个小赞赞鼓励一下
吧。球球了 
