laekov

BZOJ3672 [NOI2014]购票

考场上只想到暴力。


如果只是一条链的话怎么乱搞一搞?


如果没有深度限制的话简单的斜率优化+链剖就行了。


有深度限制就把hull扔到线段树里用可持久化栈来维护一下。DFS的时候塞进线段树里,然后完了再扔出来。总的复杂度O(n*log^2(n)),


代码也不怎么复杂。


#include <cstdio>

#include <cctype>

#include <memory.h>

#include <vector>

#include <algorithm>


using namespace std;


struct edge {

int t;

edge* next;

};

typedef long long qw;

typedef long double exf;


#ifdef WIN32

#define lld "%I64d"

#else

#define lld "%lld"

#endif

#define _l (qw)

#define readInt(_s_) {\

int _d_;\

_s_ = 0;\

while (!isdigit(_d_ = getchar()));\

while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\

}


struct oper {

int p, v, t;

oper(int p0 = 0, int v0 = 0, int t0 = 0) {

p = p0, v = v0, t = t0;

}

};

struct phull {

int *s, t;

vector <oper> r;

};

struct seg {

int l, r;

phull d;

seg *ls, *rs;

};


const int maxn = 200009;

const qw inf = 0x3f3f3f3f3f3f3f3fLL;

const exf eps = 1e-8;


qw d[maxn], k[maxn], b[maxn], dl[maxn], f[maxn];

int n, fa[maxn], stc[maxn];

edge *head[maxn], *ep;

seg *rt, *sp;


inline exf getK(int a, int b) {

return ((exf)f[b] - f[a]) / ((exf)d[b] - d[a]);

}


inline void addEdge(int u, int v) {

ep-> t = v;

ep-> next = head[u];

head[u] = ep ++;

}


#define mid(p) ((p->l+p->r)>>1)


void phIns(phull& h, int v0) {

if (!h. t) {

h. r. push_back(oper(1, 0, 0));

h. s[h. t = 1] = v0;

}

else if (h. t == 1) {

h. r. push_back(oper(2, 0, 1));

h. s[h. t = 2] = v0;

}

else {

int l = 2, r = h. t;

while (l < r) {

int mid = (l + r + 1) >> 1;

if (getK(h. s[mid - 1], h. s[mid]) > getK(h. s[mid - 1], v0) + eps)

r = mid - 1;

else

l = mid;

}

if (l > 2 || getK(h. s[1], h. s[2]) <= getK(h. s[1], v0))

++ l;

h. r. push_back(oper(l, h. s[l], h. t));

h. s[h. t = l] = v0;

}

}


void phCancel(phull& h) {

if (h. r. empty())

return;

oper o = *h. r. rbegin();

h. r. pop_back();

h. s[o. p] = o. v;

h. t = o. t;

}


qw phQry(phull& h, int i) {

int l = 1, r = h. t - 1;

if (!h. t)

return inf;

while (l < r) {

int mid = (l + r) >> 1;

if (getK(h. s[mid], h. s[mid + 1]) + eps < k[i])

l = mid + 1;

else

r = mid;

}

if (l == h. t - 1 && getK(h. s[l], h. s[l + 1]) + eps < k[i])

++ l;

return f[h. s[l]] + (d[i] - d[h. s[l]]) * k[i] + b[i];

}


seg *sgtBuild(int l, int r) {

seg *p = sp ++;

p-> d. s = new int[r - l + 3];

p-> d. t = 0;

p-> l = l;

p-> r = r;

if (l + 1 < r) {

p-> ls = sgtBuild(l, mid(p));

p-> rs = sgtBuild(mid(p), r);

}

return p;

}


void sgtChg(seg* p, int p0, int v0) {

if (v0 == -1)

phCancel(p-> d);

else

phIns(p-> d, v0);

if (p-> l + 1 < p-> r) {

if (p0 < mid(p))

sgtChg(p-> ls, p0, v0);

else

sgtChg(p-> rs, p0, v0);

}

}


qw sgtQry(seg* p, int l, int r, int v0) {

if (l >= r)

return inf;

else if (l == p-> l && r == p-> r)

return phQry(p-> d, v0);

else if (r <= mid(p))

return sgtQry(p-> ls, l, r, v0);

else if (l >= mid(p))

return sgtQry(p-> rs, l, r, v0);

else

return min(sgtQry(p-> ls, l, mid(p), v0), sgtQry(p-> rs, mid(p), r, v0));

}


qw getAns(int p, int d0) {

int l = 1, r = d0;

while (l < r) {

int mid = (l + r) >> 1;

if (d[p] - d[stc[mid]] > dl[p])

l = mid + 1;

else

r = mid;

}

return sgtQry(rt, l, d0 + 1, p);

}


void dfs(int p, int d0) {

if (p > 1)

f[p] = getAns(p, d0 - 1);

sgtChg(rt, d0, p);

stc[d0] = p;

for (edge* e = head[p]; e; e = e-> next)

dfs(e-> t, d0 + 1);

sgtChg(rt, d0, -1);

}


int main() {

#ifndef ONLINE_JUDGE

freopen("ticket.in", "r", stdin);

freopen("ticket.out", "w", stdout);

#endif


memset(head, 0, sizeof(head));

ep = new edge[maxn];

qw tmp;

readInt(n);

readInt(tmp);

sp = new seg[maxn * 3];

rt = sgtBuild(1, n + 1);

d[1] = 0;

f[1] = 0;

for (int i = 2; i <= n; ++ i) {

readInt(fa[i]);

addEdge(fa[i], i);

readInt(tmp);

d[i] = d[fa[i]] + tmp;

readInt(k[i]);

readInt(b[i]);

readInt(dl[i]);

}

dfs(1, 1);

for (int i = 2; i <= n; ++ i)

printf(lld "\n", f[i]);

}



评论

© laekov | Powered by LOFTER