首页 > 其他分享 >线段树合并

线段树合并

时间：2024-01-24 22:44:58浏览次数：31  
标签：p2 p1 int 合并 线段 tree rch lch

线段树合并

线段树合并可以使很多跑不过的暴力，特别是树上暴力的时间复杂度正确，与树分治的区别在于，线段树合并必须依次处理节点，但优势在于，保持了树的形态。

算法思路

引入

CF600E Lomsat gelral

使用一个数组记录该子树内的颜色出现次数。

每次每个节点暴力将儿子的信息合并到自己的数组上，因而求出答案。

显然这样的操作，空间和时间都不允许，我们需要效率更高的方式。

过程

线段树合并会将两颗形态相同的线段树的对应信息合并为一棵线段树。

我们考虑先每个节点开一棵动态开点的线段树，存下颜色出现次数，记录颜色区间的最大值和最大颜色编号和。

然后进行线段树合并，这个过程本质上非常暴力。

设两颗线段树为 A 树和 B 树。

从 1 号节点开始，遍历 A 树和 B 树中线段树的对应节点。

递归到某个节点时，如果 A 树中该节点为空，或者 B 树中该节点为空，直接返回另一棵树上的节点。

递归到线段树叶子节点时，区间大小为 1，看做两个元素合并值。

根据儿子节点求出当前节点状态。

void merge(int &p1,int p2,int l,int r)
{
    if(!p1||!p2) {p1=p1+p2;return ;}
    if(l==r) {/*do something*/;return ;}
    int mid=(l+r)>>1;
    push_down(p1);
    push_down(p2);//下传懒标记
    merge(tree[p1].lch,tree[p2].lch,l,mid);
    merge(tree[p1].rch,tree[p2].rch,mid+1,r);
    updata(p1);//根据儿子从新求值
}

这里 \(p1\) 直接引用回传了更改后节点对应的编号。

回到引入的题目，该题的合并直接将同一颜色对应节点的值求和即可。

时间复杂度

在树上的合并，时间复杂度在 \(O(n\log n)\)，因为每一次合并的花费相当于 \(O(重复节点个数)\)，然而每一条路径只有可能是原树中一个节点更新的，所以每条路径合并一次就相当于将原树中两个节点变为一个。

其他情况下，可以使用类似的方式分析时间复杂度，主要从一条路径合并在原情况中的变化展开讨论。

引入代码

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define lch(p) tree[p].lch
#define rch(p) tree[p].rch

const int maxn=1e5+5;

struct linetree
{
    int tot;
    struct treenode{int lch,rch,sum,res;}tree[maxn*30];
    void updata(int p)
    {
        if(tree[lch(p)].sum>tree[rch(p)].sum) tree[p].sum=tree[lch(p)].sum,tree[p].res=tree[lch(p)].res;
        else if(tree[lch(p)].sum<tree[rch(p)].sum) tree[p].sum=tree[rch(p)].sum,tree[p].res=tree[rch(p)].res;
        else tree[p].sum=tree[lch(p)].sum,tree[p].res=tree[lch(p)].res+tree[rch(p)].res;
    }
    void insert(int &p,int l,int r,int co,int val)
    {
        if(l>co||r<co) return ;
        if(!p) p=++tot;
        if(l==r)
        {
            tree[p].sum+=val;
            tree[p].res=co;
            return ;
        }
        int mid=(l+r)>>1;
        insert(lch(p),l,mid,co,val);
        insert(rch(p),mid+1,r,co,val);
        updata(p);
    }
    void merge(int &p1,int p2,int l,int r)
    {
        if(!p1||!p2) {p1=p1+p2;return ;}
        if(l==r) {tree[p1].sum+=tree[p2].sum;return ;}
        int mid=(l+r)>>1;
        merge(lch(p1),lch(p2),l,mid);
        merge(rch(p1),rch(p2),mid+1,r);
        updata(p1);
    }
}T;
struct Edge
{
    int tot;
    int head[maxn];
    struct edgenode{int to,nxt;}edge[maxn*2];
    void add(int x,int y)
    {
        tot++;
        edge[tot].to=y;
        edge[tot].nxt=head[x];
        head[x]=tot;
    }
}E;

