【線分樹】HDOJ 5361 In Touch

シンプルな線分樹です...最短dijをセグメントツリーでシミュレートすればいいのですが..

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

#define lson o << 1, L, mid
#define rson o << 1 | 1, mid + 1, R
#define ls o << 1
#define rs o << 1 | 1
#define mp(x, y) make_pair(x, y)

const int maxn = 200005;
const LL INF = 1e16;

pair<LL, int> minv[maxn << 2];
LL lazy[maxn << 2];
LL ans[maxn];
int l[maxn];
int r[maxn];
int c[maxn];
int n, m;

void pushup(int o)
{
	if(minv[ls].first == -1) {
		if(minv[rs].first == -1) minv[o] = mp(-1LL, 0);
		else minv[o] = minv[rs];
	}
	else {
		if(minv[rs].first == -1) minv[o] = minv[ls];
		else minv[o] = min(minv[ls], minv[rs]);
	}
}

void pushdown(int o)
{
	if(lazy[o] != INF) {
		minv[ls].first = min(minv[ls].first, lazy[o]);
		minv[rs].first = min(minv[rs].first, lazy[o]);
		lazy[ls] = min(lazy[ls], lazy[o]);
		lazy[rs] = min(lazy[rs], lazy[o]);
		lazy[o] = INF;
	}
}

void build(int o, int L, int R)
{
	lazy[o] = INF;
	if(L == R) {
		if(L == 1) minv[o] = mp(0LL, L);
		else minv[o] = mp(INF, L);
		return;
	}
	int mid = (L + R) >> 1;
	build(lson);
	build(rson);
	pushup(o);
}

void update(int o, int L, int R, int ql, int qr, LL v)
{
	if(ql <= L && qr >= R) {
		lazy[o] = min(lazy[o], v);
		minv[o].first = min(minv[o].first, v);
		return;
	}
	pushdown(o);
	int mid = (L + R) >> 1;
	if(ql <= mid) update(lson, ql, qr, v);
	if(qr > mid) update(rson, ql, qr, v);
	pushup(o);
}

void update(int o, int L, int R, int q)
{
	if(L == R) {
		minv[o].first = -1;
		return;
	}
	pushdown(o);
	int mid = (L + R) >> 1;
	if(q <= mid) update(lson, q);
	else update(rson, q);
	pushup(o);
}

void work()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &l[i]);
	for(int i = 1; i <= n; i++) scanf("%d", &r[i]);
	for(int i = 1; i <= n; i++) scanf("%d", &c[i]);
	
	build(1, 1, n);
	
	for(int i = 1; i <= n; i++) ans[i] = INF;
	for(int C = 1; C <= n; C++) {
		LL v = minv[1].first;
		int id = minv[1].second;
		if(v == -1) break;
		ans[id] = v;
		update(1, 1, n, id);

		int ql = id + l[id], qr = min(id + r[id], n);
		if(qr >= ql) update(1, 1, n, ql, qr, v + c[id]);

		ql = max(id - r[id], 1), qr = id - l[id];
		if(qr >= ql) update(1, 1, n, ql, qr, v + c[id]);
	}
	for(int i = 1; i <= n; i++) {
		if(ans[i] == INF) printf("-1%c", i == n ? '
' : ' ');
		else printf("%lld%c", ans[i], i == n ? '
' : ' ');
	}
}

int main()
{
	int _;
	scanf("%d", &_);
	while(_--) work();
	
	return 0;
}