CF 1523G Try Booking

题目描述

https://codeforces.com/problemset/problem/1523/G

简要题意：给定 $m$ 个区间 $[l_i,r_i]$ 和一个整数 $n$，保证 $1\le l_i\le r_i\le n$，求对于 $x\in [1,n]$，如果只保留 $x\le r_i-l_i+1$ 的区间，按照区间的编号依次放置区间，放置区间 $[l_i,r_i]$ 的条件是 $[l_i,r_i]$ 与之前放置的任何区间无交点，求被放置的区间的总长度

$n\le 5\times 10^4,m\le 10^5$

Solution

注意到对于某一个 $x$，被放置的区间总数是小于等于 $\lfloor\frac{n}{x}\rfloor$，所以我们可以考虑求出所有放置区间，我们考虑倒叙处理 $x$，那么我们现在只有插入区间，那么我们需要支持的操作是插入一个区间 $[l,r]$，查询被区间 $[l,r]$ 完全包含的编号最小的区间，具体实现我们发现插入是一个类似后缀加的操作，所以我们使用树状数组套动态开点线段树，内部的线段树只需要维护单点修改，区间查询最小值

时间复杂度 $O(n\log^3 n)$，但常数非常小

#include <iostream>
#include <vector>
#define maxn 50010
#define maxm 100010
#define INF 1000000000
#define lowbit(i) ((i) & (-i))
using namespace std;

int n, m, l[maxm], r[maxm];
vector<int> A[maxn];

#define lc T[i].ch[0]
#define rc T[i].ch[1]
struct Seg {
    int v, ch[2];
} T[maxn * 200]; int rt[maxn], top;
inline int newnode(int v) {
    int i = ++top;
    T[i].v = v;
    return i; 
}

void update(int &i, int l, int r, int k, int v) {
    if (!i) i = newnode(v); T[i].v = min(T[i].v, v);
    if (l == r) return ; int m = l + r >> 1;
    if (k <= m) update(lc, l, m, k, v);
    else update(rc, m + 1, r, k, v); 
}

int query(int i, int l, int r, int L, int R) {
    if (!i || l > R || r < L) return INF;
    if (L <= l && r <= R) return T[i].v;
    int m = l + r >> 1;
    return min(query(lc, l, m, L, R), query(rc, m + 1, r, L, R)); 
}

void add(int i, int k, int v) { while (i <= n) update(rt[i], 1, n, k, v), i += lowbit(i); }
int get_sum(int l, int r) {
    int s = INF, i = r;
    while (i) s = min(s, query(rt[i], 1, n, l, r)), i -= lowbit(i);
    return s; 
}

int solve(int l, int r) {
    if (l > r) return 0; 
    int v = get_sum(l, r); if (v == INF) return 0;
    return ::r[v] - ::l[v] + 1 + solve(l, ::l[v] - 1) + solve(::r[v] + 1, r); 
}

int ans[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> l[i] >> r[i];
        A[r[i] - l[i] + 1].push_back(i);
    } T[0].v = INF;
    for (int i = n; i; --i) {
        for (auto t : A[i]) add(r[t], l[t], t);
        ans[i] = solve(1, n); 
    }
    for (int i = 1; i <= n; ++i) cout << ans[i] << "\n";
    return 0;
}