int n;
int c[maxn],rt[maxn],ans[maxn];

void dfs(int u,int f)
{
    for(int i=E.head[u];i;i=E.edge[i].nxt)
    {
        int v=E.edge[i].to;
        if(v==f) continue;
        dfs(v,u);
        T.merge(rt[u],rt[v],1,n);
    }
    ans[u]=T.tree[rt[u]].res;
}

signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%lld",&x);
        T.insert(rt[i],1,n,x,1);
    }
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%lld%lld",&u,&v);
        E.add(u,v);
        E.add(v,u);
    }

    dfs(1,0);
    for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
}

例题

例一 P4556 Vani有约会 雨天的尾巴 /【模板】线段树合并

使用树上差分，将一段路径的加操作看做四个单点修改，线段树维护每个点的救济粮种类个数，儿子向父亲合并自己的线段树即可。

#include<bits/stdc++.h>
using namespace std;

#define inf 2e5

const int maxn=5e5+5;

struct linetree
{
    int tot;
    struct treenode{int sum,res,lch,rch;}tree[maxn*20];
    void updata(int p)
    {
        int lch=tree[p].lch,rch=tree[p].rch;
        if(tree[lch].sum<tree[rch].sum) tree[p].res=tree[rch].res,tree[p].sum=tree[rch].sum;
        else tree[p].res=tree[lch].res,tree[p].sum=tree[lch].sum;
    }
    void insert(int &p,int l,int r,int co,int val)
    {
        if(r<co||l>co) return ;
        if(!p) p=++tot;
        if(l==r)
        {
            tree[p].sum+=val;
            tree[p].res=co;
            return ;
        }
        int mid=(l+r)>>1;
        insert(tree[p].lch,l,mid,co,val);
        insert(tree[p].rch,mid+1,r,co,val);
        updata(p);
    }
    void merge(int &p1,int p2,int l,int r)
    {
        if(!p1||!p2) {p1=p1+p2;return ;}
        if(l==r) {tree[p1].sum+=tree[p2].sum;return ;}
        int mid=(l+r)>>1;
        merge(tree[p1].lch,tree[p2].lch,l,mid);
        merge(tree[p1].rch,tree[p2].rch,mid+1,r);
        updata(p1);
    }
}T;
struct Edge
{
    int tot;
    int head[maxn];
    struct edgenode{int to,nxt;}edge[maxn*2];
    void add(int x,int y)
    {
        tot++;
        edge[tot].to=y;
        edge[tot].nxt=head[x];
        head[x]=tot;
    }
}E;

int n,m;
int f[maxn][25],deep[maxn],rt[maxn],ans[maxn];

void dfs(int u)
{
    for(int i=E.head[u];i;i=E.edge[i].nxt)
    {
        int v=E.edge[i].to;
        if(deep[v]) continue;
        deep[v]=deep[u]+1;
        f[v][0]=u;
        for(int j=1;j<=20;j++) f[v][j]=f[f[v][j-1]][j-1];
        dfs(v);
    }
}
int Lca(int x,int y)
{
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=20;i>=0;i--) if(deep[f[x][i]]>=deep[y]) x=f[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
void gtans(int u)
{
    for(int i=E.head[u];i;i=E.edge[i].nxt)
    {
        int v=E.edge[i].to;
        if(v==f[u][0]) continue;
        gtans(v);
        T.merge(rt[u],rt[v],1,inf);
    }
    ans[u]=T.tree[rt[u]].res;
    if(T.tree[rt[u]].sum==0) ans[u]=0;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        E.add(u,v);
        E.add(v,u);
    }

    deep[1]=1;
    dfs(1);

    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        T.insert(rt[x],1,inf,z,1);
        T.insert(rt[y],1,inf,z,1);
        int lca=Lca(x,y);
        T.insert(rt[lca],1,inf,z,-1);
        if(f[lca][0]) T.insert(rt[f[lca][0]],1,inf,z,-1);
    }
    gtans(1);
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
}

