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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 1754 단일 업데이트 구간 구문 및 zkw 세그먼트 트리 + 귀속 세그먼트 트리HDOJ 1754 라인 트리 누드 문제, 직접 코드. AC code: 반복 세그먼트 트리: 매크로를 쓸 때 괄호를 반드시 주의해야 한다. 처음에mid는 매크로로 괄호를 쓰지 않았다... zkw 세그먼트 트리, 훨씬 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.