ABC360F InterSections题解

Iceturky · 2024-07-05 10:20:36 · 题解

Link

感觉就很扫描线。

需要注意这里全部都是小于号，不能取等，在离散化的时候需要注意加入 x-1 和 x+1 。在扫描线的时候也要特别注意一下边界问题。

还有一个细节是需要初始化，因为答案对应贡献可能为 0 ，这时需要初始化为 \{0,1\} 。

注意左右端点不能取等。

(一开始写了一个酷似扫描线的枚举左端点求最优右端点的一个东西，但是挂了，调不出来)

code

const int N=6e5+5;

struct Seg_Tree{
    int t[N<<2],tag[N<<2],c[N<<2];
    void pushup(int x){
        if(t[ls]>=t[rs])
            c[x]=c[ls],t[x]=t[ls];
        else
            c[x]=c[rs],t[x]=t[rs];
    }
    void pushdown(int x){
        t[ls]+=tag[x];
        tag[ls]+=tag[x];
        t[rs]+=tag[x];
        tag[rs]+=tag[x];
        tag[x]=0;
    }
    void update(int x,int l,int r,int L,int R,int a){
        if(L<=l&&r<=R){
            t[x]+=a;
            tag[x]+=a;
            return;
        }
        if(tag[x]!=0)
            pushdown(x);
        if(L<=mid)
            update(ls,l,mid,L,R,a);
        if(R>mid)
            update(rs,mid+1,r,L,R,a);
        pushup(x);
    }
    void build(int x,int l,int r){
        tag[x]=t[x]=0;
        if(l==r)
            c[x]=l;
        else{
            build(ls,l,mid);
            build(rs,mid+1,r);
            pushup(x);
        }
    }
}T;

struct upd{
    int l,r,x,w;
    bool operator<(upd ano)const{
        return x<ano.x;
    }
}Q[N];
int tot;

int X[N],len; 

int l[N],r[N];

signed main(){
    int n=read(),limit=1e9;
    for(int i=1;i<=n;i++){
        l[i]=read(),r[i]=read();
        X[++len]=l[i],X[++len]=r[i];
        X[++len]=min(limit,l[i]+1),X[++len]=max(0ll,l[i]-1);
        X[++len]=min(limit,r[i]+1),X[++len]=max(0ll,r[i]-1);
    }
    X[++len]=0,X[++len]=limit;
    sort(X+1,X+1+len);
    len=unique(X+1,X+1+len)-X-1;
    T.build(1,1,len);
    for(int i=1;i<=n;i++){
        l[i]=lower_bound(X+1,X+1+len,l[i])-X;
        r[i]=lower_bound(X+1,X+1+len,r[i])-X;
        if(l[i]>1&&l[i]+1<=r[i]-1){
            Q[++tot]={l[i]+1,r[i]-1,1,1};
            Q[++tot]={l[i]+1,r[i]-1,l[i],-1};
        }
        if(r[i]<len){
            Q[++tot]={r[i]+1,len,l[i]+1,1};
            Q[++tot]={r[i]+1,len,r[i],-1};
        }
    }
    sort(Q+1,Q+1+tot);
    pir ans={0,1};
    int mx=0;
    for(int i=1,j=1;i<=len;i++){
        while(j<=tot&&Q[j].x==i){
            T.update(1,1,len,Q[j].l,Q[j].r,Q[j].w);
            j++;
        }
        if(mx<T.t[1]){
            ans={X[i],X[T.c[1]]};
            mx=T.t[1];
        }
    }print(ans.fi),pc(' '),print(ans.se),pc('\n');
    return 0;
}