글 읽기 - 자료구조의 시간차이에 대한 질문..

jason9319 8년 전 0

parallel binary search를 공부하려고 boj 8217번을 공부하다가 궁금증이 생겼는데

문제에서 구간의 합을 처리하는 연산을 보통 다 bit를 이용해서 처리해주시더라구요

저는 lazy propagation를 이용한 segment tree로 처리를 했는데 TLE를 맞아서

이용한 자료구조만 다를 뿐인데 시간차이가 나길래 ㅜㅜ

lazy_propagation에서 업데이트나 쿼리를 처리하는 시간복잡도가 logN이 보장되는거 아닌가요?

물론 제가 잘못 구현하였을수도 있습니다..

//BIT를 이용하여 AC받은 코드
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
ll n, m, need[300030], k, lo[300030], hi[300030], ql[300030], qr[300030], qa[300030], x;
ll tree[300030];
vector<ll> vt[300030];
vector<ll> ground[300030];
void update(ll x, long long val) {
	while (x <= m) {
		tree[x] += val;
		x += (x&-x);
 
	}
}
long long read(int x) {
	long long s = 0;
	while (x>0) {
		s += tree[x];
		x -= (x&-x);
	}
	return s;
}
 
void apply(ll x) {
	if (ql[x] <= qr[x])
		update(ql[x], qa[x]), update(qr[x] + 1, -qa[x]);
	else {
		update(1, qa[x]);
		update(qr[x] + 1, -qa[x]);
		update(ql[x], qa[x]);
	}
}
int main() {
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%lld", &x);
		ground[x].push_back(i);
	}
	for (int i = 1; i <= n; i++)
		scanf("%lld", &need[i]);
	scanf("%lld", &k);
	for (int i = 1; i <= k; i++) 
		scanf("%lld%lld%lld", &ql[i], &qr[i], &qa[i]);
	for (int i = 1; i <= n; i++) 
		lo[i] = 1, hi[i] = k + 1;
	bool f = 1;
	while (f) {
		f = 0;
		memset(tree, 0, sizeof(tree));
		for (int i = 1; i <= n; i++) {
			if (lo[i] < hi[i])
				vt[(lo[i] + hi[i]) >> 1].push_back(i);
		}
		for (int i = 1; i <= k; i++) {
			apply(i);
			while (vt[i].size()) {
				f = 1;
				int idx = vt[i].back();
				vt[i].pop_back();
				ll sum = 0;
				for (auto next : ground[idx]) {
					sum += read(next);
					if (sum >= need[idx])break;
				}
				if (sum >= need[idx])
					hi[idx] = i;
				else
					lo[idx] = i + 1;
			}
		}
 
	}
	for (int i = 1; i <= n; i++) {
		if (lo[i] > k)
			puts("NIE");
		else
			printf("%d\n", lo[i]);
	}
	return 0;
} 

//lazy_propagation을 이용한 TLE받은 코드

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
ll n, m, need[300030], k, lo[300030], hi[300030], ql[300030], qr[300030], qa[300030], x, lazy[1200000], seg[1200000];
vector<ll> vt[300030];
vector<ll> ground[300030];
void update_lazy(ll node, ll x, ll y) {
	if (!lazy[node])
		return;
	seg[node] += lazy[node] * (y - x + 1);
	if (x != y) {
		lazy[node * 2] += lazy[node];
		lazy[node * 2 + 1] += lazy[node];
	}
	lazy[node] = 0;
}
ll update(ll lo, ll hi, ll val, ll node, ll x, ll y) {
	update_lazy(node, x, y);
	if (y < lo || hi < x)return seg[node];
	if (lo <= x&&y <= hi) {
		lazy[node] += val;
		update_lazy(node, x, y);
		return seg[node];
	}
	ll mid = (x + y) >> 1;
	return seg[node] = update(lo, hi, val, node * 2, x, mid) + update(lo, hi, val, node * 2 + 1, mid + 1, y);
}
ll query(ll pos, ll node, ll x, ll y) {
	update_lazy(node, x, y);
	if (y < pos || pos < x)return 0;
	if (x == y)
		return seg[node];
	ll mid = (x + y) >> 1;
	return query(pos, node * 2, x, mid) + query(pos, node * 2 + 1, mid + 1, y);
}
int main() {
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%lld", &x);
		ground[x].push_back(i);
	}
	for (int i = 1; i <= n; i++)
		scanf("%lld", &need[i]);
	scanf("%lld", &k);
	for (int i = 1; i <= k; i++)
		scanf("%lld%lld%lld", &ql[i], &qr[i], &qa[i]);
	for (int i = 1; i <= n; i++)
		lo[i] = 1, hi[i] = k + 1;
	bool f = 1;
	while (f) {
		f = 0;
		for (int i = 0; i < 1200000; i++) {
			seg[i] = 0;
			lazy[i] = 0;
		}
		for (int i = 1; i <= n; i++) {
			if (lo[i] < hi[i])
				vt[(lo[i] + hi[i]) >> 1].push_back(i);
		}
		for (int i = 1; i <= k; i++) {
			if (ql[i] <= qr[i])
				update(ql[i], qr[i], qa[i], 1, 1, m);
			else {
				update(1, qr[i], qa[i], 1, 1, m);
				update(ql[i], m, qa[i], 1, 1, m);
			}
			while (vt[i].size()) {
				f = 1;
				ll idx = vt[i].back();
				vt[i].pop_back();
				ll sum = 0;
				for (auto next : ground[idx]) {
					sum += query(next, 1, 1, m);
					if (sum >= need[idx])break;
				}
				if (sum >= need[idx])
					hi[idx] = i;
				else
					lo[idx] = i + 1;
			}
		}

	}
	for (int i = 1; i <= n; i++) {
		if (lo[i] > k)
			puts("NIE");
		else
			printf("%d\n", lo[i]);
	}
	return 0;
}

jason9319 8년 전 0

답변해주신 @cubelover님 @zlzmsrhak님 감사합니다

byeongkeunahn 7년 전 0

Segment Tree with Lazy Propagation으로 3초 후반에서 4초 중반 정도로 통과 가능한 것 같습니다. BIT로는 1.5초 정도 나왔습니다

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

문제

문제

출처

ICPC

자료구조의 시간차이에 대한 질문..

jason9319 8년 전 0

jason9319 8년 전 0

byeongkeunahn 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말