首先分析一下题目,对于这棵树,操作如下:
- 查询从 X 到 Y 的路径上的前 k 大的值。
- 把 $P_i$ 上的武力值减去一个 $F_i$ 并在 Y 上的武力值加上一个 $F_i$,再把 $P_i$ 改成 Y。
- 将 $P_i$ 上的武力值减去一个 $F_i$ 再加上一个 Y,并把 $F_i$ 改成 Y。
由第一个我们可以想到,先用树剖,再用线段树处理。每个节点上存储该范围下的前 k 大,每个地方的武力值就用 multiset 存下来就可以了。因为 $k \le 20$,所以每个叶子节点暴力更新就可以了。PushUp 就用归并排序的方式合并两个子节点的前 k 大,最后用常规的树剖操作查询就结束了。
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int N = 40000 + 5;
int n, m, Q, K;
int F[N], P[N];
vector<int> V[N];
multiset <int, greater<int> > S[N];
int fa[N], dep[N], siz[N], son[N];
int top[N], id[N], cnt;
void dfs1(int sx, int ffa) {
fa[sx] = ffa;
dep[sx] = dep[ffa] + 1;
siz[sx] = 1;
int maxn = -1;
for (auto to : V[sx]) {
if (to == ffa) continue;
dfs1 (to, sx);
siz[sx] += siz[to];
if (siz[to] > maxn) {
maxn = siz[to];
son[sx] = to;
}
}
return ;
}
void dfs2(int sx, int topf) {
top[sx] = topf;
id[sx] = ++ cnt;
if (son[sx]) dfs2 (son[sx], topf);
for (auto to : V[sx]) {
if (to == fa[sx] || to == son[sx]) continue;
dfs2 (to, to);
}
return ;
}
struct sgt {
struct node {
int res[25], len;
}sum[N << 2];
node merge(node A, node B) {
node C;
C.len = 0;
int i = 1, j = 1;
while (i <= A.len && j <= B.len && C.len < K) {
if (A.res[i] > B.res[j])
C.res[++ C.len] = A.res[i ++];
else C.res[++ C.len] = B.res[j ++];
}
while (i <= A.len && C.len < K) C.res[++ C.len] = A.res[i ++];
while (j <= B.len && C.len < K) C.res[++ C.len] = B.res[j ++];
return C;
}
void PushUp (int u) {
sum[u] = merge(sum[u << 1], sum[u << 1 | 1]);
return ;
}
void build (int u, int l, int r) {
if (l == r) {
sum[u].len = 0;
for (auto i : S[l]) {
sum[u].res[++ sum[u].len] = i;
if (sum[u].len == K)
break;
}
return ;
}
int mid = l + r >> 1;
build (u << 1, l, mid);
build (u << 1 | 1, mid + 1, r);
PushUp (u);
}
void modify(int u, int l, int r, int pos, int add, int red) {
if (l == r) {
if (add != -1) S[pos].emplace (add);
if (red != -1) S[pos].erase (S[pos].find(red));
sum[u].len = 0;
for (auto i : S[l]) {
sum[u].res[++ sum[u].len] = i;
if (sum[u].len == K)
break;
}
return ;
}
int mid = l + r >> 1;
if (pos <= mid)
modify (u << 1, l, mid, pos, add, red);
if (mid < pos)
modify (u << 1 | 1, mid + 1, r, pos, add, red);
PushUp (u);
return ;
}
node query(int u, int l, int r, int L, int R) {
if (L <= l && r <= R) return sum[u];
int mid = l + r >> 1;
if (R <= mid)
return query (u << 1, l, mid, L, R);
if (L > mid)
return query (u << 1 | 1, mid + 1, r, L, R);
return merge (query (u << 1, l, mid, L, R), query (u << 1 | 1, mid + 1, r, L, R));
}
node get(int x, int y) {
node ans;
ans.len = 0;
while (top[x] != top[y]) {
if (dep[top[x]] > dep[top[y]])
swap (x, y);
ans = merge (ans, query (1, 1, n, id[top[y]], id[y]));
y = fa[top[y]];
}
if (dep[x] > dep[y]) swap (x, y);
ans = merge (ans, query (1, 1, n, id[x], id[y]));
return ans;
}
}tre;
int main() {
scanf ("%d", &n);
for (int i = 1;i < n; ++ i) {
int u, v;
scanf ("%d%d", &u, &v);
V[u].push_back(v);
V[v].push_back(u);
}
scanf ("%d", &m);
for (int i = 1;i <= m; ++ i)
scanf ("%d%d", F + i, P + i);
dfs1 (1, 1);
dfs2 (1, 1);
for (int i = 1;i <= m; ++ i)
S[id[P[i]]].emplace (F[i]);
scanf ("%d%d", &Q, &K);
tre.build(1, 1, n);
while (Q--) {
int opt, X, Y;
scanf ("%d%d%d", &opt, &X, &Y);
if (opt == 1) {
sgt :: node ans;
ans = tre.get (X, Y);
for (int i = 1;i <= ans.len; ++ i)
printf ("%d ", ans.res[i]);
if (ans.len == 0) printf ("-1");
puts("");
}
if (opt == 2) {
tre.modify (1, 1, n, id[P[X]], -1, F[X]);
P[X] = Y;
tre.modify (1, 1, n, id[P[X]], F[X], -1);
}
if (opt == 3) {
tre.modify (1, 1, n, id[P[X]], Y, F[X]);
F[X] = Y;
}
}
return 0;
}
标签:dep,sx,剖分,int,res,BJOI2015,P5478,++,id
From: https://www.cnblogs.com/Assassins-Creed/p/18018378