并不敢说完全会了线段树合并,只是至少知道原理写法了。。。还是太菜了,每天被大佬吊锤 qwq
我看到的几道线段树合并都是权值线段树的合并。这个算法适用范围应该只是 01 线段树的。
这两道算入门题了吧。。。
发现粘题面没人看(自己都懒得看),以后粘链接加题意吧。
给 $n$ 个没有连边的带权点,动态加边,询问 $u$ 所在连通块权值第 $k$ 大的点是什么。$n \leq 1e5 , q\leq 3e5$
给定森林,点有点权有重复!,边有边权。询问 $u$ 所在连通块,只能走边权小于 $w$ 的边,可达的权值第 $k$ 大的点编号!是什么。$n \leq 1e5 , m,q \leq 5e5$ 被坑的巨惨 qwq
后面的离线一下,按边权从小到大加进去就和永无乡一样了。
并查集维护连通性,并将两个连通块的权值线段树合并。询问就是在所在连通块线段树二分找。$(O(nlogn))$
- #include < bits / stdc++.h > using namespace std;
- const int N = 100010;
- inline int read() {
- int r = 0,
- c = getchar();
- while (!isdigit(c)) c = getchar();
- while (isdigit(c)) r = r * 10 + c - '0',
- c = getchar();
- return r;
- }
- int fa[N],
- rt[N],
- n,
- m;
- int find(int x) {
- return x == fa[x] ? x: fa[x] = find(fa[x]);
- }
- struct Node {
- int L,
- R,
- sum;
- }
- T[N * 20];
- int sz;#define ls T[o].L#define rs T[o].R void pullup(int o) {
- T[o].sum = T[ls].sum + T[rs].sum;
- }
- void ins(int & o, int l, int r, int v) {
- if (!o) o = ++sz;
- if (l == r) {
- T[o].sum = 1;
- return;
- }
- int mid = l + r >> 1;
- if (v <= mid) ins(ls, l, mid, v);
- else ins(rs, mid + 1, r, v);
- pullup(o);
- }
- int merge(int x, int y) {
- if (!x) return y;
- if (!y) return x;
- T[x].L = merge(T[x].L, T[y].L);
- T[x].R = merge(T[x].R, T[y].R);
- pullup(x);
- return x;
- }
- int query(int o, int l, int r, int rk) {
- if (l == r) return l;
- int mid = l + r >> 1;
- if (rk <= T[ls].sum) return query(ls, l, mid, rk);
- else return query(rs, mid + 1, r, rk - T[ls].sum);
- }
- void Link(int x, int y) {
- int u = find(x),
- v = find(y);
- fa[u] = v;
- rt[v] = merge(rt[u], rt[v]);
- }
- int a[N],
- id[N];
- void init() {
- n = read(),
- m = read();
- for (int i = 1; i <= n; i++) a[i] = read(),
- id[a[i]] = fa[i] = i;
- while (m--) {
- int u = read(),
- v = read();
- fa[find(u)] = find(v);
- }
- for (int i = 1; i <= n; i++) ins(rt[find(i)], 1, n, a[i]);
- }
- void solve() {
- m = read();
- char s[10];
- while (m--) {
- scanf("%s", s);
- if (s[0] == 'B') {
- int u = read(),
- v = read();
- Link(u, v);
- } else {
- int u = find(read()),
- rk = read();
- if (T[rt[u]].sum < rk) puts("-1");
- else printf("%d\n", id[query(rt[u], 1, n, rk)]);
- }
- }
- }
- int main() {
- init();
- solve();
- }
- #include<bits/stdc++.h>
- using namespace std;
- const int N=200010;
- const int M=500010;
- inline int read(){
- int r=0,c=getchar();
- while(!isdigit(c))c=getchar();
- while(isdigit(c))
- r=r*10+c-'0',c=getchar();
- return r;
- }
- int n,m,q;
- struct Edge{
- int u,v,w;
- friend bool operator < (Edge p,Edge q){
- return p.w<q.w;
- }
- }e[M];
- struct ask{
- int u,w,k,ans,id;
- }a[M];
- bool cmpw(ask p,ask q){
- return p.w<q.w;
- }
- bool cmpid(ask p,ask q){
- return p.id<q.id;
- }
- int fa[N],h[N],t[N],id[N];
- inline int find(int x){
- return x==fa[x]?x:fa[x]=find(fa[x]);
- }
- int rt[N],sz;
- struct Node{
- int L,R,sum;
- }T[N*40];
- #define ls T[o].L
- #define rs T[o].R
- #define mid (l+r>>1)
- inline void pullup(int o){
- T[o].sum=T[ls].sum+T[rs].sum;
- }
- void ins(int &o,int l,int r,int val){
- if(!o)o=++sz;
- if(l==r){
- T[o].sum=1;return;
- }
- if(val<=mid)ins(ls,l,mid,val);
- else ins(rs,mid+1,r,val);
- pullup(o);
- }
- int query(int o,int l,int r,int rk){
- if(l==r){
- return t[l];
- }
- if(rk<=T[ls].sum)return query(ls,l,mid,rk);
- else return query(rs,mid+1,r,rk-T[ls].sum);
- }
- int merge(int x,int y){
- if(!x)return y;
- if(!y)return x;
- if(!T[x].L&&!T[x].R){
- T[x].sum+=T[y].sum;
- return x;
- }
- T[x].L=merge(T[x].L,T[y].L);
- T[x].R=merge(T[x].R,T[y].R);
- pullup(x);return x;
- }
- inline void Link(int x,int y){
- x=find(x),y=find(y);
- if(x==y)return;
- fa[y]=x;
- rt[x]=merge(rt[x],rt[y]);
- }
- void init(){
- n=read(),m=read(),q=read();
- for(int i=1;i<=n;i++)
- h[i]=t[i]=read(),fa[i]=i;
- sort(t+1,t+n+1);
- for(int i=1;i<=n;i++){
- h[i]=lower_bound(t+1,t+n+1,h[i])-t;
- ins(rt[i],1,n,h[i]);
- }
- for(int i=1;i<=m;i++)
- e[i].u=read(),e[i].v=read(),e[i].w=read();
- sort(e+1,e+m+1);
- for(int i=1;i<=q;i++)
- a[i].u=read(),a[i].w=read(),a[i].k=read(),a[i].id=i;
- sort(a+1,a+q+1,cmpw);
- }
- void solve(){
- int now=1;
- for(int i=1;i<=q;i++){
- int lim=a[i].w,rk=a[i].k;
- while(e[now].w<=lim&&now<=m){
- Link(e[now].u,e[now].v);now++;
- }
- int u=find(a[i].u),siz=T[rt[u]].sum;
- if(siz<rk){
- a[i].ans=-1;continue;
- }
- else rk=siz-rk+1;
- a[i].ans=query(rt[u],1,n,rk);
- }
- sort(a+1,a+q+1,cmpid);
- for(int i=1;i<=q;i++)
- printf("%d\n",a[i].ans);
- }
- int main(){
- init();
- solve();
- }
来源: http://www.bubuko.com/infodetail-2438250.html