关于 set 处理一类区间问题

· · 算法·理论

P2161 题解区没有一篇本质讲清楚为什么用set<>::find的，连std::lower_bound都没有。所以我发一篇题解讲一下。

首先我们考察源代码定义的定义与实现，这里用std::lower_bound和std::upper_bound来类比std::set<>，二者实现逻辑相同，但是序列上的源代码更可读。

... __lower_bound(...) {
    ...
    while (__len > 0) {
        _DistanceType __half = __len >> 1;
        _ForwardIterator __middle = __first;
        std::advance(__middle, __half);
        if (__comp(__middle, __val)) { // 手动高亮代码
            __first = __middle;
            ++__first;
            __len = __len - __half - 1;
        } else
            __len = __half;
    }
    return __first;
}
... __upper_bound(...) {
  ...
    while (__len > 0) {
        _DistanceType __half = __len >> 1;
        _ForwardIterator __middle = __first;
        std::advance(__middle, __half);
        if (__comp(__val, __middle)) // 手动高亮代码
            __len = __half;
        else {
            __first = __middle;
            ++__first;
            __len = __len - __half - 1;
        }
    }
    return __first;
}

可以看到，std::lower_bound的cmp是mid在val左边，std::upper_bound则相反。

这一道题目我们要求交集（很多区间不重合的题目都可以这么做）。我们要查看的是第一个与目标区间重合的区间和最后一个与目标区间重合的区间，后者转换一下就是第一个不与目标区间重合的区间的前一个区间。

由于区间不重合，以及上面对于std::lower_bound的讨论，求左端点的比较函数我们可以这么写。

bool operator <(const node &a, const node &b) {
    return a.r < b.l;
}
iter L = s.lower_bound(node(l, 0));
// 找到第一个 r 比目标区间 l 大(包括等于)的区间

同时，我们发现，根据std::upper_bound的性质，比较函数依旧是可用的！这样我们可以把他们塞进一个std::set<>中。

bool operator <(const node &a, const node &b) {
    return a.r < b.l;
}
iter R = s.upper_bound(node(0, r)); 
// 找到第一个 l 比目标区间 r 大的区间

那么接下来就显而易见了。

#include <bits/stdc++.h>

#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
using lnt = long long;

struct mystream {
    int x; char s[100];
    operator int() { scanf("%d", &x); return x; }
    char to_char() { scanf("%s", s); return *s; }
} _rp_read;

#define input() _rp_read

/************************    head    ******************************/

const int max_n = 1e3;

struct node { 
    int l, r; 
    node() = default;
    node(int _l, int _r) : l(_l), r(_r) {}
};

bool operator <(const node &a, const node &b) {
    return a.r < b.l;
}

std::set<node> s;

#define iter std::set<node>::iterator

int insert() {
    int l = input(), r = input();
    iter L = s.lower_bound(node(l, 0)); // mid, val
    iter R = s.upper_bound(node(0, r)); // val, mid
    int res = std::distance(L, R);
    s.erase(L, R), s.insert(node(l, r));
    return res;
}

void solve() {
    int n = input();
    for (int i = 0; i < n; ++i) {
        int opt = input().to_char();
        if (opt == 'A') printf("%d\n", insert());
        else printf("%d\n", int(s.size()));
    }
}

int main() {
    solve();

    return 0;
}

/*

*/

同样的，如果要找最后一个不相交集合之类，直接使用std::prev()和std::next()对上文进行修改即可。

还有就是找完全包含集合，这种需要在查找相交集合后进行特判。如果完全包含就 ok，否则进行std::prev()和std::next()，~不过可以用下文的方法就是了~。

对于另一种题目如 P1840 Color the Axis，这种找断点的题目，可以只用std::lower_bound维护，可以这么写：

node(int _l, int _r = -1, int _v = -1) : l(_l), r(_r) v(_v) { }
bool operator <(const node &a, const node &b) {
    return a.l < b.l;
}
iter it = s.lower_bound(node(pos));

~不过这就是珂朵莉树吧~。