bzoj3545 [ONTAK2010]Peaks

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

Sample Output 6

1

-1

8

HINT 【数据范围】

N<=10^5, M,Q<=5*10^5，h_i,c,x<=10^9。

题解：我将询问离线一下 然后按照道路的难度从小到大 排序 然后 再将 我要询问的难度从小到大 排序 然后根据每个询问的难度去把小于这个难度的边连上然后把他们根的主席树合并 线段树合并的均摊复杂度是n*log(n) 然后用并查集判断是否这两个点联通 然后在线段树上去二分我想要的即可

如果询问的数量比我总的山还要多 就输出-1即可

#include#include#define N 110000using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x*f;}int a[N],w[N],a1[N],nn,n,m,q,num,fa[N],root[N],ans[N*5];struct node{ int left,right,v;}tree[N*40];struct node1{ int x,y,z;}data[550000];struct node2{ int x,y,k,id;}qr[550000];inline void insert1(int &x,int l,int r,int p){ tree[++num]=tree[x];x=num;tree[x].v++; if (l==r) return;int mid=l+r>>1; if (p<=mid) insert1(tree[x].left,l,mid,p);else insert1(tree[x].right,mid+1,r,p);}inline int merge(int rt1,int rt2){ if (!rt1||!rt2) return rt1+rt2; tree[rt2].left=merge(tree[rt1].left,tree[rt2].left);tree[rt2].right=merge(tree[rt1].right,tree[rt2].right); tree[rt2].v=tree[rt1].v+tree[rt2].v;return rt2;}inline bool cmp(node1 a,node1 b){return a.z>1;int l1=tree[x].left,r1=tree[x].right; if (k<=tree[l1].v) return query(l1,l,mid,k);else return query(r1,mid+1,r,k-tree[l1].v);}void print(int x,int l,int r){ int mid=l+r>>1; if (tree[x].left) print(tree[x].left,l,mid); if (l==r) printf("%d %d %d\n",l,r,tree[x].v); if (tree[x].right) print(tree[x].right,mid+1,r);}int main(){ //freopen("bzoj3545.in","r",stdin); n=read();m=read();q=read(); for (int i=1;i<=n;++i) a[i]=read(),w[i]=a[i];sort(w+1,w+n+1);nn=unique(w+1,w+n+1)-w-1; for (int i=1;i<=n;++i) a1[i]=lower_bound(w+1,w+nn+1,a[i])-w;for (int i=1;i<=n;++i) fa[i]=i; for (int i=1;i<=n;++i) insert1(root[i],1,nn,a1[i]); for (int i=1;i<=m;++i){ int x=read(),y=read(),z=read(); data[i].x=x;data[i].y=y;data[i].z=z; }sort(data+1,data+m+1,cmp);for (int i=1;i<=q;++i) qr[i].x=read(),qr[i].y=read(),qr[i].k=read(),qr[i].id=i; sort(qr+1,qr+q+1,cmp1);int now=1;//for (int i=1;i<=m;++i) printf("%d %d %d\n",data[i].x,data[i].y,data[i].z); for (int i=1;i<=q;++i){ while(data[now].z<=qr[i].y&&now<=m){ int x=find(data[now].x),y=find(data[now].y); if (x!=y) fa[x]=y,root[y]=merge(root[x],root[y]);now++; }//print(root[find(qr[i].x)],1,nn);printf("asdfasd\n");printf("%d %d\n",find(qr[i].x),qr[i].k);printf("dfsd\n"); int rt=root[find(qr[i].x)];if (tree[rt].v-qr[i].k+1<=0) {ans[qr[i].id]=-1; continue;} int tmp=query(rt,1,nn,tree[rt].v-qr[i].k+1);ans[qr[i].id]=w[tmp]; } for (int i=1;i<=q;++i) printf("%d\n",ans[i]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。