题目链接:https://codeforces.com/contest/1175/problem/E
给你n条线段,m次询问。每次询问至少需要n条线段中的多少条线段能把本次询问中的线段覆盖?n条线段必须相交才算可以连起来(也就是$r_1>l_2$)。
考虑倍增预处理$n$条线段:$f(l,j)$表示从$l$出发连$2^j$条线段最远可以到达的点是多少,于是得到更新方式:
$$
f(l,j)=f(f(l,j-1),j-1)
$$
查询的时候$j$单调递减,每次查询$l$出发是否可以经过$j$次到达$r$,如果不可以那么更新$l$为$l$走$2^j$最远到达的点,下次从这个点出发查看是否可以到达$r$.
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 37 38 39 40 41 42 43 44 45 46 47 48 49
|
using namespace std; using LL = long long; using PLL = pair<LL, LL>;
const int maxn = 500500; int n, m; int f[maxn][24];
signed () { int l, r; while (cin >> n >> m) { memset(f, 0, sizeof f); int hi = 0; for (int i = 1; i <= n; i++) { cin >> l >> r; l++; r++; hi = max(hi, r); f[l][0] = max(f[l][0], r); } for (int i = 1; i <= hi; i++) { f[i][0] = max(f[i][0], max(i, f[i - 1][0])); } for (int j = 1; j < 24; j++) { for (int l = 1; l <= hi; l++) { f[l][j] = f[f[l][j - 1]][j - 1]; } } while (m--) { cin >> l >> r; l++; r++; if (f[l][23] < r) { cout << -1 << endl; continue; } int ret = 0; for (int i = 23; i >= 0; i--) { if (f[l][i] < r) { l = f[l][i]; ret += (1 << i); } } cout << ret + 1 << endl; } } return 0; }
|
近期评论