Codeforces 1175E（倍增）
要点[*]与cf 1168C相似的一点都是看某点x最远能拓展到哪里
[*]看数据想要在logn内查询，考虑倍增步数
const int maxn = 2e5 + 5, X = 5e5 + 5, LOG = 25;
int n, m;
int l, r;
int dp;//点i走pow(2, j)步最远到达的点
int main() {
read(n), read(m);
rep(i, 1, n) {
read(l), read(r);
dp = max(dp, r);//会被更新
}
rep(i, 1, X - 5) {
dp = max(dp, dp);
}
rep(i, 1, 20)
rep(j, 0, X - 5)//倍增
dp = dp];
rep(i, 1, m) {
read(l), read(r);
int ans = 0;
per(j, 20, 0)
if (dp < r) {//要写小于；走2^20步最远能到r：2^1就到了，后面19次都是空步
ans += 1 << j;
l = dp;
}
if (ans <= n)writeln(ans + 1);//最后一步
elsewriteln(-1);
}
return 0;
}
文档来源：51CTO技术博客https://blog.51cto.com/u_14696602/3107442
页:
[1]