Codeforces 1175E（倍增）

太阳不下山

要点

• 与cf 1168C相似的一点都是看某点x最远能拓展到哪里
  
• 看数据想要在logn内查询，考虑倍增步数
  

const int maxn = 2e5 + 5, X = 5e5 + 5, LOG = 25;
int n, m;
int l, r;
int dp[X][LOG];//点i走pow(2, j)步最远到达的点
int main() {
read(n), read(m);
rep(i, 1, n) {
read(l), read(r);
dp[l][0] = max(dp[l][0], r);//会被更新
}
rep(i, 1, X - 5) {
dp[i][0] = max(dp[i][0], dp[i - 1][0]);
}
rep(i, 1, 20)
rep(j, 0, X - 5)//倍增
dp[j][i] = dp[dp[j][i - 1]][i - 1];
rep(i, 1, m) {
read(l), read(r);
int ans = 0;
per(j, 20, 0)
if (dp[l][j] < r) {//要写小于；走2^20步最远能到r：2^1就到了，后面19次都是空步
ans += 1 << j;
l = dp[l][j];
}
if (ans <= n)writeln(ans + 1);//最后一步
elsewriteln(-1);
}
return 0;
}