Description

woniuxia最近很不开心，所以他准备发泄一下，虽然这没什么，但是不巧的是，他准备拿你开刀，但是 你又不可能躲避。
那么题目来了：
给定n个区间，每个区间范围为[x,y].
求最多的区间覆盖次数。

Input

多组测试数据。
n代表区间个数。1<=n<=300
接下来n行，x y 代表区间范围。0<=x
 

Output

一个数,表示区间覆盖的最大次数。

Sample Input

4 
10 20 
30 40 
50 60 
70 80 
2 
1 3 
2 200 
3 
10 100 
20 80 
30 50

Sample Output

1
2
3

Hint

 

Source

hdu
 
 
区间端点很大， 但是区间个数在可接受的范围之内。
 
记得两个月之前的某场网络赛碰见了树状数组离散化， 被卡了，打算补补离散化，后来咕了。今天又碰见了。
  
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=400;

ll a[N*2], num[N*2], x[2*N];    ///为什么开二倍：区间有俩端点
ll l[N], r[N];
int n;

int main()
{
    while(~scanf("%d", &n))
    {
        memset(a, 0, sizeof(a));
        memset(num, 0, sizeof(num));
        memset(x, 0, sizeof(x));
        memset(l, 0, sizeof(l));
        memset(r, 0, sizeof(r));
        memset(ans, 0, sizeof(ans));
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d%d", &l[i], &r[i]);    ///原数组
            r[i]++;
            a[2*i] = l[i];  ///离散化数组
            a[2*i+1] = r[i];
        }
        sort(a+1, a+2*n+1);     ///排序
        int tot = unique(a, a+2*n+1)-a;     ///去重
        for(int i = 1; i <= n; ++i)
        {
            int L = lower_bound(a, a+tot, l[i])-a;  ///找到区间左端点离散化后的位置，对应为x[]的下标
            int R = lower_bound(a, a+tot, r[i])-a;
            x[L]++;     ///差分
            x[R]--;     ///因为前面有r[i]++, 所以不需要x[R++]--;
        }
        num[0] = x[0];     ///num[]差分数组的前缀和，有点多余， 打x[]的前缀和就够了
        for(int i  = 1; i <= tot; ++i)  ///数轴上现在共tot个数
        {
            num[i] = num[i-1] + x[i];
        }
        sort(num+1, num+tot+1);
        cout<<num[tot]<<'\n';
    }
    return 0;
}