18-2-6~2-12 주간 알고리즘 총결산(수론,st표,수상수조)

7,9
수론
꾸르륵꾸르륵
11
st표, 트리 배열
내용이 좀 많아요.천천히 해.
첫째, RMQ, 검색 구간이 가장 크다(작다).
전체 길이 n의 구간에 대해 한 번에 전체 검색 시간이 n이고 최악의 경우 n^2의 경우 검색을 하는데 예가 많으면 시간의 복잡도를 초과할 수밖에 없다.그래서 시계를 칩니다.처음에 n*n의 이중순환 타이머를 생각했지만 안 돼요. rmq는 사실 그것에 대한 최적화예요. dp[i][j]는 i부터 2^j의 길이를 나타냅니다.한편, dp[i][j]=max(dp[i][j-1], dp[i+2^(j-1)][j-1]) 즉 이 길이 2^j의 최대치는 왼쪽 2^(j-1)와 오른쪽 2^(j-1)의 최대치로 확정된다.즉 두 번째 단락의 데이터 복잡도를 n에서logn으로 낮추었다.
그럼 x 하나 주세요. y 어떻게 찾죠?
 k=log(y-x)/log(2)
ans=max(mx[x-1][k], mx[y-1-(1<=y-1-2^k+1, 그래서 반드시 찾는 최대치는 구간 최대입니다.
코드

	for(int j=1;j<20;j++){
		for(int i=0;i+(1<