直线上n个区间，求被覆盖次数最多的点的被覆盖次数

将区间端点离散化

变为区间加问题

1 //2018年2月14日12:02:51 2 /* 3 直线上n个区间，求被覆盖次数最多的点的被覆盖次数 4 将区间端点离散化 5 变为区间加问题 6  7 */ 8 #include 
     
       9 #include 
      
       10 #include 
       
        11 using namespace std;12 13 const int N = 100001;14 int n;15 int a[N<<1], b[N<<1];16 int dif[N];17 18 int main(){19     cin >> n;20     for(int i=1;i<=2*n;i++){21         cin >> a[i];22         b[i] = a[i];23     }24     sort(b+1, b+2*n+1);25     for(int i=1;i<=2*n;i++)26         a[i] = lower_bound(b+1, b+2*n+1, a[i]) - b;27     for(int i=1;i<=2*n;i+=2){28         int s = a[i], t = a[i+1];29         dif[s]++;30         dif[t+1]--;31     }32     for(int i=1;i<=2*n;i++)33         dif[i] += dif[i-1];34     int maxx = 0;35     for(int i=1;i<=2*n;i++)36         if(dif[i] > maxx)37             maxx = dif[i];38     cout << maxx << endl;39 40     return 0;41 }42 /*43 input: 3 [1,3], [2, 4], [2,2]44 output: 345 46 */