线段树合并例题

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 long

const 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(){                //lca
    queue<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;
}