前缀和应用 续 Starting a Scenic Railroad Service

题目链接
参考博客：
I. Starting a Scenic Railroad Service

题意：给出n个乘客的乘车区间，问在乘客自主选择座位和统一安排座位的情况下分别最少需要多少个座位。

题解：乘客自主选择座位的情况下，座位的最小数目是与某个乘车区间相交的区间数目的最大值。

相交的区间数目即：有多少区间是在这个区间内结束，或在这个区间内开始的。用前缀和分别处理上车和下车即可。

统一安排座位的情况下，座位的最小数目就是区间的最大覆盖数，同样用前缀和解决。

记录两个经典的球区间的最大覆盖数 和 最大区间交的方法。

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+8;
int sum[N],st[N],ed[N],l[N],r[N];
int n;
void Put(int a[])
{
  int top =1;
    for(int i=1;i<=n;i++)
    { if(top)top=0;
    else printf(" ");
    printf("%d",a[i]);


    }
    printf("\n");
}
int main()
{
    //int n;
    cin>>n;
    int L,R;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&L,&R);
        l[i] = L;
        r[i] = R;
        st[L]++;
        ed[R]++;
        sum[L]++;
        sum[R]--;
    }
    for(int i=1;i<=N;i++)
    {
       st[i]+=st[i-1];
       sum[i]+=sum[i-1];
       ed[i]+=ed[i-1];
    }
//    n = 10;
//    Put(st);
//    Put(ed);
//    Put(sum);
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
       ans = max(ans,st[r[i]-1]-ed[l[i]]);
    }
    cout<<ans<<" ";
    ans =0;
    for(int i=1;i<=N;i++)
    {
        ans = max(ans,sum[i]);
    }
    cout<<ans<<endl;
    return 0;
}
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+8;
int sum[N],st[N],ed[N],l[N],r[N];
int n;
void Put(int a[])
{
  int top =1;
    for(int i=1;i<=n;i++)
    { if(top)top=0;
    else printf(" ");
    printf("%d",a[i]);


    }
    printf("\n");
}
int main()
{
    //int n;
    cin>>n;
    int L,R;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&L,&R);
        l[i] = L;
        r[i] = R;
        st[L]++;
        ed[R]++;
        sum[L]++;
        sum[R]--;
    }
    for(int i=1;i<=N;i++)
    {
       st[i]+=st[i-1];
       sum[i]+=sum[i-1];
       ed[i]+=ed[i-1];
    }
//    n = 10;
//    Put(st);
//    Put(ed);
//    Put(sum);
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
       ans = max(ans,st[r[i]-1]-ed[l[i]]);
    }
    cout<<ans<<" ";
    ans =0;
    for(int i=1;i<=N;i++)
    {
        ans = max(ans,sum[i]);
    }
    cout<<ans<<endl;
    return 0;
}