题解：AT_abc360_f [ABC360F] InterSections

endswitch · 2024-10-10 10:08:30 · 题解

首先考虑给定的区间 [l_i, r_i] 和 一个暂定区间 [x, y] 何时相交。

根据题意，有：

则：

其中 V 为 值域。

那么同理，可得另一种情况：

将区间 [x,y] 映射到平面的点 (x, y) 上，发现上述相交的性质可以转为对点 (x, y) 的横纵坐标的上下界约束。

把这种上下界约束抽象成矩形，题目便转化为找到被最多矩形覆盖的横纵坐标最小的点。

这是扫描线经典 trick，线段树维护即可。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 5;
int n, cnt, tot, num[N << 2];
struct Node {
    int x, y1, y2, val;
    Node(int xx = 0, int yy1 = 0, int yy2 = 0, int vval = 0) {
        x = xx, y1 = yy1, y2 = yy2, val = vval;
    }
} a[N << 2];
map<int, int> lsh;

namespace SGT {
    #define mid (L + R) >> 1
    #define son p, L, R
    #define lson ls(p), L, (L + R) >> 1
    #define rson rs(p), ((L + R) >> 1) + 1, R

    struct sgt {
        int mx, id, pls;
    } t[N << 4];

    inline int ls(int p) {
        return p << 1;
    }

    inline int rs(int p) {
        return p << 1 | 1;
    }

    inline void psup(int p) {
        if(t[ls(p)].mx >= t[rs(p)].mx) {
            t[p].mx = t[ls(p)].mx;

            t[p].id = t[ls(p)].id;
        }
        else {
            t[p].mx = t[rs(p)].mx;

            t[p].id = t[rs(p)].id;
        }

        return ;
    } // 容易写挂 

    inline void build(int p = 1, int L = 1, int R = tot)  {
        if(L == R) {
            t[p].id = L;

            return ;
        }

        build(lson), build(rson), psup(p); 
    }

    inline void work(int p, int L, int R, int k) {
        t[p].mx += k;
        t[p].pls += k;

        return ;
    }

    inline void psd(int p, int L, int R) {
        if(! t[p].pls) return ;

        work(lson, t[p].pls), work(rson, t[p].pls);

        t[p].pls = 0;

        return ;
    }

    inline void add(int l, int r, int k, int p = 1, int L = 1, int R = tot) {
        if(l <= L && R <= r) {
            work(son, k);

            return ;
        }

        psd(son);

        if(l <= mid) add(l, r, k, lson);
        if(r > mid) add(l, r, k, rson);

        psup(p);

        return ;
    }

    #undef mid
    #undef son
    #undef lson
    #undef rson 
}

using namespace SGT;

inline bool cmp(Node a, Node b) {
    if(a.x == b.x) return a.val > b.val;

    return a.x < b.x;
}

signed main() {
    ios_base :: sync_with_stdio(NULL);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;

    num[++ tot] = 1e9;

    for(int i = 1 ; i <= n ; ++ i) {
        int l, r;

        cin >> l >> r;

        num[++ tot] = l + 1, num[++ tot] = r - 1, num[++ tot] = r + 1;

        a[++ cnt] = Node(0, l + 1, r - 1, 1);
        a[++ cnt] = Node(l - 1, l + 1, r - 1, -1);
        a[++ cnt] = Node(l + 1, r + 1, 1e9, 1);
        a[++ cnt] = Node(r - 1, r + 1, 1e9, -1);
    }

    sort(num + 1, num + 1 + tot);
    tot = unique(num + 1, num + 1 + tot) - num - 1;

    for(int i = 1 ; i <= tot ; ++ i)
        lsh[num[i]] = i;

    sort(a + 1, a + 1 + cnt, cmp);

    build();

    int ans = 0, posl = 0, posr = 1;

    for(int i = 1 ; i <= cnt ; ++ i) {
        add(lsh[a[i].y1], lsh[a[i].y2], a[i].val);

        if(t[1].mx > ans) {
            posl = a[i].x, posr = num[t[1].id];

            ans = t[1].mx;
        }
        else if(t[1].mx == ans && posl == a[i].x)
            posr = max(1ll, min(posr, num[t[1].id]));
    }

    cout << posl << ' ' << posr;

    return 0;
}