라인 트리 구간 추출 max 구간 조회

1950 단어
요선 구간 도자기 구간 max와 문의 구간 및.
$[L, R]$를 mx에서 max로 가져오도록 설정합니다.
우리는 라인 트리에서 mx보다 작은 구간을 나누어 구간 수정으로 바꿀 수 있다.
구체적인 실현은 유지보수 구간의 최소값과 구간의 최대값을 우리가 한 구간으로 귀속시키는 것이다. 만약에 이 구간의 최소값이 mx보다 크면 이 구간을 상관하지 않아도 된다.
그리고 우리는 구간이 $[L, R]$에 포함되어 있다고 가정합니다. 만약 이 구간의 최대 값이 mx보다 작다면, 직접 수정하고, 그렇지 않으면 다시 그의 하위 구역으로 돌아가서 찾습니다.
void change(int l, int r, int o, int ql, int qr, int c)
{
    if (mn[o] >= c) return ;
    if (l >= ql and r <= qr) 
    {
        if (mx[o] <= c) {
            mx[o] = mn[o] = lzy[o] = c;
            tr[o] = (r - l + 1) * c;
            return ;
        }
    }
    spread(o, l, r);// 
    int mid = (l + r) >> 1;
    if (ql <= mid) change(l, mid, ls, ql, qr, c);
    if (qr > mid) change(mid + 1, r, rs, ql, qr, c);
    pushup(o);
}

 
다음으로 전송:https://www.cnblogs.com/BriMon/p/9864702.html

좋은 웹페이지 즐겨찾기