[COCI2021-2022#2] Osumnjičeni 题解

钰瑾_恋涵 · 2022-08-29 13:11:24 · 题解

题目链接

题目大意：

给你 n 个人的身高范围，一次操作可以将连续的一段人排除，但要求这些人身高没有交集，有 Q 个询问，每个询问给定 l，r 问最多需要几次操作可以将 l - r 之间的人全部排除。

分析：

考虑贪心，对于一次操作，设其左端点为 l，那么我们一定会让右端点尽可能的大，所以 r 选择身高无交集的最大的 r。

对于每一个 l 们都求出它的 r，这一操作可以用数据结构去维护，我这里用的是单调队列加线段树，复杂度为 O(n\log n)。

另外身高很高啊，还要离散化。

然后整道题目就很清晰了，就相当于最少线段覆盖，这就是倍增优化 DP 的板子题了，点可以转成线段。

code

#include <bits/stdc++.h>

using namespace std;

typedef long long i64;

i64 read() {
    i64 x(0), f(0); char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return f ? -x : x;
}
int __stk[128], __len;
void put(i64 x) {
    if (x < 0) putchar('-'), x = -x;
    do { __stk[++__len] = x % 10, x /= 10; } while (x);
    while (__len) putchar(__stk[__len--] ^ 48);
}
const int N = 401010;
int n, q, cnt;
int L[N], R[N], c[N];
int f[N][22];

struct Tree {
    #define mid ((l + r) >> 1)
    #define ls (x << 1)
    #define rs (x << 1 | 1)
    int t[N << 4], tag[N << 4];
    void pushdown(int x) {
        if (tag[x]) {
            t[ls] += tag[x], tag[ls] += tag[x];
            t[rs] += tag[x], tag[rs] += tag[x];
            tag[x] = 0;
        }
    }
    void modify(int x, int l, int r, int L, int R, int v) {
        if (l >= L && r <= R) return t[x] += v, tag[x] += v, void();
        pushdown(x);
        if (mid >= L) modify(ls, l, mid, L, R, v);
        if (mid < R) modify(rs, mid + 1, r, L, R, v);
        t[x] = max(t[ls], t[rs]);
    }
    int ask(int x, int l, int r, int L, int R) {
        if (l >= L && r <= R) return t[x];
        pushdown(x); int ans = 0;
        if (mid >= L) ans = max(ans, ask(ls, l, mid, L, R));
        if (mid < R) ans = max(ans, ask(rs, mid + 1, r, L, R));
        return ans;
    }
}T;

signed main() {
//  freopen("osumnjiceni.in","r",stdin);
//  freopen("osumnjiceni.out","w",stdout);
    n = read();
    for (int i = 1; i <= n; ++i) {
        c[++cnt] = L[i] = read();
        c[++cnt] = R[i] = read(); 
    }
    sort(c + 1, c + cnt + 1), cnt = unique(c + 1, c + cnt + 1) - c - 1;
    for (int i = 1; i <= n; ++i) {
        L[i] = lower_bound(c + 1, c + cnt + 1, L[i]) - c;
        R[i] = lower_bound(c + 1, c + cnt + 1, R[i]) - c;
    }
    int p = 1;
    for (int i = 1; i <= n; ++i) {
        while (T.ask(1, 1, cnt, L[i], R[i])) {
            f[p - 1][0] = i - 1;
            T.modify(1, 1, cnt, L[p], R[p], -1), ++p;
        }
        T.modify(1, 1, cnt, L[i], R[i], 1);
    }
    while (p <= n + 1) f[p - 1][0] = n, ++p;
    for (int j = 1; j <= 20; ++j) 
        for (int i = 0; i <= n; ++i) 
            f[i][j] = f[f[i][j - 1]][j - 1];
    q = read();
    while (q--) {
        int l = read() - 1, r = read(), ans = 1;
        for (int i = 20; ~i; --i) if(f[l][i] < r) ans += 1 << i, l = f[l][i];
        put(ans), putchar('\n');
    }
    return 0;
}