首页 > 代码库 > bzoj3545 [ONTAK2010]Peaks
bzoj3545 [ONTAK2010]Peaks
3545: [ONTAK2010]Peaks
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 572 Solved: 164
[Submit][Status]
Description
在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。
Input
第一行三个数N，M，Q。
第二行N个数，第i个数为h_i
接下来M行，每行3个数a b c，表示从a到b有一条困难值为c的双向路径。
接下来Q行，每行三个数v x k，表示一组询问。
Output
对于每组询问，输出一个整数表示答案。
Sample Input
10 11 4
1 2 3 4 5 6 7 8 9 10
1 4 4
2 5 3
9 8 2
7 8 10
7 1 4
6 7 1
6 4 8
2 1 5
10 8 10
3 4 7
3 4 6
1 5 2
1 5 6
1 5 8
8 9 2
1 2 3 4 5 6 7 8 9 10
1 4 4
2 5 3
9 8 2
7 8 10
7 1 4
6 7 1
6 4 8
2 1 5
10 8 10
3 4 7
3 4 6
1 5 2
1 5 6
1 5 8
8 9 2
Sample Output
6
1
-1
8
1
-1
8
HINT
【数据范围】
N<=10^5, M,Q<=5*10^5，h_i,c,x<=10^9。
不难想但是写起来细节超多
首先建成n棵平衡树，把询问和边都排序
然后每次用边权小于当前询问的边来合并平衡树，已经在同一集合的不理他就行了，所以还要并查集
ps：平衡树的启发式合并就是每次合并两棵树的时候把小的那棵的元素一个一个扔进大的那棵，每次nlogn。这样最坏情况是两棵树一样大，也就是说这样的状态只有logn个，所以复杂度nlog^2n
询问第k大不是随便打
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<deque> 9 #include<set> 10 #include<map> 11 #include<ctime> 12 #define LL long long 13 #define inf 0x7ffffff 14 #define pa pair<int,int> 15 #define pi 3.1415926535897932384626433832795028841971 16 using namespace std; 17 struct query{int v,k,x,rnk;}q[500010];bool operator <(const query &a,const query &b){return a.x<b.x;} 18 struct edge{int x,y,z;}ed[500010];bool operator <(const edge &a,const edge &b){return a.z<b.z;} 19 struct SBT{int l,r,son,rnd,rep,dat;}tree[2000010]; 20 int N,M,Q,treesize; 21 int root[500010]; 22 int ans[500010]; 23 int fa[500010]; 24 inline LL read() 25 { 26 LL x=0,f=1;char ch=getchar(); 27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 28 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 29 return x*f; 30 } 31 inline int getfa(int x) 32 {return fa[x]==x?x:fa[x]=getfa(fa[x]);} 33 inline void update(int k){tree[k].son=tree[tree[k].l].son+tree[tree[k].r].son+tree[k].rep;} 34 inline void right_rotate(int &k) 35 { 36 int t=tree[k].l; 37 tree[k].l=tree[t].r; 38 tree[t].r=k; 39 tree[t].son=tree[k].son; 40 update(k); 41 k=t; 42 } 43 inline void left_rotate(int &k) 44 { 45 int t=tree[k].r; 46 tree[k].r=tree[t].l; 47 tree[t].l=k; 48 tree[t].son=tree[k].son; 49 update(k); 50 k=t; 51 } 52 inline void insert(int &k,int x,int rep) 53 { 54 if (!k) 55 { 56 k=++treesize; 57 tree[k].dat=x; 58 tree[k].son=rep; 59 tree[k].rep=rep; 60 tree[k].rnd=rand(); 61 return; 62 } 63 tree[k].son+=rep; 64 if (x==tree[k].dat) 65 { 66 tree[k].rep+=rep; 67 return; 68 } 69 if (x<tree[k].dat) 70 { 71 insert(tree[k].l,x,rep); 72 if (tree[tree[k].l].rnd>tree[k].rnd)right_rotate(k); 73 }else 74 if (x>tree[k].dat) 75 { 76 insert(tree[k].r,x,rep); 77 if (tree[tree[k].r].rnd>tree[k].rnd)left_rotate(k); 78 } 79 } 80 inline int ask(int now,int x) 81 { 82 if(now==0)return -1; 83 if(x<=tree[tree[now].l].son)return ask(tree[now].l,x); 84 else if(x>tree[tree[now].l].son+tree[now].rep)return ask(tree[now].r,x-tree[tree[now].l].son-tree[now].rep); 85 else return tree[now].dat; 86 } 87 inline void dfs(int from,int &to) 88 { 89 if (!from)return; 90 insert(to,tree[from].dat,tree[from].rep); 91 dfs(tree[from].l,to); 92 dfs(tree[from].r,to); 93 } 94 inline void merge(int k) 95 { 96 int l=getfa(ed[k].x),r=getfa(ed[k].y); 97 if (l==r)return; 98 if (tree[root[l]].son<tree[root[r]].son) 99 {100 dfs(root[l],root[r]);101 fa[l]=r;102 }else103 {104 dfs(root[r],root[l]);105 fa[r]=l;106 }107 }108 inline void init()109 {110 N=read();M=read();Q=read();111 for (int i=1;i<=N;i++)fa[i]=i;112 for (int i=1;i<=N;i++)insert(root[i],read(),1);113 for (int i=1;i<=M;i++)114 {115 ed[i].x=read();116 ed[i].y=read();117 ed[i].z=read();118 }119 for (int i=1;i<=Q;i++)120 {121 q[i].v=read();122 q[i].x=read();123 q[i].k=read();124 q[i].rnk=i;125 }126 sort(ed+1,ed+M+1);127 sort(q+1,q+Q+1);128 }129 inline void work()130 {131 int now=1;132 for(int i=1;i<=Q;i++)133 {134 while (now<=M&&ed[now].z<=q[i].x)merge(now),now++;135 int st=getfa(q[i].v),tot=tree[root[st]].son;136 if (tot<q[i].k)ans[q[i].rnk]=-1;137 else ans[q[i].rnk]=ask(root[st],tot-q[i].k+1);138 }139 for (int i=1;i<=Q;i++)140 printf("%d\n",ans[i]);141 }142 int main()143 {144 init();145 work();146 return 0;147 }
bzoj3545 [ONTAK2010]Peaks
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。