CF1424G Years

Solution

这个题意思很显然，是求 (n) 个区间重叠最多的地方和值。

那么我们能想到用差分数组，在扫一遍的过程中维护最大值和 (pos) 。

但是需要注意的是，区间最大会到 (10^9) ，直接差分是不行的，我们需要先对所有 (b) 和 (d) 进行离散化，然后再去差分。

代码

#include<bits/stdc++.h>

using namespace std;
const int N=5e5+10,INF=1e9;
int n,ans,sum,pos,cnt,tot,a[N],l[N],r[N],b[N],c[N];

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    return x*f;
}

int main(){
    n=read();
    for(int i=1;i<=n;i++){
        l[i]=read();
        r[i]=read();
        a[++cnt]=l[i];
        a[++cnt]=r[i];
    }
    sort(a+1,a+cnt+1);
    for(int i=1;i<=cnt;i++)
        if(i==1||a[i]!=a[i-1]) a[++tot]=a[i];
    int t1,t2;
    for(int i=1;i<=n;i++){
        t1=lower_bound(a+1,a+tot+1,l[i])-a;
        t2=lower_bound(a+1,a+tot+1,r[i])-a;
        c[t1]=l[i],c[t2]=r[i];//记录本来的位置
        b[t1]++,b[t2]--;
    }
    for(int i=1;i<=tot;i++){
        sum+=b[i];
        if(sum>ans) ans=sum,pos=c[i];
    }
    printf("%d %d
",pos,ans);
    return 0;
}