laekov

BZOJ1146 [CTSC2008]网络管理Network

数据结构题总是很令人开心的。


这题据说可以主席树?好麻烦的说。


树链剖分+线段树+treap就好了吧。


#include <cstdio>

#include <cstdlib>

#include <cctype>

#include <memory.h>

#include <algorithm>


using namespace std;


struct edge {

int t;

edge *next;

};

struct seg {

int l, r, v;

seg *ls, *rs;

};


#define readInt(_s_) {\

int _d_;\

_s_ = 0;\

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

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

}


const int maxn = 80009;

const int maxv = 1e8;


namespace treap {

struct node {

int ls, rs, v, w, sz;

};

const int maxnd = 80009 * 19;

node a[maxnd];

int tn, nst[maxnd];

void init() {

srand(239407234);

a[0]. sz = 0;

tn = 0;

for (int i = 1; i < maxnd; ++ i)

nst[++ tn] = i;

}

inline int newNode(int v) {

int p = nst[tn --];

a[p]. ls = 0;

a[p]. rs = 0;

a[p]. v = v;

a[p]. w = rand() | (rand() << 16);

a[p]. sz = 1;

return p;

}

inline void update(const int& p) {

a[p]. sz = a[a[p]. ls]. sz + a[a[p]. rs]. sz + 1;

}

inline void lRot(int& p) {

int q = a[p]. rs;

a[p]. rs = a[q]. ls;

a[q]. ls = p;

update(p);

update(q);

p = q;

}

inline void rRot(int& p) {

int q = a[p]. ls;

a[p]. ls = a[q]. rs;

a[q]. rs = p;

update(p);

update(q);

p = q;

}

inline void maintain(int& p, bool d) {

if (d) {

if (a[a[p]. ls]. w > a[p]. w)

rRot(p);

}

else

if (a[a[p]. rs]. w > a[p]. w)

lRot(p);

}

inline void ins(int& p, int v) {

if (!p)

p = newNode(v);

else {

if (v < a[p]. v)

ins(a[p]. ls, v);

else

ins(a[p]. rs, v);

update(p);

maintain(p, v < a[p]. v);

}

}

inline void ers(int& p, int v) {

if (!p)

return;

else if (a[p]. v == v) {

if (!a[p]. ls)

p = a[p]. rs;

else if (!a[p]. rs)

p = a[p]. ls;

else {

int q = a[p]. ls;

while (a[q]. rs)

q = a[q]. rs;

a[p]. v = a[q]. v;

ers(a[p]. ls, a[p]. v);

update(p);

}

}

else {

if (v < a[p]. v)

ers(a[p]. ls, v);

else

ers(a[p]. rs, v);

update(p);

}

}

inline int cnt(int p, int v) {

if (!p)

return 0;

else if (v <= a[p]. v)

return cnt(a[p]. ls, v);

else

return a[a[p]. ls]. sz + 1 + cnt(a[p]. rs, v);

}

};


int n, q, v[maxn];

int tc, d[maxn], fa[maxn], sz[maxn], ch[maxn], fc[maxn], cl[maxn];

seg *rt[maxn], *sp;

edge *ep, *head[maxn];


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)


inline seg* sgtBuild(int l, int r) {

seg* p = sp ++;

p-> l = l;

p-> r = r;

p-> v = 0;

if (l + 1 < r) {

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

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

}

return p;

}


inline void sgtChg(seg* p, int p0, int v, int ty) {

if (ty == 1)

treap :: ins(p-> v, v);

else

treap :: ers(p-> v, v);

if (p-> l + 1 == p-> r)

return;

else if (p0 < mid(p))

sgtChg(p-> ls, p0, v, ty);

else

sgtChg(p-> rs, p0, v, ty);

}


inline int sgtQry(seg* p, int l, int r, int v) {

if (l >= r)

return 0;

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

return treap :: cnt(p-> v, v);

else if (r <= mid(p))

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

else if (l >= mid(p))

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

else

return sgtQry(p-> ls, l, mid(p), v) + sgtQry(p-> rs, mid(p), r, v);

}


#define cpos(_p_) (d[_p_]-d[ch[fc[_p_]]])


void divide() {

static int q[maxn];

int hd = 0, tl = 1;

memset(d, 0, sizeof(d));

d[1] = 1;

fa[1] = 0;

q[0] = 1;

while (hd < tl) {

int p = q[hd ++];

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

if (!d[e-> t]) {

d[e-> t] = d[p] + 1;

fa[e-> t] = p;

q[tl ++] = e-> t;

}

}

tc = 0;

for (int ti = tl - 1; ti >= 0; -- ti) {

int p = q[ti], x = -1;

sz[p] = 1;

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

if (fa[e-> t] == p) {

sz[p] += sz[e-> t];

if (x == -1 || sz[e-> t] > sz[x])

x = e-> t;

}

if (x == -1) {

fc[p] = ++ tc;

ch[fc[p]] = p;

cl[fc[p]] = 1;

}

else {

fc[p] = fc[x];

ch[fc[p]] = p;

++ cl[fc[p]];

}

}

sp = new seg[maxn * 4];

for (int i = 1; i <= tc; ++ i)

rt[i] = sgtBuild(0, cl[i]);

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

sgtChg(rt[fc[i]], cpos(i), v[i], 1);

}


int LCA(int u, int v) {

while (fc[u] ^ fc[v])

if (d[ch[fc[u]]] > d[ch[fc[v]]])

u = fa[ch[fc[u]]];

else

v = fa[ch[fc[v]]];

if (d[u] < d[v])

return u;

else

return v;

}


int cntChain(int u, int a, int v) {

int s = 0;

while (fc[u] ^ fc[a]) {

s += sgtQry(rt[fc[u]], 0, cpos(u) + 1, v);

u = fa[ch[fc[u]]];

}

if (u ^ a)

s += sgtQry(rt[fc[u]], cpos(a) + 1, cpos(u) + 1, v);

return s;

}


int main() {

#ifndef ONLINE_JUDGE

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

#endif


treap :: init();

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

ep = new edge[maxn * 2];

readInt(n);

readInt(q);

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

readInt(v[i]);

for (int i = 0; i < n - 1; ++ i) {

int u, v;

readInt(u);

readInt(v);

addEdge(u, v);

addEdge(v, u);

}

divide();

while (q --) {

int k, a, b;

readInt(k);

readInt(a);

readInt(b);

if (!k) {

sgtChg(rt[fc[a]], cpos(a), v[a], -1);

v[a] = b;

sgtChg(rt[fc[a]], cpos(a), v[a], 1);

}

else {

int l = 0, r = maxv, c = LCA(a, b);

if (d[a] + d[b] - d[c] * 2 + 1 < k)

puts("invalid request!");

else {

k = d[a] + d[b] - d[c] * 2 + 2 - k;

while (l < r) {

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

if (cntChain(a, c, mid) + cntChain(b, fa[c], mid) >= k)

r = mid - 1;

else

l = mid;

}

printf("%d\n", l);

}

}

}

}


评论

© laekov | Powered by LOFTER