例二 P3224 HNOI2012 永无乡

使用并查集，每个并查集的根处建立一棵权值线段树，区间表示排名在这个区间内的点的个数，每次加边使用并查集判断，执行线段树合并，查询直接查。

#include<bits/stdc++.h>
using namespace std;

#define lch(p) tree[p].lch
#define rch(p) tree[p].rch

const int maxn=2e5+5;

int p[maxn],fp[maxn];

struct linetree
{
    int tot;
    struct treenode{int lch,rch,sum;}tree[maxn*30];
    void updata(int p)
    {
        tree[p].sum=tree[lch(p)].sum+tree[rch(p)].sum;
    }
    void insert(int &p,int l,int r,int x,int val)
    {
        if(l>x||r<x) return ;
        if(!p) p=++tot;
        if(l==r)
        {
            tree[p].sum+=val;
            return ;
        }
        int mid=(l+r)>>1;
        insert(lch(p),l,mid,x,val);
        insert(rch(p),mid+1,r,x,val);
        updata(p);
    }
    int fd(int p,int l,int r,int k)
    {
        int mid=(l+r)>>1;
        if(tree[p].sum<k) return -1;
        if(l==r) return fp[l];
        if(tree[lch(p)].sum>=k) return fd(lch(p),l,mid,k);
        return fd(rch(p),mid+1,r,k-tree[lch(p)].sum);
    }
    void merge(int &p1,int p2,int l,int r)
    {
        int mid=(l+r)>>1;
        if(!p1||!p2){p1=p1+p2;return;}
        if(l==r){tree[p1].sum+=tree[p2].sum;return ;}
        merge(lch(p1),lch(p2),l,mid);
        merge(rch(p1),rch(p2),mid+1,r);
        updata(p1);
    }
}T;

int n,m;
int rt[maxn],f[maxn];

int fr(int u){return f[u]==u?u:f[u]=fr(f[u]);}
void link(int u,int v)
{
    int fu=fr(u),fv=fr(v);
    if(fu==fv) return ;
    T.merge(rt[fu],rt[fv],1,n);
    f[fv]=fu;
}
void query(int u,int k)
{
    int fu=fr(u);
    printf("%d\n",T.fd(rt[fu],1,n,k));
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&p[i]);
        fp[p[i]]=i;
        T.insert(rt[i],1,n,p[i],1);
    }
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        link(u,v);
    }
    int q;
    scanf("%d",&q);
    while(q--)
    {
        char op;
        int x,y;
        cin>>op;
        scanf("%d%d",&x,&y);
        if(op=='B') link(x,y);
        else query(x,y);
    }
}

例三 P7563 JOISC 2021 Day (4Worst Reporter 4)

很好的线段树合并+树上 dp 的题目。

做出这道题你会对线段树合并有更多启发。

P7563 JOISC 2021 Day4 最悪の記者 4 (Worst Reporter 4) 题解

推荐练习

P3605 USACO17JAN Promotion Counting P

P8844 传智杯 #4 初赛 小卡与落叶

P8959 「CGOI-3」灵气

标签：p2,p1,int,合并,线段,tree,rch,lch
From： https://www.cnblogs.com/binbinbjl/p/17986021

