【線分樹】HDOJ 5361 In Touch
2660 ワード
シンプルな線分樹です...最短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;
}