线段树合并例题

https://www.luogu.com.cn/problem/P3224

1. 永无乡

题意：

 给 n 个岛屿，每个岛有一个标号，初始修有 m 条路，有两个操作，操作1 为 给两个岛屿之间修路，操作2为求出 所有能从当前岛屿到达的岛 中标号第k小的岛

思路：

求标号第k小的岛，我们考虑使用权值线段树，通过线段树上二分查找第k小，对于多个岛屿，我们考虑动态开点建 n 棵线段树，对于岛屿修路的操作 使用并查集维护连通块，并利用线段树合并实现岛屿合并

代码：

#include<bits/stdc++.h>
using namespace std;#define int long long
#define mid ((l+r)>>1)const int N=1e5+5;
int rt[N],n,m,num,id[N],f[N];
int ls[60*N],rs[60*N],cnt[60*N];int find(int x){return x==f[x]?x:f[x]=find(f[x]);}int merge(int x,int y,int l,int r){        //线段树合并if(!x)return y;if(!y)return x;if(l==r){cnt[x]+=cnt[y];return x;}ls[x]=merge(ls[x],ls[y],l,mid);rs[x]=merge(rs[x],rs[y],mid+1,r);cnt[x]=cnt[ls[x]]+cnt[rs[x]];return x;
}void upd(int &p,int l,int r,int x){    //建树if(!p)p=++num;if(l==r){cnt[p]=1;return;}if(x<=mid)upd(ls[p],l,mid,x);else upd(rs[p],mid+1,r,x);cnt[p]=cnt[ls[p]]+cnt[rs[p]];
}int q(int p,int l,int r,int k){    //二分查找第k小if(cnt[p]<k)return -1;if(l==r)return l;if(cnt[ls[p]]>=k)return q(ls[p],l,mid,k);return q(rs[p],mid+1,r,k-cnt[ls[p]]);
}void solve(){cin>>n>>m;for(int i=1;i<=n;i++){int x;cin>>x;id[x]=i;upd(rt[i],1,n,x);f[i]=i;}while(m--){int u,v;cin>>u>>v;if(find(u)==find(v))continue;u=find(u),v=find(v);rt[u]=merge(rt[u],rt[v],1,n);f[v]=u;}cin>>m;while(m--){string op;int x,y;cin>>op>>x>>y;if(op=="B"){if(find(x)==find(y))continue;x=find(x),y=find(y);rt[x]=merge(rt[x],rt[y],1,n);f[y]=x;}else{x=find(x);int ans=q(rt[x],1,n,y);if(ans!=-1)ans=id[ans];cout<<ans<<endl;}}return;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;//cin>>T;while(T--){solve();}return 0;
}

---

2. 雨天的尾巴

https://www.luogu.com.cn/problem/P4556

题意：

给一棵树型村庄，每次给 x到y路径上的村庄发一袋 z 粮食  ，求最后 每个村庄拥有数量最多的粮食种类

思路：

将树看成有根树，取1作为根，每次发放粮食的操作 利用树上差分转化为4次单点发放粮食，直接修改即可，查询数量最多的粮食种类，我们采用 权值线段树 维护每种粮食的数量，建n棵线段树，最后通过 线段树合并+dfs 求出线段树的树上前缀和

代码：

#include<bits/stdc++.h>
using namespace std;#define int long longconst int N=1e5+5;
int head[N],cntt=0;        //建图
struct Edge{int to,next;
}edge[2*N];
void add(int u,int v){edge[++cntt].to=v;edge[cntt].next=head[u];head[u]=cntt;
}int f[N][30],dis[N],n,t;
void init(){                //lcaqueue<int>q;q.push(1);dis[1]=1;while(!q.empty()){int tmp=q.front();q.pop();for(int i=head[tmp];i;i=edge[i].next){int y=edge[i].to;if(dis[y])continue;dis[y]=dis[tmp]+1;f[y][0]=tmp;q.push(y);for(int j=1;j<=t;j++){f[y][j]=f[f[y][j-1]][j-1];}}}
}
int lca(int u,int v){if(dis[u]>dis[v])swap(u,v);for(int i=t;i>=0;i--){if(dis[f[v][i]]>=dis[u])v=f[v][i];}if(u==v)return u;for(int i=t;i>=0;i--){if(f[u][i]!=f[v][i]){u=f[u][i],v=f[v][i];}}return f[u][0];
}#define mid ((l+r)>>1)int X[N],Y[N],Z[N],rt[N],num=0;
int ls[60*N],rs[60*N],cnt[60*N],pos[60*N];void pushup(int p){if(cnt[ls[p]]>cnt[rs[p]]){cnt[p]=cnt[ls[p]];pos[p]=pos[ls[p]];}else if(cnt[rs[p]]>cnt[ls[p]]){cnt[p]=cnt[rs[p]];pos[p]=pos[rs[p]];}else{cnt[p]=cnt[ls[p]];pos[p]=min(pos[ls[p]],pos[rs[p]]);}
}void upd(int &p,int l,int r,int x,int k){if(!p)p=++num;if(l==r){cnt[p]+=k;pos[p]=l;return;}if(x<=mid)upd(ls[p],l,mid,x,k);else upd(rs[p],mid+1,r,x,k);pushup(p);
}int merge(int x,int y,int l,int r){if(!x)return y;if(!y)return x;if(l==r){cnt[x]+=cnt[y];pos[x]=l;return x;}ls[x]=merge(ls[x],ls[y],l,mid);rs[x]=merge(rs[x],rs[y],mid+1,r);pushup(x);return x;
}int ans[N],mx;
void dfs(int x,int ff){for(int i=head[x];i;i=edge[i].next){int y=edge[i].to;if(y==ff)continue;dfs(y,x);rt[x]=merge(rt[x],rt[y],1,mx);}if(cnt[rt[x]])ans[x]=pos[rt[x]];
}void solve(){int m;cin>>n>>m;t=log2(n);for(int i=1;i<n;i++){int u,v;cin>>u>>v;add(u,v);add(v,u);}init();for(int i=1;i<=m;i++){cin>>X[i]>>Y[i]>>Z[i];mx=max(mx,Z[i]);}for(int i=1;i<=m;i++){upd(rt[X[i]],1,mx,Z[i],1);upd(rt[Y[i]],1,mx,Z[i],1);upd(rt[lca(X[i],Y[i])],1,mx,Z[i],-1);if(f[lca(X[i],Y[i])][0])upd(rt[f[lca(X[i],Y[i])][0]],1,mx,Z[i],-1);}dfs(1,1);for(int i=1;i<=n;i++){cout<<ans[i]<<endl;}return;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;while(T--){solve();}return 0;
}