Sparse Table 설명
dp[i][j]: i를 기점으로 하고 길이가 2^j인 구간 최대치를 나타냅니다.
그러면 우리는 상태 이동 방정식을 쉽게 얻을 수 있다. dp[i][j]=max(dp[i][j-1], dp[i+(1<(j-1)][j-1])])는 상태 이동 방정식을 설명한다. 여기서 상태 이동 방정식을 설명한다. i로 시작하는 길이가 2^j의 구간 최대치이고 i로 시작하는 길이가 2^(j-1)의 최대치와 i+(1<(j-1))로 시작하는 길이가 2^(j-1)의 최대치로 두 가지를 크게 하면 된다.상태 이동 방정식을 통해 알 수 있듯이 큰 상태 j는 작은 상태(j-1)에 의존하기 때문에 우리는 작은 상태에서 큰 단위로 j를 열거하면 된다.j의 하계는 1(0일 때 하는 dp 초기화)이라는 것을 쉽게 알 수 있는데 관건은 j의 상계가 어떻게 확정되는가?n개의 원소가 있는 서열에 대해 j의 상계는 2를 밑으로 하는 n의 대수보다 작다(이곳에서 정돈). 만약에 j값이 다른 것보다 작다면 dp[i][j]의 정의는 이미 의미가 없다. 이 점은 이해하기 쉽다.
쿼리 구간[L, R]
ST표에서 [L, R]의 최고치를 조회하려면 우리는 먼저 2를 밑으로(R-L+1)의 대수 k를 계산한 다음에 dp[L][k]와 dp[R-(1<
#include
#include
#include
using namespace std;
const int N = 1e+5;
int st[N][20];
void init_st(int size)
{
for (int j = 1; 1 << j <= size; ++j)
for (int i = 0; i + (1 << j) - 1 < size; ++i)
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
int query(int L, int R)
{
int k = log(R - L + 1) / log(2.0);
return max(st[L][k], st[R - (1 << k) + 1][k]);
}
int main()
{
int n, q;
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d", &st[i][0]);
init_st(n);
scanf("%d", &q);
while (q--)
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d
", query(l, r));
}
return 0;
}
위의 분석에서 우리는 ST표가 동적 업데이트에 적합하지 않다는 것을 알 수 있다. 만약에 프로그램에서 섹션 업데이트나 단일 업데이트가 필요하다면 섹션 트리나 트리 모양의 그룹을 사용해야 한다.그러나 정적 데이터에 대해 말하자면 ST표는 의심할 여지없이 가장 좋은 선택이고 인코딩이 간단하며 조회 효율도 매우 높다.
여기에 여러분이 연습할 수 있는 제목이 첨부되어 있습니다.
http://codeforces.com/contest/488/problem/D
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
