글 읽기 - 이 문제는 lazy propagation으로 못푸나요?

dntjd1081 4년 전 0

평범하게 lazy propagation으로 풀려고하는데 계속 10%정도에서 시간초과 뜨네요 쿼리하나당 lg10^5라고할때 시간안에 모두 가능하지 않나요?

어떤식으로 시간을 줄여야할까요? 아니면 아예 코드 자체가 잘못된 부분이 있는건가요? 알려주시면 감사하겠습니다...ㅠ

#include<iostream>
#include<cmath>
using namespace std;
#define MAX 1000001
typedef long long ll;

ll N, Q;
ll A[MAX], seq[MAX * 4], lazy[MAX * 4];

ll init(ll nodeLeft, ll nodeRight, ll node) { //초기화
	if (nodeLeft == nodeRight)
		return seq[node] = A[nodeLeft];

	ll mid = (nodeLeft + nodeRight) / 2;
	return seq[node] = init(nodeLeft, mid, node * 2)
		+ init(mid + 1, nodeRight, node * 2 + 1);
}

void update_lazy(ll nodeLeft, ll nodeRight, ll node) {
	if (lazy[node] != 0) {
		ll sum = 0;
        //lazy에 저장되있는 크기에서 구간의 길이만큼 1씩 줄여가며 더해준다. 
		for (ll i = nodeLeft, added = lazy[node]; i <= nodeRight; ++i, --added)
			sum += added;
		seq[node] += sum; //그 구간의 합

		if (nodeLeft != nodeRight) {
            //왼쪽 부분은 왼쪽 부분의 제일 뒤 원소의 크기(최대)를 넣어주고
			lazy[node * 2] = lazy[node] - (nodeRight - (nodeLeft + nodeRight) / 2);
			//오른쪽 부분는 현재 제일 뒤 원소 유지
            lazy[node * 2 + 1] = lazy[node];
		}

		lazy[node] = 0;
	}
}

//이 이후는 일반적인 lazy propagation 코드와 동일합니다.
ll update_range(ll nodeLeft, ll nodeRight, ll start, ll end, ll node,ll value) {
	update_lazy(nodeLeft, nodeRight, node);

	if (nodeLeft > end || nodeRight < start)
		return seq[node];

	if (start <= nodeLeft && nodeRight <= end) {
		lazy[node] += value;
		update_lazy(nodeLeft, nodeRight, node);
		return seq[node];
	}

	ll mid = (nodeLeft + nodeRight) / 2;
    
    
	return seq[node] = update_range(nodeLeft, mid, start, end, node * 2, value / 2)
		+ update_range(mid + 1, nodeRight, start, end, node * 2 + 1, value);
}

ll query(ll nodeLeft, ll nodeRight, ll start, ll end, ll node) {
	update_lazy(nodeLeft, nodeRight, node);
	if (nodeLeft > end || nodeRight < start)
		return 0;

	if (start <= nodeLeft && nodeRight <= end)
		return seq[node];

	ll mid = (nodeLeft + nodeRight) / 2;
	return query(nodeLeft, mid, start, end, node * 2) +
		query(mid + 1, nodeRight, start, end, node * 2 + 1);
}

int main() {
	scanf("%lld", &N);
	for (ll i = 0; i < N; ++i)
		scanf("%lld", &A[i]);
	init(0, N - 1, 1);

	scanf("%lld", &Q);
	while (Q--) {
		ll k, L, R;
		scanf("%lld", &k);
		if (k == 1) {
			scanf("%lld %lld", &L, &R);
			update_range(0, N - 1, L - 1, R - 1, 1, R - L + 1);
		}
		else {
			scanf("%lld", &L);
			printf("%lld\n", query(0, N - 1, L - 1, L - 1, 1));
		}
	}
}

djm03178 4년 전 0

lazy를 할 때 구간의 크기만큼씩 돌고 있기 때문에 쿼리당 O(N)의 시간이 걸립니다.

dntjd1081 4년 전 0

아.....진짜 정말 감사합니다......하 ㅜㅠㅠㅠ 저번에도 도움 받은거같은데 감사합니다!!!!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이 문제는 lazy propagation으로 못푸나요?

dntjd1081 4년 전 0

djm03178 4년 전 0

dntjd1081 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말