数据结构题总是很令人开心的。
这题据说可以主席树？好麻烦的说。
树链剖分+线段树+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);
}
}
}
}