선분 트 리 템 플 릿

발췌
4.567917.maxn 은 제목 이 주 는 최대 구간 이 고 노드 수 는 4 배 를 열 어야 한다.정확히 말 하면 노드 수 는 maxn 의 최소 2x 의 두 배 보다 크다

lson 과 rson 은 결점 을 나타 내 는 왼쪽 아들 과 오른쪽 아들 을 구분 하 는데 매개 변 수 를 전달 할 때마다 이 몇 개의 변 수 를 고정 시 키 기 때문에 비교적 편리 하 게 표시 할 수 있다

4.567917.예전 의 표기 법 은 두 개의 배열 을 따로 열 어 각 노드 가 표시 하 는 구간 을 기록 하 는 것 이 었 다.사실 이 구간 은 저장 할 필요 가 없고 계산 하면 서 전달 하면 된다.함 수 를 쓸 때 두 개의 매개 변 수 를 더 써 야 하 며 lson 과 rson 의 미리 정 의 를 결합 하면 편리 하 다PushUP(int rt)는 현재 노드 의 정 보 를 부모 노드 로 업데이트 하 는 것 입 니 다PushDown(int rt)은 현재 결점 의 정 보 를 아들 결점 에 업데이트 하 는 것 이다

rt 는 현재 하위 나무의 뿌리(root),즉 현재 있 는 결점 을 나타 낸다

#define lson l , m , rt << 1

#define rson m + 1 , r , rt << 1 | 1

 

const int maxn = 55555;

int lsum[maxn<<2] , rsum[maxn<<2] , msum[maxn<<2];

int cover[maxn<<2];

 

void PushDown(int rt,int m) {

    if (cover[rt] != -1) {

        cover[rt<<1] = cover[rt<<1|1] = cover[rt];

        msum[rt<<1] = lsum[rt<<1] = rsum[rt<<1] = cover[rt] ? 0 : m - (m >> 1);

        msum[rt<<1|1] = lsum[rt<<1|1] = rsum[rt<<1|1] = cover[rt] ? 0 : (m >> 1);

        cover[rt] = -1;

    }

}

void PushUp(int rt,int m) {

    lsum[rt] = lsum[rt<<1];

    rsum[rt] = rsum[rt<<1|1];

    if (lsum[rt] == m - (m >> 1)) lsum[rt] += lsum[rt<<1|1];

    if (rsum[rt] == (m >> 1)) rsum[rt] += rsum[rt<<1];

    msum[rt] = max(lsum[rt<<1|1] + rsum[rt<<1] , max(msum[rt<<1] , msum[rt<<1|1]));

}

void build(int l,int r,int rt) {

    msum[rt] = lsum[rt] = rsum[rt] = r - l + 1;

    cover[rt] = -1;

    if (l == r) return ;

    int m = (l + r) >> 1;

    build(lson);

    build(rson);

}

void update(int L,int R,int c,int l,int r,int rt) {

    if (L <= l && r <= R) {

        msum[rt] = lsum[rt] = rsum[rt] = c ? 0 : r - l + 1;

        cover[rt] = c;

        return ;

    }

    PushDown(rt , r - l + 1);

    int m = (l + r) >> 1;

    if (L <= m) update(L , R , c , lson);

    if (m < R) update(L , R , c , rson);

    PushUp(rt , r - l + 1);

}

int query(int w,int l,int r,int rt) {

    if (l == r) return l;

    PushDown(rt , r - l + 1);

    int m = (l + r) >> 1;

    if (msum[rt<<1] >= w) return query(w , lson);

    else if (rsum[rt<<1] + lsum[rt<<1|1] >= w) return m - rsum[rt<<1] + 1;

    return query(w , rson);

}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

HDU - 1166 - 적병 포진 (나무형 수조 또는 선분 수)

C 국 의 앙 숙 A 국 은 그동안 군사훈련 을 하고 있 었 기 때문에 C 국 간첩 두목 인 데 릭 과 그의 수하 인 티 디 는 또 바 빠 지기 시작 했다.A 국 가 는 해안선 을 따라 직선 으로 N 개 공병 캠프 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

선분 트 리 템 플 릿

좋은 웹페이지 즐겨찾기