免费学习网站建设,深圳刚刚突然宣布,wordpress 伪静态实现,新乐市建设银行网站https://www.luogu.com.cn/problem/P3224
1. 永无乡
题意#xff1a; 给 n 个岛屿#xff0c;每个岛有一个标号#xff0c;初始修有 m 条路#xff0c;有两个操作#xff0c;操作1 为 给两个岛屿之间修路#xff0c;操作2为求出 所有能从当前岛屿到达的岛 中标号第k小的…https://www.luogu.com.cn/problem/P3224
1. 永无乡
题意 给 n 个岛屿每个岛有一个标号初始修有 m 条路有两个操作操作1 为 给两个岛屿之间修路操作2为求出 所有能从当前岛屿到达的岛 中标号第k小的岛
思路
求标号第k小的岛我们考虑使用权值线段树通过线段树上二分查找第k小对于多个岛屿我们考虑动态开点建 n 棵线段树对于岛屿修路的操作 使用并查集维护连通块并利用线段树合并实现岛屿合并
代码
#includebits/stdc.h
using namespace std;#define int long long
#define mid ((lr)1)const int N1e55;
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 xf[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(lr){cnt[x]cnt[y];return x;}ls[x]merge(ls[x],ls[y],l,mid);rs[x]merge(rs[x],rs[y],mid1,r);cnt[x]cnt[ls[x]]cnt[rs[x]];return x;
}void upd(int p,int l,int r,int x){ //建树if(!p)pnum;if(lr){cnt[p]1;return;}if(xmid)upd(ls[p],l,mid,x);else upd(rs[p],mid1,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(lr)return l;if(cnt[ls[p]]k)return q(ls[p],l,mid,k);return q(rs[p],mid1,r,k-cnt[ls[p]]);
}void solve(){cinnm;for(int i1;in;i){int x;cinx;id[x]i;upd(rt[i],1,n,x);f[i]i;}while(m--){int u,v;cinuv;if(find(u)find(v))continue;ufind(u),vfind(v);rt[u]merge(rt[u],rt[v],1,n);f[v]u;}cinm;while(m--){string op;int x,y;cinopxy;if(opB){if(find(x)find(y))continue;xfind(x),yfind(y);rt[x]merge(rt[x],rt[y],1,n);f[y]x;}else{xfind(x);int ansq(rt[x],1,n,y);if(ans!-1)ansid[ans];coutansendl;}}return;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T1;//cinT;while(T--){solve();}return 0;
} 2. 雨天的尾巴
https://www.luogu.com.cn/problem/P4556
题意
给一棵树型村庄每次给 x到y路径上的村庄发一袋 z 粮食 求最后 每个村庄拥有数量最多的粮食种类
思路
将树看成有根树取1作为根每次发放粮食的操作 利用树上差分转化为4次单点发放粮食直接修改即可查询数量最多的粮食种类我们采用 权值线段树 维护每种粮食的数量建n棵线段树最后通过 线段树合并dfs 求出线段树的树上前缀和
代码
#includebits/stdc.h
using namespace std;#define int long longconst int N1e55;
int head[N],cntt0; //建图
struct Edge{int to,next;
}edge[2*N];
void add(int u,int v){edge[cntt].tov;edge[cntt].nexthead[u];head[u]cntt;
}int f[N][30],dis[N],n,t;
void init(){ //lcaqueueintq;q.push(1);dis[1]1;while(!q.empty()){int tmpq.front();q.pop();for(int ihead[tmp];i;iedge[i].next){int yedge[i].to;if(dis[y])continue;dis[y]dis[tmp]1;f[y][0]tmp;q.push(y);for(int j1;jt;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 it;i0;i--){if(dis[f[v][i]]dis[u])vf[v][i];}if(uv)return u;for(int it;i0;i--){if(f[u][i]!f[v][i]){uf[u][i],vf[v][i];}}return f[u][0];
}#define mid ((lr)1)int X[N],Y[N],Z[N],rt[N],num0;
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)pnum;if(lr){cnt[p]k;pos[p]l;return;}if(xmid)upd(ls[p],l,mid,x,k);else upd(rs[p],mid1,r,x,k);pushup(p);
}int merge(int x,int y,int l,int r){if(!x)return y;if(!y)return x;if(lr){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],mid1,r);pushup(x);return x;
}int ans[N],mx;
void dfs(int x,int ff){for(int ihead[x];i;iedge[i].next){int yedge[i].to;if(yff)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;cinnm;tlog2(n);for(int i1;in;i){int u,v;cinuv;add(u,v);add(v,u);}init();for(int i1;im;i){cinX[i]Y[i]Z[i];mxmax(mx,Z[i]);}for(int i1;im;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 i1;in;i){coutans[i]endl;}return;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T1;while(T--){solve();}return 0;
}
