离散化

离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：
原数据：1,999,100000,15；处理后：1,3,4,2；
原数据：{100,200}，{20,50000}，{1,400}；
处理后：{3,4}，{2,6}，{1,5}；

Gym 101964E Fishermen

题意：
求每个渔民的鱼竿能钓到多少鱼，渔民都在x轴上，且每个渔民位置一定不同，在其他点上有鱼（一个点可能有好几条鱼），若渔民坐标（x，0），鱼坐标（a，b），鱼竿长为l，当且仅当满足 |a ? x| + b <= l时，这条鱼能被渔夫捕到.
分析：
求每条鱼对渔民的贡献，据鱼的坐标我们可以求出，有哪几个渔夫可以捕到这条鱼，对这些渔夫能捕的鱼加1，由于这些渔夫一定是连续的，相当于对一个区间加一，我们可以利用差分，最后跑一边前缀和即可求出在每个点上人能捕到的鱼。
但是，据数据范围渔夫坐标最大1e9，然而渔夫总是只有2e5，所以，我们考虑离散化。
AC代码：

#include <bits/stdc++.h>

using namespace std;

int n, m, l;
int x[200050], y[200050];
int d[200050];
int ans[200050];
int ar[200050];
int le, ri;
struct node
{
    int x, id;
    bool operator < (const node &b) const
    {
        return x < b.x;
    }
}br[200050];
node xx;

int main()
{
    scanf("%d%d%d", &n, &m, &l);
    for(int i = 1; i <= n; ++i) scanf("%d%d", &x[i], &y[i]);
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d", &ar[i]);
        br[i].x = ar[i];
        br[i].id = i;
    }
    sort(br + 1, br + m + 1);
    for(int i = 1; i <= n; ++i)
    {
        if(y[i] > l) continue;
        xx.x = x[i] - (l - y[i]);
        le = lower_bound(br + 1, br + m + 1, xx) - br;
        if(le > m) continue;
        xx.x = x[i] + (l - y[i]);
        ri = upper_bound(br + 1, br + m + 1, xx) - br;
        ++d[le];
        --d[ri];
    }
    for(int i = 1; i <= m; ++i)
    {
        d[i] += d[i - 1];
        ans[br[i].id] = d[i];
    }
    for(int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
    return 0;
}

/*
8 4 4
7 2
3 3
4 5
5 1
2 2
1 4
8 4
9 4
6 1 4 9
*/

在结构体里二分查找

1.写operator
2.二分函数第三个参数要是一个结构体