CF1523G Try Booking 题解

· · 题解

不知道更好还是更坏的阅读体验

复盘 ntf 讲的题，写篇题解来祸害社会

Description

给定 m 个请求和空闲的 n 天，每个请求包含两个整数 l 和 r 表示第 i 个请求想占用 l 到 r 这几天。

然后你自己有一个限制 x ，当目前这个请求想占用的天数不小于 x 时，你才会考虑是否安排，并且该请求生效的条件是在 l 到 r 中的所有天目前均无人占用。

问 x \in [1,\ n] 的所有限制下能安排的天数。

n \leq 5 \cdot 10 ^ 4,\ m \leq 10 ^ 5

Solution

因为每一天只能至多有一个人能够占用，所以我们可以考虑分治，因为每次最少减少 x 天，所以分支这一段的时间是：\sum_{i = 1} ^ n {\large \frac{n}{i}} = n\ln n 。

因为要先来后到，所以我们还要考虑维护被包含在区间内的请求的最小序号。虽然显然线段树，但是我们似乎并不能直接压缩状态，我们想想在什么情况下能够表达出来。

我们想象一个二维平面，右上角是 (0, 0) ，然后假设我们要的区间是 (l, r) ：

图中也就只有紫色的点是满足要求的，也就是说当且仅当满足 L_i \geq l,\ R_i \leq r 时才满足。

所以我们可以考虑分开维护 l 和 r ，采用树套树维护，每次查询一次，然后递归到 [limL, L - 1] 和 [R + 1, limR] 继续查询。

总时间复杂度 O(n\ln n\log^ 2 n + m \log ^ 2 n) 。

Code

/*

*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 6e6 + 10, INF = 2e9;
int n, m, l[N], r[N], pt[N], ans[N];
int rt[N], cnt, tr[N], ls[N], rs[N];
vector<int> lth[N];
const int Mxdt = 100000;
inline char gc() {
    static char buf[Mxdt], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, Mxdt, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
    char ch = getchar();
    int s = 0, w = 1;
    while (!isdigit(ch)) {if (ch == '-') w = -1; ch = getchar();}
    while (isdigit(ch)) {s = (s << 3) + (s << 1) + (ch ^ 48); ch = getchar();}
    return s * w;
}
inline void pushup(int now) {
    tr[now] = min(tr[ls[now]], tr[rs[now]]);
}
inline void modify(int &now, int lt, int rt, int k, int it) {
    if (!now) tr[now = ++cnt] = INF;
    if (lt == rt) {
        tr[now] = min(tr[now], it); return ;
    }
    int mid = (lt + rt) >> 1;
    if (k <= mid) modify(ls[now], lt, mid, k, it);
    else modify(rs[now], mid + 1, rt, k, it);
    pushup(now);
}
inline int query(int now, int lt, int rt, int L, int R) {
    if (!now) return INF;
    if (L <= lt && rt <= R) return tr[now];
    int mid = (lt + rt) >> 1, res = INF, ret = INF;
    if (L <= mid) res = query(ls[now], lt, mid, L, R);
    if (R > mid) ret = query(rs[now], mid + 1, rt, L, R);
    return min(res, ret);
}
inline int lowbit(int x) {return x & (-x);}
inline void modify(int l, int r, int it) {
    for (int i = r; i <= n; i += lowbit(i)) modify(rt[i], 1, n, l, it);
}
inline int query(int l, int r) {
    int res = INF;
    for (int i = r; i; i -= lowbit(i)) res = min(res, query(rt[i], 1, n, l, r));
    return res;
}
inline int calc(int lt, int rt, int it) {
    if (rt - lt + 1 < it) return 0;
    int res = query(lt, rt);
    if (res > m) return 0;
    return calc(lt, l[res] - 1, it) + pt[res] + calc(r[res] + 1, rt, it);
}
int main() {
    n = read(); m = read(); tr[0] = INF;
    for (int i = 1; i <= m; ++i) {
        l[i] = read(); r[i] = read();
        pt[i] = r[i] - l[i] + 1;
        lth[pt[i]].push_back(i);
    }
    for (int i = n; i >= 1; --i) {
        for (int j : lth[i]) modify(l[j], r[j], j);
        ans[i] = calc(1, n, i);
    }
    for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
    return 0;