首页 > 其他分享 >【线段树合并/树上差分】[P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并

【线段树合并/树上差分】[P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并

时间:2024-08-09 11:07:13浏览次数:17  
标签:int P4556 线段 合并 pos tr root Sum pst

【线段树合并/树上差分】P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并

思路

对 \(x,y,lca(u,v),fa_{lca(u,v)}\) 四个点进行树上差分,然后用线段树合并动态权值线段树。

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

template<class Node>
struct PersidentSegmentTree {
#define lc(u) tr[u].l
#define rc(u) tr[u].r
    const int n;
    int tot = 0;
    vector<Node> tr;
    vector<int> root;

    PersidentSegmentTree(): n(0) {}

    PersidentSegmentTree(int n_): n(n_) {
        int N = (n << 6) + 10;
        tr.reserve(N); root.reserve(N);
        tr.resize(N); root.resize(N);
    }

    PersidentSegmentTree(vector<int>& a): PersidentSegmentTree(a.size() - 1) {
        function<void(int&, int, int)> build = [&](int& now, int l, int r) {
            now = ++ tot;
            if (l == r) {
                return ;
            }
            int m = (l + r) >> 1;
            build(lc(now), l, m);
            build(rc(now), m + 1, r);
        };
        build(root[0], 1, n);
    }

    //上传
    void pushup(int u) {
        if (tr[lc(u)].Sum >= tr[rc(u)].Sum) {
            tr[u].Sum = tr[lc(u)].Sum;
            tr[u].pos = tr[lc(u)].pos;
        } else {
            tr[u].Sum = tr[rc(u)].Sum;
            tr[u].pos = tr[rc(u)].pos;
        }
    }

    //动态开点/更新树结点
    void insert(int& now, int l, int r, int pos, int w) {
        if (!now)
            now = ++ tot;

        if (l == r) {
            tr[now].Sum += w;
            tr[now].pos = pos;
            return;
        }

        int m = l + r >> 1;
        if (pos <= m)
            insert(lc(now), l, m, pos, w);
        else
            insert(rc(now), m + 1, r, pos, w);
        pushup(now);
    }

    //开新前缀树,last代表前缀,now代表新树根
    void insert(int& now, int last, int l, int r, int pos, int w) {
        now = ++ tot;
        tr[now] = tr[last];
        if (l == r) {
            return;
        }
        int m = l + r >> 1;
        if (pos <= m)
            insert(lc(now), lc(last), l, m, pos, w);
        else
            insert(rc(now), rc(last), m + 1, r, pos, w);
    }

    //单点
    int query(int now, int l, int r, int pos) {
        if (l == r) {
            return tr[now].Sum;
        }

        int m = l + r >> 1;
        if (pos <= m)
            return query(lc(now), l, m, pos);
        else
            return query(rc(now), m + 1, r, pos);
    }

    //区间查询 [u,v]->[root[l-1],root[r]]
    int query(int u, int v, int l, int r, int pos) {
        if (l == r) {
            return tr[u].Sum;
        }

        int m = l + r >> 1;
        if (pos <= m)
            return query(lc(u), lc(v), l, m, pos);
        else
            return query(rc(u), rc(v), m + 1, r, pos);
    }

    void merge(int &u, int v, int l, int r) {
        if (!u || !v) {
            u = u + v;
            return;
        }

        if (l == r) {
            tr[u].Sum += tr[v].Sum;
            return ;
        }

        int m = l + r >> 1;
        merge(lc(u), lc(v), l, m);
        merge(rc(u), rc(v), m + 1, r);
        pushup(u);
    }
};

struct Node {
    int l, r;
    int Sum = 0, pos = 0;
};

constexpr int N = 1e5 + 10, M = N - 10, logn = 20;
PersidentSegmentTree<Node> pst(N);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector g(n + 1, vector<int>());
    for (int i = 1; i < n; i ++) {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    vector dep(n + 1, 0);
    vector f(n + 1, vector<int>(logn + 1));

    auto dfs = [&](auto && self, int u, int fa)->void{
        f[u][0] = fa;
        dep[u] = dep[fa] + 1;
        for (int i = 1; i <= logn; i ++) {
            f[u][i] = f[f[u][i - 1]][i - 1];
        }
        for (auto v : g[u]) {
            if (v == fa)continue;
            self(self, v, u);
        }
    };

    dfs(dfs, 1, 0);

    auto lca = [&](int u, int v)->int{
        if (dep[u] < dep[v])
            swap(u, v);

        for (int i = logn; i >= 0 ; i --) {
            if (dep[f[u][i]] >= dep[v]) {
                u = f[u][i];
            }
        }

        if (u == v)
            return u;

        for (int i = logn; i >= 0; i --) {
            if (f[u][i] != f[v][i]) {
                u = f[u][i], v = f[v][i];
            }
        }

        return f[u][0];
    };

    while (m --) {
        int x, y, z;
        cin >> x >> y >> z;
        int k = lca(x, y);
        pst.insert(pst.root[x], 1, M, z, 1);
        pst.insert(pst.root[y], 1, M, z, 1);
        pst.insert(pst.root[k], 1, M, z, -1);
        pst.insert(pst.root[f[k][0]], 1, M, z, -1);
    }

    vector<int> ans(n + 1);
    auto calc = [&](auto && self, int u, int fa)->void{
        for (auto v : g[u]) {
            if (v == fa) continue;
            self(self, v, u);
            pst.merge(pst.root[u], pst.root[v], 1, M);
        }
        ans[u] = pst.tr[pst.root[u]].pos;
        if (!pst.tr[pst.root[u]].Sum) ans[u] = 0;
    };

    calc(calc, 1, 0);

    for (int i = 1; i <= n; i ++)
        cout << ans[i] << "\n";

    return 0;
}

标签:int,P4556,线段,合并,pos,tr,root,Sum,pst
From: https://www.cnblogs.com/Kescholar/p/18350411

相关文章

  • 线段树合并模板
    template<classNode>structPersidentSegmentTree{#definelc(u)tr[u].l#definerc(u)tr[u].rconstintn;inttot=0;vector<Node>tr;vector<int>root;PersidentSegmentTree():n(0){}PersidentSegmentTree(in......
  • 将二维数组与一维数组合并
    我目前np.append与两个数组组合,但它不能工作,它显示:ValueError:alltheinputarraydimensionsexceptfortheconcatenationaxismustmatchexactly,butalongdimension0,thearrayatindex0hassize64andthearrayatindex1hassize0这是我的......
  • Git合并之————指定提交记录合并
    应用场景在测试环境提交了多个功能代码,其中一个功能需要提前上线如图所示,红框部分为我本次需要上线的功能提交记录代码,绿框部分为我已选择上线成功,可以看到红框与绿框直接的内容并没有被带入master分支.这里我以IDEA为例.首先,切换到master分支,也就是你需要......
  • 【题解】Solution Set - NOIP2024集训Day2 线段树
    【题解】SolutionSet-NOIP2024集训Day2线段树https://www.becoder.com.cn/contest/5431「CF1149C」TreeGenerator™结论:对于括号序列的一个子段,删去所有的匹配括号之后,剩下的不匹配的括号,按顺序构成树上的一条路径。Why?从括号序列的构造出发。每次(相当于开始遍历......
  • P3834 【模板】可持久化线段树 2
    P3834【模板】可持久化线段树2-洛谷|计算机科学教育新生态(luogu.com.cn)#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;template<classNode>structPersidentSegmentTree{#definelc(u)tr[u].l#definerc(u)tr[u].r#definesum(u)t......
  • 洛谷P3842 线段——题解
    洛谷P3842题解传送锚点摸鱼环节[TJOI2007]线段题目描述在一个\(n\timesn\)的平面上,在每一行中有一条线段,第\(i\)行的线段的左端点是\((i,L_{i})\),右端点是\((i,R_{i})\)。你从\((1,1)\)点出发,要求沿途走过所有的线段,最终到达\((n,n)\)点,且所走的路程长度要尽......
  • 涨冷门知识之CSS魔法:边距合并
    后端同学问了一个问题:“为什么背景色没有充满?”F12,inspect,哎嗨,p标签存在默认边距源码如下:点击查看代码<!DOCTYPEhtml><htmllang="zh-CN"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,i......
  • 数据结构——线段树优化 学习笔记
    数据结构——线段树优化学习笔记比较基础,因此讲的很快。我们主要关注单点修改、区间查询的线段树,这是应用最广泛的。线段树问题我们以LOJ的这道题为例,例题:LOJ#130.树状数组1:单点修改,区间查询。洛谷上面也有类似的题:P3374【模板】树状数组1。因为洛谷的题的数据范......
  • 数据结构——线段树提高 学习笔记
    数据结构——线段树提高学习笔记一些比较系统的东西,会单独放文章,这里只写一些理论的。线段树维护矩阵例题:P7453[THUSCH2017]大魔法师。当区间信息比较复杂,但是满足结合律的时候,可以使用矩阵维护。线段树每个节点维护一个矩阵,合并区间时使用矩阵乘法转移。但是,矩阵乘法的......
  • freemarker实现动态行单元格合并
    原文链接:https://www.cnblogs.com/10158wsj/p/11211471.htmlhttps://blog.csdn.net/weixin_43667830/article/details/106936546项目需求:项目中有个需求,需要将一些数据库中的数据根据需求导出,生成一个word,研究了一些技术,其中包括POI、freemaker,对比了一下实现过程及技术难度没......