「Bzoj 2028」「SHOI2009」会场预约 (Splay / Set)

BZOJ 2028
luogu免权限地址
Set维护不相交区间，lower_bound求前后与当前区间最近的区间，检查是否重合，重合即删除，直到不重合为止。
注意set.lower_bound()如果找不到就会返回set.end()

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
struct data {
    int l, r;
    bool operator < (const data &b) const {
        if (l == b.l) return r < b.r;
        return l < b.l;
    }
};
set<data> s;
int n;
int getch() {
    char ch = getchar();
    while (ch != 'A' && ch != 'B') ch = getchar();
    return ch == 'A' ? 1 : 2;
}
void clean() {}
void solve() {
    clean();
    for (int i = 1; i <= n; i++) {
        int opt = getch();
        if (opt == 2) printf("%d\n", (int)s.size()); else {
            int ans = 0;
            int l, r;
            scanf("%d%d", &l, &r);
            data a = (data){l, r};
            while (true) {
                set<data>::iterator p = s.lower_bound(a);
                if (p->l <= r && p->r >= l) {
                    ans++;
                    s.erase(p);
                    continue;
                }
                p = s.lower_bound(a);
                if (p != s.begin()) {
                    p--;
                    if (p->l <= r && p->r >= l) {
                        ans++;
                        s.erase(p);
                        continue;
                    }
                }
                s.insert(a);
                printf("%d\n", ans);
                break;
            }
        }
    }
}
int main() {
    scanf("%d", &n), solve();
    return 0;
}