「BZOJ3545」[ONTAK2010] Peaks
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。
题解
唉。。。
为啥我要作死的写线段树合并T T
谁告诉我这个复杂度是啥，为何比平衡树的启发式合并慢
做法就是离线后按照边权排序
不断合并连通块以及回答询问，每个连通块建权值线段树
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<vector> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,q,sz; int disc[100005],fa[100005],h[100005],root[100005],ans[500005]; int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);} struct data{int a,b,w,ans,id,f;}a[1000005]; int ls[5000005],rs[5000005],sum[5000005]; bool operator<(data a,data b) { return a.w<b.w||(a.w==b.w&&a.f<b.f); } void insert(int &k,int l,int r,int val) { if(!k)k=++sz;sum[k]=1; if(l==r)return; int mid=(l+r)>>1; if(val<=mid)insert(ls[k],l,mid,val); else insert(rs[k],mid+1,r,val); } int query(int k,int l,int r,int rank) { if(l==r)return l; int mid=(l+r)>>1; if(sum[ls[k]]>=rank)return query(ls[k],l,mid,rank); else return query(rs[k],mid+1,r,rank-sum[ls[k]]); } int merge(int x,int y) { if(!x)return y; if(!y)return x; if(!ls[x]&&!rs[x]) { sum[x]=sum[x]+sum[y]; return x; } ls[x]=merge(ls[x],ls[y]); rs[x]=merge(rs[x],rs[y]); sum[x]=sum[ls[x]]+sum[rs[x]]; return x; } void solve() { for(int i=1;i<=n;i++)insert(root[i],1,n,h[i]); for(int i=1;i<=m+q;i++) if(!a[i].f) { int p=find(a[i].a),q=find(a[i].b); if(p!=q) { fa[p]=q; root[q]=merge(root[p],root[q]); } } else { int x=find(a[i].a); if(sum[root[x]]<a[i].b)ans[a[i].id]=-1; else ans[a[i].id]=disc[query(root[x],1,n,sum[root[x]]-a[i].b+1)]; } } int main() { n=read();m=read();q=read(); for(int i=1;i<=n;i++)h[i]=read(),disc[i]=h[i]; sort(disc+1,disc+n+1); for(int i=1;i<=n;i++)h[i]=lower_bound(disc+1,disc+n+1,h[i])-disc; for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++) a[i].f=0,a[i].a=read(),a[i].b=read(),a[i].w=read(); for(int i=m+1;i<=m+q;i++) a[i].f=1,a[i].id=i-m,a[i].a=read(),a[i].w=read(),a[i].b=read(); sort(a+1,a+m+q+1); solve(); for(int i=1;i<=q;i++) printf("%d\n",ans[i]); return 0; } |
计数器 9787231
OI 课件=>
OI 课件=>
线段树的合并如果没有重复元素是O(nlogn)的，有就是O(nlog^2n)
%%%%%PO姐