相关文章

  • Ybt 金牌导航 6.1.H. 时空旅行 / P5416 [CTSC2016] 时空旅行（线段树分治+凸包）
    题意简述初始有版本\(0\)，其中仅包含点\(0\)，且\(c_0\)给出，\(x_0=0\)。对于第\(i\)个版本，它依赖第\(fr_i\)个版本，而且会在父级版本的基础上进行以下两种操作之一：插入一个新点，并且会给出\(x_i\)和\(c_i\)。删除一个本就存在的点（不为\(0\)）给出\(m\)次询问，每次给出......
  • (19)Powershell字符串合并运算符
    (19)Powershell字符串合并运算符Powershell提供了对字符串的合并运算符，连接运算符-join将一组字符串连接成单个字符串，子字符串按其在命令中出现的顺序添加到生成的字符串中。连接运算符Powershell中字符串的连接运算符的语法如下：-Join<String[]><String[]>-Join参数......
  • 优美的暴力——树上启发式合并（dsu on tree）
    dsuontree前言在我认为，这个并不能说单独列出来成为一个算法，更恰当的说，是一种思想、技巧。反正挺简单的，也很有趣（谁会拒绝一个优美的暴力呢），所以写篇笔记记录一手。dsu是什么dsu一般指“disjointsetunion”，即并查集。那么dsuontree也就是指树上的合并和查询操作。但是......
  • java8找出两个集合List<Employee> 中 id相同的元素，再将别的属性合并，放在新的集合里面
    可以使用Java8的StreamAPI来实现这个需求。具体步骤如下：1.创建一个新的集合，用于存放合并后的元素。2.使用Stream的filter()方法过滤出id相同的元素。3.使用Stream的map()方法将id相同的元素合并成一个新的元素，其中别的属性可以通过自定义的合并规则来实现。4.使用Stream的c......
  • 主席树（可持久化线段树）
    主席树前言主席树也是一种数据结构，是线段树的进阶，作用是可以保留历史版本，支持回退，就是回到之前某个未修改的状态。就像我们在写博客时如果误删了重要的内容，就可以用Ctrl+z撤回一次操作，也可以用Ctrl+Shift+z还原我们撤回的操作，这就需要存下每次编辑的操作。基本原理可......
  • laravel collect结果集group分组合并数据
    1、需求将相同apply_id的apply_remark用;拼接$r=[['apply_id'=>1,'apply_remark'=>'xxx'],['apply_id'=>1,'apply_remark'=>'xxx2'],['apply_id'=>2......
  • 「笔记」李超线段树
    目录写在前面引入线段区间修改单点查询完整代码例题P4254[JSOI2008]BlueMary开公司P3081[USACO13MAR]HillWalkG写在最后写在前面LiChaoTree也是LCT（智将和典中典之楼房重建都是\(O(\log^2n)\)地进行修改的样子，但是楼房重建是拆分完区间后再\(O(\log^2n)\)地向上......
  • 数据库重构(一）：字段合并
    刚到公司不久，才知道公司产品在性能上有问题，数据量和并发数一大，系统就很慢，需要优化。在和公司技术同事讨论某模块优化，通过sql无法优化，因为系统sql是判断5个纬度，一个用户id,一个机构id，一个岗位id,还有级别判断和是否公共。     刚到公司不久，才知道公......
  • 线段树二分
    问题描述维护长度为\(n\)的序列\(a\)，支持以下操作：1ix：把\(a_i\)修改为\(x\)。2ix：询问最小的\(j\)满足\(j>=i\)且\(a_j>=x\)。\(1\leqn\leq10^6\)解决方法在线段树外直接二分可以做到\(O(n\log^2n)\)的时间复杂度，加上简单的剪枝可能效率会高一些，但都无......
  • Ybt 金牌导航 6.1.F 大根堆 / BZOJ 4919 大根堆（LIS，启发式合并）
    题意简述有一个以\(1\)为根的有根树，每个点有权值\(v_i\)。你需要选出一个点集\(S\)，使得点集里任意两个元素\(x,y\)，若\(x\)在原树上是\(y\)的祖先，则要满足\(v_x>v_y\)。求选出的点集的最大大小是多少。解法原题限制相当于：在选出的点集构成的新树\(T\)中，每个点到根节......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99