lyzqs的博客

差分好题。

先把区间合并。

然后差分一下。

就做完了

#include <bits/stdc++.h>
#define il inline
#define Max 1000005
#define inf 0x3f3f3f3f
using namespace std;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node
{
    int l,r;
}e[Max];
int n,m,s[(Max<<1)+5],a[Max],cnt,ans,dis;
il bool cmp(node x,node y)
{
    return x.l<y.l;
}
int main()
{
    n=read(),cnt=m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=m;i++) e[i].l=read(),e[i].r=read();
    sort(e+1,e+1+m,cmp);
    for(int i=2;i<=m;i++)
    {
        if(e[i].l<=e[i-1].r) cnt--,e[i].r=max(e[i-1].r,e[i].r),e[i].l=e[i-1].l,e[i-1].l=inf;
    }
    sort(e+1,e+1+m,cmp);
    m=cnt;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            s[e[j].l-a[i]+Max]++,s[e[j].r-a[i]+Max+1]--;
        }
    for(int i=1;i<=(Max<<1);i++)
    {
        s[i]+=s[i-1];
        if(ans<s[i]) ans=s[i],dis=abs(i-Max);
        if(ans==s[i]) dis=min(dis,abs(i-Max));
    }
    cout<<dis<<' '<<ans<<endl;
}