离散化 线段树 HDU 5124

关于离散化

离散化是什么：一些数字，他们的范围很大（0-1e9），但是个数不算多（1-1e5），并且这些数本身的数字大小不重要，重要的是这些数字之间的相对大小（比如说某个数字是这些数字中的第几小，而与这个数字本身大小没有关系，要的是相对大小）（6 8 9 4 离散化后即为 2 3 4 1）（要理解相对大小的意思）（6在这4个数字中排第二小，那么就把6离散化成2，与数字6本身没有关系， 8,9,4亦是如此）

我个人觉得“离散化”根据其功能明明应该命名为“聚敛化”

更多关于离散化 https://blog.csdn.net/xiangaccepted/article/details/73276826

Description

John has several lines. The lines are covered on the X axis. Let A is a point which is covered by the most lines. John wants to know how many lines cover A.

题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=5124

Input

The first line contains a single integer (the data for less than 11 cases),indicating the number of test cases.
Each test case begins with an integer ,indicating the number of lines.Next N lines contains two integers and ,describing a line.

Output

For each case, output an integer means how many lines cover A.

Sample Input

2
5
1 2 
2 2
2 4
3 4
5 1000
5
1 1
2 2
3 3
4 4
5 5
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13

Sample Output

3

1

Code of 离散化部分

        for(int i = 0; i < n; ++i)
        {
//            cin >> b[i] >> c[i];
            scanf("%d%d", &b[i], &c[i]);///cin就超时，scanf就过...
            tem[tot++] = b[i];
            tem[tot++] = c[i];
        }
        sort(tem, tem + tot);
        int m = unique(tem, tem + tot) - tem;
        init(1, 1, m);
        for(int i = 0; i < n; ++i)
        {                ///+ 1 是为了让区间标号从1开始
            int tl = lower_bound(tem, tem + m, b[i]) - tem + 1;
            int tr = lower_bound(tem, tem + m, c[i]) - tem + 1;
            update(1, tl, tr);
        }
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

m记的是不同的元素个数，也就是要“聚敛“到 1 ~ m这个区间上

lower_bound操作等效聚敛

Code of this problem

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;

struct node
{
    int L, R;
    int val;
    int mmax;
} a[N << 2];

int b[N];
int c[N];
int tem[N << 1];

void down(int x)///对标号为x的区间的左右孩子区间更新val、mmax
{
    if(a[x].val)
    {
        a[x << 1].val += a[x].val;
        a[x << 1].mmax += a[x].val;
        a[x << 1 | 1].val += a[x].val;
        a[x << 1 | 1].mmax += a[x].val;
        a[x].val = 0;
    }
}

void init(int num, int l, int r)
{
    a[num].L = l;
    a[num].R = r;
    a[num].val = 0;
    a[num].mmax = 0;

    if(l == r)
        return ;

    int mid = (l + r) >> 1;
    init(num << 1, l, mid);
    init(num << 1 | 1, mid + 1, r);
}

void update(int num, int l, int r)
{
    if(a[num].L == l && a[num].R == r)
    {
        a[num].val++;
        a[num].mmax++;
        return ;
    }

    if(a[num].L == a[num].R)
        return ;

    down(num);

    int mid = (a[num].L + a[num].R) >> 1;
    if(mid >= r)
        update(num << 1, l, r);
    else if(mid < l)
        update(num << 1 | 1, l, r);
    else
    {
        update(num << 1, l, mid);
        update(num << 1 | 1, mid + 1, r);
    }

    a[num].mmax = max(a[num << 1].mmax, a[num << 1 | 1].mmax);
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        memset(b, 0, sizeof(b));
        memset(c, 0, sizeof(c));
        memset(tem, 0, sizeof(tem));
        int n;
        cin >> n;
        int tot = 0;
        for(int i = 0; i < n; ++i)
        {
//            cin >> b[i] >> c[i];
            scanf("%d%d", &b[i], &c[i]);///cin就超时，scanf就过...
            tem[tot++] = b[i];
            tem[tot++] = c[i];
        }
        sort(tem, tem + tot);
        int m = unique(tem, tem + tot) - tem;
        init(1, 1, m);
        for(int i = 0; i < n; ++i)
        {
            int tl = lower_bound(tem, tem + m, b[i]) - tem + 1;
            int tr = lower_bound(tem, tem + m, c[i]) - tem + 1;
            update(1, tl, tr);
//            cout << tl << ' ' << tr << '\n';
        }
        cout << a[1].mmax << '\n';
    }
    return 0;
}
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107