HihoCoder 1078 세그먼트 트리 구간 업데이트

6256 단어 tree)Hihocoder
전송문: HihoCoder 1078
문제풀이
그냥 레이지 마크예요.
code:
/*
adrui's submission
Language : C++
Result : Accepted
Love : ll
Favorite : Dragon Balls

Standing in the Hall of Fame
*/



#include
#include
#include
#include
using namespace std;

#define debug 0
#define mid ((l + r) >> 1)
#define ls rt << 1, l, mid
#define rs rt << 1|1, mid + 1, r
#define LL long long
#define MOD 12357
#define M(a, b) memset(a, b, sizeof(a))

const int maxn(1e5 + 7);
int n;

struct {
    int v;
    int lazy;
}node[maxn << 2];

void pushUp(int rt) {
    node[rt].v = node[rt << 1].v + node[rt << 1 | 1].v;
}

void pushDown(int rt, int m) {
    if (node[rt].lazy != 0) {
        //node[rt].v = m * node[rt].lazy;
        node[rt << 1].v = node[rt].lazy * (m - (m >> 1));
        node[rt << 1|1].v = node[rt].lazy * (m >> 1);
        node[rt << 1].lazy = node[rt << 1 | 1].lazy = node[rt].lazy;
        node[rt].lazy = 0;;
    }
}
void build(int rt, int l, int r) {
    if (l == r) {
        scanf("%d", &node[rt].v);
        return;
    }

    build(ls);
    build(rs);

    pushUp(rt);
}

void update(int rt, int l, int r, int ul, int ur, int cal) {
    if (ul <= l && ur >= r) {
        node[rt].lazy = cal;
        node[rt].v = (r - l + 1) * cal;
        return;
    }

    pushDown(rt, r - l + 1);

    if (ul <= mid) {
        update(ls, ul, ur, cal);
    }

    if (ur > mid) {
        update(rs, ul, ur, cal);
    }

    pushUp(rt);
}

int query(int rt, int l, int r, int ql, int qr) {
    if (ql <= l && qr >= r) {
        return node[rt].v;
    }

    pushDown(rt, r - l + 1);

    int res = 0;
    if (ql <= mid)  res += query(ls, ql, qr);
    if (qr > mid)   res += query(rs, ql, qr);

    return res;
}
int main() {
#if debug
    freopen("in.txt", "r", stdin);
#endif //debug
    int q, k, a, b, c;

    M(node, 0);
    scanf("%d", &n);
    build(1, 1, n);
    scanf("%d", &q);
    while (q--) {
        scanf("%d", &k);
        if (k) {
            scanf("%d%d%d", &a, &b, &c);
            update(1, 1, n, a, b, c);
        }
        else {
            scanf("%d%d", &a, &b);
            printf("%d
"
, query(1, 1, n, a, b)); } } return 0; }

좋은 웹페이지 즐겨찾기