DDOSvoid's Blog

CF 1175E Minimal Segment Cover

发表于 分类于
本文字数： 961 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/problemset/problem/1175/E

Solution

我们考虑一个贪心的暴力即每次找到左端点小于当前点且右端点最远的线段，然后跳到对应的右端点，注意到这个就是倍增的过程

所以我们预处理后倍增即可

时间复杂度 $O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <vector>
#include <algorithm>
#define maxn 200010
#define maxm 500010
#define ll long long
using namespace std;

const int N = 500000; 

int n, m, p[maxm];

int nxt[maxm][21];

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; 
    for (int i = 1; i <= n; ++i) {
        int x, y; cin >> x >> y;
        p[x] = max(p[x], y); 
    }
    for (int i = 1; i <= N; ++i) p[i] = max(p[i], p[i - 1]);
    for (int i = 1; i <= N; ++i) nxt[i][0] = p[i];
    for (int j = 1; j <= 20; ++j)
        for (int i = 1; i <= N; ++i) nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
    while (m--) { 
        int x, y, p, ans = 0; cin >> x >> y; p = x;
        for (int i = 1; ~i; --i)
            if (nxt[p][i] && nxt[p][i] < y) p = nxt[p][i], ans += 1 << i;
        cout << (nxt[p][0] >= y ? ans + 1 : -1) << "\n"; 
    } 
    return 0;
}