网站地图做关键词排名,厦门网络推广外包,wordpress 分享文章,网站开发项目个人总结正题
题目链接:https://www.luogu.com.cn/problem/P3224 题目大意 nnn个点#xff0c;每次可以连接两个点和询问一个点所在联通块中第kkk大的数。 解题思路
我们发现可以启发式合并#xff0c;对于每个联通块维护一个线段树#xff0c;然后每次合并时将小的暴力丢入大的平…正题
题目链接:https://www.luogu.com.cn/problem/P3224 题目大意
nnn个点每次可以连接两个点和询问一个点所在联通块中第kkk大的数。 解题思路
我们发现可以启发式合并对于每个联通块维护一个线段树然后每次合并时将小的暴力丢入大的平很树里然后询问即可。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n)
其实可以用权线合并做到O(nlogn)O(n\log n)O(nlogn)但是在练平衡树就算了 codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N2e510,M6e610;
struct node{int to,next;
}a[N];
int n,m,tot,p[N],siz[N],rt[N],ls[N];
struct Treap{int tot,rt[N],siz[M],cnt[M],ls[M],rs[M],val[M],dat[M];void Updata(int x){siz[x]siz[ls[x]]siz[rs[x]]cnt[x];return;}void zig(int x){int yls[x];ls[x]rs[y];rs[y]x;xy;Updata(rs[x]);Updata(x);return;}void zag(int x){int yrs[x];rs[x]ls[y];ls[y]x;xy;Updata(ls[x]);Updata(x);return;}void Insert(int x,int w){if(!x){xtot;val[x]w;cnt[x]siz[x]1;dat[x]rand()*rand();return;}if(p[w]p[val[x]])cnt[x],Updata(x);if(p[w]p[val[x]]){Insert(ls[x],w);if(dat[x]dat[ls[x]])zig(x);}else{Insert(rs[x],w);if(dat[x]dat[rs[x]])zag(x);}Updata(x);return;}int GetVal(int x,int rank){if(!x)return 0;if(ranksiz[x])return -1;if(siz[ls[x]]rank)return GetVal(ls[x],rank);if(siz[ls[x]]cnt[x]rank)return val[x];return GetVal(rs[x],rank-siz[ls[x]]-cnt[x]); }
}T;
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x,int fa){T.Insert(T.rt[rt[x]],x);for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;rt[y]rt[x];dfs(y,x);}
}
void Merge(int x,int y){xrt[x];yrt[y];if(xy)return;if(siz[x]siz[y])swap(x,y);rt[y]rt[x];siz[x]siz[y];addl(x,y);dfs(y,x);return;
}
int main()
{scanf(%d%d,n,m);srand(n*m);for(int i1;in;i){scanf(%d,p[i]);rt[i]i;T.Insert(T.rt[i],i);siz[rt[i]]1;}while(m--){int x,y;scanf(%d%d,x,y);Merge(x,y);}scanf(%d,m);while(m--){char op[4];int x,y;scanf(%s %d %d,op,x,y);if(op[0]Q)printf(%d\n,T.GetVal(T.rt[rt[x]],y));else Merge(x,y);}return 0;
}
