P4175 [CTSC2008]網絡管理
每次詢問兩點間的第 k k k大,考慮建立 n n n棵主席樹,每棵主席樹記錄的是從根節點到目前節點的狀态,
由于主席樹是一種類似字首和的資料結構,可以使用差分的方式得到 ( u , v ) (u, v) (u,v)點對之間的主席樹為 u + v − l c a ( u , v ) − f a ( l c a ( u , v ) ) u + v - lca(u, v) - fa(lca(u, v)) u+v−lca(u,v)−fa(lca(u,v)),
#include <bits/stdc++.h>
using namespace std;
const int N = 8e4 + 10, maxn = 100000000;
int a[N], n, m;
int head[N], to[N << 1], nex[N << 1], cnt = 1;
int son[N], sz[N], l[N], r[N], dep[N], top[N], fa[N], tot;
int root[N], sum[N << 8], ls[N << 8], rs[N << 8], num;
int A[N], B[N], cnt1, cnt2;
inline int lowbit(int x) {
return x & (-x);
}
inline void add(int x, int y) {
to[cnt] = y;
nex[cnt] = head[x];
head[x] = cnt++;
}
void update(int &rt, int l, int r, int x, int v) {
if (!rt) {
rt = ++num;
}
sum[rt] += v;
if (l == r) {
return ;
}
int mid = l + r >> 1;
if (x <= mid) {
update(ls[rt], l, mid, x, v);
}
else {
update(rs[rt], mid + 1, r, x, v);
}
}
void dfs1(int rt, int f) {
fa[rt] = f, l[rt] = ++tot, sz[rt] = 1, dep[rt] = dep[f] + 1;
for (int i = l[rt]; i <= n; i += lowbit(i)) {
update(root[i], 0, maxn, a[rt], 1);
}
for (int i = head[rt]; i; i = nex[i]) {
if (to[i] == f) {
continue;
}
dfs1(to[i], rt);
sz[rt] += sz[to[i]];
if (!son[rt] || sz[son[rt]] < sz[to[i]]) {
son[rt] = to[i];
}
}
r[rt] = tot;
for (int i = r[rt] + 1; i <= n; i += lowbit(i)) {
update(root[i], 0, maxn, a[rt], -1);
}
}
void dfs2(int rt, int tp) {
top[rt] = tp;
if (!son[rt]) {
return ;
}
dfs2(son[rt], tp);
for (int i = head[rt]; i; i = nex[i]) {
if (to[i] == fa[rt] || to[i] == son[rt]) {
continue;
}
dfs2(to[i], to[i]);
}
}
int lca(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) {
swap(x, y);
}
x = fa[top[x]];
}
return dep[x] < dep[y] ? x : y;
}
int query(int l, int r, int k) {
if (l == r) {
return l;
}
int cur = 0, mid = l + r >> 1;
for (int i = 1; i <= cnt1; i++) {
cur += sum[ls[A[i]]];
}
for (int i = 1; i <= cnt2; i++) {
cur -= sum[ls[B[i]]];
}
if (cur >= k) {
for (int i = 1; i <= cnt1; i++) {
A[i] = ls[A[i]];
}
for (int i = 1; i <= cnt2; i++) {
B[i] = ls[B[i]];
}
return query(l, mid, k);
}
else {
for (int i = 1; i <= cnt1; i++) {
A[i] = rs[A[i]];
}
for (int i = 1; i <= cnt2; i++) {
B[i] = rs[B[i]];
}
return query(mid + 1, r, k - cur);
}
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (int i = 1; i < n; i++) {
int x, y;
scanf("%d %d", &x, &y);
add(x, y);
add(y, x);
}
dfs1(1, 0);
dfs2(1, 1);
for (int i = 1; i <= m; i++) {
int k, u, v;
scanf("%d %d %d", &k, &u, &v);
if (!k) {
for (int i = l[u]; i <= n; i += lowbit(i)) {
update(root[i], 0, maxn, a[u], -1);
}
for (int i = r[u] + 1; i <= n; i += lowbit(i)) {
update(root[i], 0, maxn, a[u], 1);
}
a[u] = v;
for (int i = l[u]; i <= n; i += lowbit(i)) {
update(root[i], 0, maxn, a[u], 1);
}
for (int i = r[u] + 1; i <= n; i += lowbit(i)) {
update(root[i], 0, maxn, a[u], -1);
}
}
else {
int f = lca(u, v), ff = fa[f], total = dep[u] + dep[v] - dep[f] - dep[ff];
if (total < k) {
puts("invalid request!");
}
else {
cnt1 = cnt2 = 0;
for (int i = l[u]; i; i -= lowbit(i)) {
A[++cnt1] = root[i];
}
for (int i = l[v]; i; i -= lowbit(i)) {
A[++cnt1] = root[i];
}
for (int i = l[f]; i; i -= lowbit(i)) {
B[++cnt2] = root[i];
}
for (int i = l[ff]; i; i -= lowbit(i)) {
B[++cnt2] = root[i];
}
k = total - k + 1;
printf("%d\n", query(0, maxn, k));
}
}
}
return 0;
}