競技プログラミングにハマるプログラマのスレ 156

[885 仕様書無しさん 2024/02/11(日) 02:34:13.28]

k回操作を行ったあとの頂点数は絶対に連続した数になるのでk±1回操作した頂点と異なるとすると精々k+1個なので頂点数はsigma(1->logn)k+1=O(logn^2)
各頂点に精々2回しかアクセスしない
mapへの追加も一度だけ
よってO(logn^3)くらいかと思った