首页 > 其他分享 >P5478 [BJOI2015] 骑士的旅行 - 重链剖分

P5478 [BJOI2015] 骑士的旅行 - 重链剖分

时间:2024-02-17 20:56:42浏览次数:26  
标签:dep sx 剖分 int res BJOI2015 P5478 ++ id

首先分析一下题目,对于这棵树,操作如下:

  1. 查询从 X 到 Y 的路径上的前 k 大的值。
  2. 把 $P_i$ 上的武力值减去一个 $F_i$ 并在 Y 上的武力值加上一个 $F_i$,再把 $P_i$ 改成 Y。
  3. 将 $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

相关文章

  • P3384 【模板】重链剖分/树链剖分 - SGT && 重链剖分
    本题是非常非常非常纯粹的树剖,利用了重链剖分后下标的性质不多说上代码就好了#include<cstdio>#include<vector>#definelllonglongusingnamespacestd;constintN=1e5+5;intn,m,r;llp,a[N],b[N];vector<int>V[N];intfa[N],dep[N],siz[N],hson[N]......
  • P3038 [USACO11DEC] Grass Planting G - 重链剖分
    本题可以说是板题P3384的弱化版,只不过要改的变成了边权边权很好处理,只需要将每个边的边权下放到两端点深度比较深的上面就好了(因为每个点连比它浅的节点必定只有一条边)。那么就将模板改一下就好了代码如下:#include<cstdio>usingnamespacestd;constintN=1e5+5;in......
  • 树链剖分
    树链剖分分为重链剖分和长链剖分重链剖分首先是重链剖分,树链剖分顾名思义是一种将代码大小增加1k树剖成一条条链的方法。定义:重儿子该节点所有儿子中以该儿子为根的子树最大的儿子重边连接该节点与该节点的重儿子的那条边重链由根节点或一个轻儿子为链头一路重边连到叶......
  • 树链剖分
    看逆天算法,品百味OI#41.重链剖分给出如下定义:重子结点:一个点的子节点中子树最大的点轻子节点:剩余的子节点重边:该节点到重子节点的边轻边:到轻子节点的边重链:若干条首尾相接的重边预处理由两个DFS实现DFS1:记录节点的父节点、深度、子树大小、重子结点DFS......
  • 重链剖分
    重链剖分优先走重儿子,路径跳不超过\(O(\logn)\)intsiz[N],fa[N],dep[N],top[N],dfn[N],hson[N],dfc;//注意每个都要处理voiddfs1(intx,intFa){ fa[x]=Fa; siz[x]=1; hson[x]=0; for(inti=h[x];i;i=e[i].ne){ inty=e[i].to; if(y==Fa)continue; dep[y]=dep[......
  • 树链剖分学习笔记
    树链剖分,计算机术语,指一种对树进行划分的算法,它先通过轻重边剖分将树分为多条链,保证每个点属于且只属于一条链,然后再通过数据结构(树状数组、BST、SPLAY、线段树等)来维护每一条链。——百度百科重链剖分概念1重儿子一个父节点的所有儿子中,子树节点最大(siz最大)的节点。记......
  • 链剖分
    重链剖分第一次DFS求重儿子(子节点更多的儿子)。第二次DFS求重链剖分(先访问重儿子再访问其他轻儿子)。变量:重儿子,子树大小,DFS序(\(x\)根子树DFS序中第一次出现位置),以\(x\)为根的子树的最后一次出现位置,深度,\(x\)所在重链的顶端。voiddfs1(intx){//求出重儿子,sz[v]......
  • 树链剖分
    son[x]表示节点\(x\)的重儿子,若为\(0\),则说明\(x\)为叶子节点id[x]表示节点\(x\)的dfs序编号f[x]表示节点\(x\)的父节点dep[x]表示节点\(x\)的深度sz[x]表示节点为\(x\)的子树的大小top[x]表示x所在重链顶部的节点函数原型voiddfs1(llu,llfa)功能:计算dep[]、f[]、sz[]和......
  • 【动态规划】长链剖分优化树形 dp
    我们在树形dp中经常会遇到这样一个模型:设\(f_{x,i}\)表示节点\(x\)的子树中深度为\(x\)的答案...有递推式:\(f_{x,i}=\sum_{son}f_{son,i-1/i+1}\dots\)。这样直接做是\(\Theta(n^2)\)的,我们考虑去优化这个dp。有一个小优化,就是我们想让\(f_x\)直接继承......
  • 【树链剖分】P3401 洛谷树 题解
    P3401考虑先将路径权值进行转化,因为很难对路径直接进行统计。考虑如何表示出这条路径的权值。记\(s_i=\oplus_{j\in\text{path}(1,i)}w_j\),其中\(\text{path}(i,j)\)表示\(i\)到\(j\)的路径上的边集。则\(u\tov\)的路径的权值为\(s_u\opluss_v\)。现在转变为......