E - Just a Hook HDU - 1698 - 선분 트 리 구간 업데이트 + lazy 태그

Think: 1 지식 포인트: 선분 트 리 구간 업데이트 + lazy 태그 2 문제: n 개의 초기 화 점 권 이 1 인 점 을 바탕 으로 구간 업 데 이 트 를 진행 하여 최종 상태 n 개의 점 권 과 3 반성: 현재 문제 lazy 태그 할당 업데이트
제목 링크
다음은 Wrong Answer 코드 - lazy 태그 업데이트 오류 입 니 다.

#include 
#include 
#include 

using namespace std;

const int N = 101400;

struct Node{
    int sum;
}node[N<<2];

int lazy[N<<2];

void Build(int l, int r, int rt);
void Updata(int rt);
void down(int rt, int l, int r);
void up_v(int L, int R, int v, int l, int r, int rt);

int main(){
    int T, k = 1, n, m, L, R, v;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        Build(1, n, 1);
        scanf("%d", &m);
        while(m--){
            scanf("%d %d %d", &L, &R, &v);
            up_v(L, R, v, 1, n, 1);
        }
        printf("Case %d: The total value of the hook is %d.
", k++, node[1].sum);
    }
    return 0;
}
void Build(int l, int r, int rt){
    lazy[rt] = 0;
    if(l == r){
        node[rt].sum = 1;
        return;
    }
    int mid = (l+r)/2;
    Build(l, mid, rt<<1);
    Build(mid+1, r, rt<<1|1);
    Updata(rt);
}
void Updata(int rt){
    node[rt].sum = node[rt<<1].sum + node[rt<<1|1].sum;
}
void up_v(int L, int R, int v, int l, int r, int rt){
    if(L <= l && r <= R){
        node[rt].sum = v*(r-l+1);
        lazy[rt] = v;
        return;
    }
    down(rt, l, r);
    int mid = (l+r)/2;
    if(L <= mid)
        up_v(L, R, v, l, mid, rt<<1);
    if(R > mid)
        up_v(L, R, v, mid+1, r, rt<<1|1);
    Updata(rt);
}
void down(int rt, int l, int r){
    if(lazy[rt]){
        lazy[rt<<1] += lazy[rt];
        lazy[rt<<1|1] += lazy[rt];
        int mid = (l+r)/2;
        node[rt<<1].sum = lazy[rt]*(mid-l+1);
        node[rt<<1|1].sum = lazy[rt]*(r-mid);
        lazy[rt] = 0;
    }
}

다음은 Accepted 코드 입 니 다.

#include 
#include 
#include 

using namespace std;

const int N = 101400;

struct Node{
    int sum;
}node[N<<2];

int lazy[N<<2];

void Build(int l, int r, int rt);
void Updata(int rt);
void down(int rt, int l, int r);
void up_v(int L, int R, int v, int l, int r, int rt);

int main(){
    int T, k = 1, n, m, L, R, v;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        Build(1, n, 1);
        scanf("%d", &m);
        while(m--){
            scanf("%d %d %d", &L, &R, &v);
            up_v(L, R, v, 1, n, 1);
        }
        printf("Case %d: The total value of the hook is %d.
", k++, node[1].sum);
    }
    return 0;
}
void Build(int l, int r, int rt){
    lazy[rt] = 0;
    if(l == r){
        node[rt].sum = 1;
        return;
    }
    int mid = (l+r)/2;
    Build(l, mid, rt<<1);
    Build(mid+1, r, rt<<1|1);
    Updata(rt);
}
void Updata(int rt){
    node[rt].sum = node[rt<<1].sum + node[rt<<1|1].sum;
}
void up_v(int L, int R, int v, int l, int r, int rt){
    if(L <= l && r <= R){
        node[rt].sum = v*(r-l+1);
        lazy[rt] = v;
        return;
    }
    down(rt, l, r);
    int mid = (l+r)/2;
    if(L <= mid)
        up_v(L, R, v, l, mid, rt<<1);
    if(R > mid)
        up_v(L, R, v, mid+1, r, rt<<1|1);
    Updata(rt);
}
void down(int rt, int l, int r){
    if(lazy[rt]){
        lazy[rt<<1] = lazy[rt];/*lazy      */
        lazy[rt<<1|1] = lazy[rt];/*lazy      */
        int mid = (l+r)/2;
        node[rt<<1].sum = lazy[rt]*(mid-l+1);
        node[rt<<1|1].sum = lazy[rt]*(r-mid);
        lazy[rt] = 0;
    }
}

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

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

D - Mayor 's posters - 선분 수 구간 덮어 쓰기 + 이산 화

Think: 1 지식 포인트: 선분 수 구간 커버 + 이산 화 2 주제 분석: 경선 자 는 벽 에 홍보 포스터 를 붙 여야 한다. 포스터 의 높이 가 같 고 너비 가 같 지 않 으 며 시간축 에 따라 커버 가 나타난...

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

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

E - Just a Hook HDU - 1698 - 선분 트 리 구간 업데이트 + lazy 태그

좋은 웹페이지 즐겨찾기