[C++] ํํ ๋ถํ , ๋ชจ์ค ์๊ณ ๋ฆฌ์ฆ
ยท
๐ Computer Science/โ Algorithm
ํํ ๋ถํ , ๋ชจ์ค ์๊ณ ๋ฆฌ์ฆ ํํ ๋ถํ (SQRT Decomposition)์ ๋ฐ์ดํฐ๊ฐ N๊ฐ์ด๋ฉด √N๊ฐ๋งํผ ๋๋ ์ ๊ด๋ฆฌํ๋ ๋ฐฉ๋ฒ์ด๋ค. ๊ฐ ๊ทธ๋ฃน์ ๋ํฏ๊ฐ์ ๊ฐ์ง๊ณ ์๋ค. ๋ง์ฝ ์ฃผ์ด์ง๋ ์ฟผ๋ฆฌ๊ฐ ๊ตฌ๊ฐ์ ๋ง์
์ด๋ผ๋ฉด ๊ทธ๋ฃน์ ํฉ์ด ๋ํฏ๊ฐ์ด ๋๋ค. ๋ชจ์ค ์๊ณ ๋ฆฌ์ฆ์ ์ด๋ค ๊ตฌ๊ฐ [s, e]์ ์ํ๋ ์์๋ค์ ์ด์ฉํ์ฌ ์ด๋ค ๊ฐ์ ๊ณ์ฐํ๋ ์ฟผ๋ฆฌ๋ฅผ ์ฒ๋ฆฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ์
๋ฐ์ดํธ๊ฐ ์์ด ์ฟผ๋ฆฌ์ ์์๋ฅผ ๋ณ๊ฒฝํด๋ ๋ฌด๋ฐฉํ๋ค. ๊ทธ๋์ ์ฟผ๋ฆฌ ์์๋ฅผ ์ฌ๋ฐฐ์นํ์ฌ ํจ์จ์ ์ผ๋ก ์ํํ๋ค. ๋ฐฐ์ด์ k(√N)๊ฐ๋ก ์ด๋ฃจ์ด์ง ๊ทธ๋ฃน์ผ๋ก ๋๋ ์ฃผ๊ณ , ์ฟผ๋ฆฌ๋ฅผ ์คํํ ๋ ๋ ์กฐ๊ฑด ์ค ํ๋๋ฅผ ๋ง์กฑํ๋ ๊ฒฝ์ฐ ๋จผ์ ์ฒ๋ฆฌํ๋ค. [s1/k] < [s2/k] [s1/k] = [s2/k] and e1 < e2 ๋ฌธ์ https://www.acmicpc.net/problem/1..