题解：AT_abc360_f [ABC360F] InterSections

· · 题解

F 题 InterSections

题意

给你 N 个区间，编号为 1 至 N。区间 i 是 [L_i,R_i]。

当且仅当两个区间 [l_i,r_a] 和 [l_b,r_b] 满足 (l_a<l_b<r_a<r_b) 或 (l_b<l_a<r_b<r_a) 时，这两个区间被称为相交。

定义 f(l,r) 为与区间 [l,r] 相交的区间 i(1\le i \le N) 的个数。

在满足 0 \le l<r\le 10^9 的所有一对整数中 (l,r)，找出使 f(l,r) 最大的一对 (l,r)。如果有多对这样的数，选择 l 最小的一对。如果仍有多对，则选择其中 r 最小的一对。(因为 0\le l<r，所以要回答的一对 (l,r) 是唯一确定的）。

分析

若所求 [l,r] 与给定区间 [L_i,R_i] 相交，那么有且仅有以下两种情况：

若将 l 当做 x 坐标，r 当做 y 坐标，可以发现，两种情况对应着点 (l,r) 在以 (L_i+1,R_i+1) 为左下角，以 (R_i-1,10^9) 为右上角的矩形内和以 (0,L_i+1) 为左下角，以 (L_i-1,R_i-1) 为右上角的矩形内。

此时，我们可以将相交转化为点在矩形内，

这两个矩形不重合。

即若指定 [l,r]，那么仅有可能与某一个矩形相交。

因此，只需要统计平面上被矩形覆盖次数最多，且最右下的点即可。

扫描线秒了。

code：

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

const int N = 1000005;
const int inf = 1e8;

int tmp[N], len;
int L[N], R[N], n;

vector<int> add[N];
vector<int> sub[N];

struct SMT {
#define ls (u << 1)
#define rs (u << 1 | 1)
    int maxx[N << 2], mpos[N << 2], tag[N << 2];
    void pushup(int u) {
        if (maxx[ls] >= maxx[rs]) maxx[u] = maxx[ls], mpos[u] = mpos[ls];
        else maxx[u] = maxx[rs], mpos[u] = mpos[rs];
    }
    void pushtag(int u, int dlt) {
        maxx[u] += dlt, tag[u] += dlt;
    }
    void pushdown(int u) {
        if (tag[u])
            pushtag(ls, tag[u]), pushtag(rs, tag[u]), tag[u] = 0;
    }
    void build(int u, int l, int r) {
        if (l == r) {
            maxx[u] = 0, mpos[u] = l;
            return ;
        }
        int mid = l + r >> 1;
        build(ls, l, mid), build(rs, mid + 1, r);
        pushup(u);
    }
    void update(int u, int l, int r, int ql, int qr, int dlt) {
        if (ql <= l && r <= qr) {
            pushtag(u, dlt);
            return ;
        }
        pushdown(u);
        int mid = l + r >> 1;
        if (ql <= mid) update(ls, l, mid, ql, qr, dlt);
        if (qr > mid) update(rs, mid + 1, r, ql, qr, dlt);
        pushup(u);
    }
} smt;
int main() {
    scanf("%d", &n);
    tmp[++len] = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &L[i], &R[i]);
        tmp[++len] = L[i], tmp[++len] = R[i];
        tmp[++len] = L[i] + 1, tmp[++len] = R[i] + 1, tmp[++len] = R[i] - 1;
    }
    sort(tmp + 1, tmp + len + 1), len = unique(tmp + 1, tmp + len + 1) - tmp - 1;
    while (tmp[len] > 1000000000) len--;
    smt.build(1, 1, len);
    for (int i = 1; i <= n; i++) {
        L[i] = lower_bound(tmp + 1, tmp + len + 1, L[i]) - tmp;
        R[i] = lower_bound(tmp + 1, tmp + len + 1, R[i]) - tmp;
        add[L[i]].push_back(R[i]);
        sub[R[i]].push_back(R[i]);
        if (L[i] + 2 <= R[i]) smt.update(1, 1, len, L[i] + 1, R[i] - 1, 1);
    }
    int mxans = -1, mxpos1 = 0, mxpos2 = 0;
    for (int i = 1; i <= len; i++) {
        for (auto R: add[i]) {
            if (i + 2 <= R)
                smt.update(1, 1, len, i + 1, R - 1, -1);
        }
        for (auto R: add[i - 1]) {
            smt.update(1, 1, len, R + 1, len, 1);
        }
        for (auto R: sub[i]) {
            smt.update(1, 1, len, R + 1, len, -1);
        }
        smt.update(1, 1, len, i, i, -inf);
        int mx = smt.maxx[1], mp = smt.mpos[1];
        if (mx > mxans)
            mxans = mx, mxpos1 = tmp[i], mxpos2 = tmp[mp];
    }
    printf("%d %d\n", mxpos1, mxpos2);
    return 0;
}

扫描线的方法在楼下有，更加详细，便不再叙述。