前置知识:
倍增LCA

树上差分

可持久化线段树(动态开点)

定义:

线段树合并就是合并值域相同的线段树。

线段树合并

 

非常的好理解。Code:

 1 int merge(int p,int q,int l,int r){//在这里,我们选择将两棵树合并到第一棵树中
 2     if(!q) return p;
 3     if(!p) return q;//因为使用动态开点线段树,所以当其中一棵线段树无该节点是便可停止
 4     if(l==r){
 5         t[p].maxn+=t[q].maxn;
 6         if(t[p].maxn>0) t[p].pos=l;
 7         else t[p].pos=0;
 8         return p;
 9     }
10     int mid=(l+r)/2;
11     t[p].l=merge(t[p].l,t[q].l,l,mid);
12     t[p].r=merge(t[p].r,t[q].r,mid+1,r);
13     pushup(p);
14     return p;
15 }

懂不起?那确实。

让我们来看一道例题来感受线段树合并的用途。

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

思路:

对于每个节点,我们用动态开点线段树来记录每种救济粮的个数。

那这道题和线段树合并有什么关系呢?

要合并,就需要在统计答案时进行“”的操作。

于是我们就想到了差分

树+差分=树上差分

于是思路就出来了:

用树上差分维护n棵线段树,统计答案时利用线段树合并完成。

详细思路在代码中解释:

 

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int N=1e5+5;
  4 const int M=6e6+5; 
  5 int n,m; 
  6 int a,b;
  7 int x,y,z;
  8 int T;
  9 int idx=0,tot=0;
 10 int f[N][30],d[N],root[N],head[N];
 11 int ans[N];
 12 struct node{
 13     int v,next;
 14 }s[2*N];
 15 struct node1{
 16     int l,r,maxn,pos;
 17     //maxn用于记录该区间最多的饲料数
 18     //pos用于记录该区间最多的饲料的种类 
 19 }t[M];
 20 
 21 void build(int a,int b){//建图 
 22     s[++idx].v=b;
 23     s[idx].next=head[a];
 24     head[a]=idx;
 25 }
 26 
 27 void bfs(){//倍增求LCA的预处理 
 28     memset(d,0,sizeof(d));
 29     d[1]=1;
 30     queue<int> q;
 31     q.push(1);
 32     while(!q.empty()){
 33         int x=q.front();
 34         q.pop();
 35         for(int i=head[x];i;i=s[i].next){
 36             int y=s[i].v;
 37             if(d[y]) continue;
 38             d[y]=d[x]+1;
 39             f[y][0]=x;
 40             for(int i=1;i<=T;i++) f[y][i]=f[f[y][i-1]][i-1];
 41             q.push(y); 
 42         }
 43     }
 44     return ;
 45 }
 46 
 47 int LCA(int x,int y){//求LCA 
 48     if(d[x]<d[y]) swap(x,y);
 49     for(int i=T;i>=0;i--){
 50         if(d[f[x][i]]>=d[y]) x=f[x][i];
 51     }
 52     if(x==y) return x;
 53     for(int i=T;i>=0;i--){
 54         if(f[x][i]!=f[y][i]){
 55             x=f[x][i];
 56             y=f[y][i];
 57         }
 58     }
 59     return f[x][0];
 60 }
 61 
 62 int Build(){//动态开点 
 63     tot++;
 64     t[tot].l=t[tot].r=t[tot].maxn=t[tot].pos=0;
 65     return tot;
 66 }
 67 
 68 void pushup(int p){//更新最大饲料数量及种类 
 69     if(t[t[p].l].maxn>=t[t[p].r].maxn){//注意:因为数量相同时,编号小的优先,所以是>=而不是> 
 70         t[p].maxn=t[t[p].l].maxn;
 71         t[p].pos=t[t[p].l].pos;
 72     }
 73     else{
 74         t[p].maxn=t[t[p].r].maxn;
 75         t[p].pos=t[t[p].r].pos;
 76     }
 77     return ;
 78 }
 79 
 80 void modify(int p,int l,int r,int x,int v){//单点修改 
 81     if(l==r){//因为用了树上差分,所以区间和可能是负数 
 82         t[p].maxn+=v;
 83         if(t[p].maxn>0) t[p].pos=x;
 84         else t[p].pos=0;
 85         return ;
 86     }
 87     int mid=(l+r)/2;
 88     if(x<=mid){
 89         if(!t[p].l) t[p].l=Build();//记住!动态开点! 
 90         modify(t[p].l,l,mid,x,v);
 91     }
 92     else{
 93         if(!t[p].r) t[p].r=Build();//记住!动态开点!
 94         modify(t[p].r,mid+1,r,x,v);
 95     }
 96     pushup(p);
 97     return ;
 98 }
 99 
100 int merge(int p,int q,int l,int r){//线段树合并 
101     if(!q) return p;
102     if(!p) return q;
103     if(l==r){
104         t[p].maxn+=t[q].maxn;
105         if(t[p].maxn>0) t[p].pos=l;
106         else t[p].pos=0;
107         return p;
108     }
109     int mid=(l+r)/2;
110     t[p].l=merge(t[p].l,t[q].l,l,mid);
111     t[p].r=merge(t[p].r,t[q].r,mid+1,r);
112     pushup(p);
113     return p;
114 }
115 
116 void dfs(int x){
117     if(!root[x]) root[x]=Build();//记住!动态开点!
118     for(int i=head[x];i;i=s[i].next){
119         int y=s[i].v;
120         if(f[x][0]==y) continue; 
121         dfs(y);
122         root[x]=merge(root[x],root[y],1,N);//注意:此处为root[x]而非x是因为对于原树的每一个节点都是线段树的根节点 
123     }
124     ans[x]=t[root[x]].pos;
125     return ;
126 } 
127 
128 int main(){
129     cin>>n>>m;
130     T=(log(n)/log(2))+1;
131     for(int i=1;i<n;i++){
132         cin>>a>>b;
133         build(a,b);
134         build(b,a);
135     }
136     bfs();//预处理 
137     for(int i=1;i<=m;i++){
138         cin>>x>>y>>z;
139         int lc=LCA(x,y);
140         if(!root[x]) root[x]=Build();
141         modify(root[x],1,N,z,1);
142         if(!root[y]) root[y]=Build();
143         modify(root[y],1,N,z,1);
144         if(!root[lc]) root[lc]=Build();
145         modify(root[lc],1,N,z,-1);
146         if(!root[f[lc][0]]) root[f[lc][0]]=Build();
147         modify(root[f[lc][0]],1,N,z,-1);//树上差分 
148     }
149     dfs(1);//答案 
150     for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
151     return 0;
152 } 

 

这样复杂度是多少呢?

由于是动态开点线段树,所以基于总操作数m,每次操作至多新建一条长为log v的链,所以至多只有O(m log v) 的节点。

那么合并时,遍历了线段树中所有已有的节点。

那么这样合并复杂度也是O(mlogv)

 

版权声明:本文为zhangzhiyuan123原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/zhangzhiyuan123/p/14998561.html