問題 問題概要 [l, r]の区間を考えた時に, al, .. , ar の最大値と bl, .. , br の最小値が一致する区間の総数を求める. 解法 区間の左端を固定して, 右端を伸ばしていくと, aの最大値は単調増加, bの最小値は単調減少していくので, 区間を伸ばしていくとど…

問題 問題概要 木のグラフが与えられる。その木に対して、辺を１つ加えでできる、閉路の長さを答える。 解法 まず、LCAを求める。LCAについては、蟻本。多くのクエリが与えられるので、いちいち親をたどっていては、間に合わない。そこで、頂点vから、2k回上…

問題 問題概要 省略。 解法 まず、簡単にわかることは、D=1の場合において、上側の何番目から始めたら、下側の何番目につくかというのを求める。それを利用して、それぞれの列から開始して、d回後にどこにいるかを求めればいい。しかし、このようにやってし…

問題 問題概要 省略 解法 参考サイト imulan.hatenablog.jp 上のサイトを見たらだいぶわかった。 ダブリングと２分探索を使うらしい。蟻本の最後の方にもかいてあった。 int now = a; for (int i = 19; i >= 0; --i){ if(nx[i][now] < b){ now = nx[i][now];…