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

1. 永無鄉(xiāng)

題意：

?給 n 個島嶼，每個島有一個標(biāo)號，初始修有 m 條路，有兩個操作，操作1 為 給兩個島嶼之間修路，操作2為求出 所有能從當(dāng)前島嶼到達(dá)的島 中標(biāo)號第k小的島

思路：

求標(biāo)號第k小的島，我們考慮使用權(quán)值線段樹，通過線段樹上二分查找第k小，對于多個島嶼，我們考慮動態(tài)開點(diǎn)建 n 棵線段樹，對于島嶼修路的操作 使用并查集維護(hù)連通塊，并利用線段樹合并實(shí)現(xià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(tǒng)路徑上的村莊發(fā)一袋 z 糧食??，求最后 每個村莊擁有數(shù)量最多的糧食種類

思路：

將樹看成有根樹，取1作為根，每次發(fā)放糧食的操作?利用樹上差分轉(zhuǎn)化為4次單點(diǎn)發(fā)放糧食，直接修改即可，查詢數(shù)量最多的糧食種類，我們采用 權(quán)值線段樹 維護(hù)每種糧食的數(shù)量，建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;
}