[bzoj3545]Peaks

概述离线读入并按照困难度排序，即相当于支持两种 *** 作：连边和查询。对于每一个连通块在根节点建一个权值线段树，连边即合并两颗线段树，而查询就是在一棵线段树中查询（注意：边数和询问为$5*10^{5}$）。 1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mid (l+r>>1) 4 #define N 200005 5

离线读入并按照困难度排序，即相当于支持两种 *** 作：连边和查询。对于每一个连通块在根节点建一个权值线段树，连边即合并两颗线段树，而查询就是在一棵线段树中查询（注意：边数和询问为*10^{5}$）。

 1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mID (l+r>>1) 4 #define N 200005 5 struct ji{ 6     int x,y,z,ID; 7 }e[N*10]; 8 int V,n,m,q,t,f[N],a[N],b[N],r[N],ans[N*5],sz[N*20],ls[N*20],rs[N*20]; 9 bool cmp(ji x,ji y){10     return (x.z<y.z)||(x.z==y.z)&&(x.ID<y.ID);11 }12 voID read(int &n){13     char c=0;14     while (!isdigit(c))c=getchar();15     while (isdigit(c)){16         n=n*10+(c^48);17         c=getchar();18     }19 }20 int find(int k){21     if (k==f[k])return k;22     return f[k]=find(f[k]);23 }24 voID update(int k,int l,int r,int x){25     sz[k]=1;26     if (l==r)return;27     if (x<=mID)update(ls[k]=++V,l,mID,x);28     else update(rs[k]=++V,mID+1,r,x);29 }30 int merge(int x,int y){31     if (x*y==0)return x+y;32     if (ls[x]+rs[x]==0)sz[x]+=sz[y];33     else sz[x]=sz[ls[x]=merge(ls[x],ls[y])]+sz[rs[x]=merge(rs[x],rs[y])];34     return x;35 }36 int query(int k,int x){37     if (l==r)return l;38     if (x<=sz[ls[k]])return query(ls[k],x);39     else return query(rs[k],mID+1,x-sz[ls[k]]);40 }41 int main(){42     read(n);43     read(m);44     read(q);45     for(int i=1;i<=n;i++){46         read(a[i]);47         b[f[i]=i]=a[i];48     }49     sort(b+1,b+n+1);50     t=unique(b+1,b+n+1)-b-1;51     for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+t+1,a[i])-b;52     for(int i=1;i<=n;i++)update(r[i]=++V,1,a[i]);53     for(int i=1;i<=m+q;i++){54         read(e[i].x);55         read(e[i].y);56         read(e[i].z);57         if (i>m){58             e[i].ID=i-m;59             swap(e[i].y,e[i].z);60         }61     }62     m+=q;63     sort(e+1,e+m+1,cmp);64     for(int i=1;i<=m;i++){65         e[i].x=find(e[i].x);66         if (!e[i].ID){67             e[i].y=find(e[i].y);68             if (e[i].x==e[i].y)continue;69             f[e[i].x]=e[i].y;70             r[e[i].y]=merge(r[e[i].x],r[e[i].y]);71         }72         else73             if (sz[r[e[i].x]]<e[i].y)ans[e[i].ID]=-1;74             else ans[e[i].ID]=b[query(r[e[i].x],1,sz[r[e[i].x]]-e[i].y+1)];75     }76     for(int i=1;i<=q;i++)printf("%d\n",ans[i]);77     return 0;78 }

VIEw Code 总结

以上是内存溢出为你收集整理的[bzoj3545]Peaks全部内容，希望文章能够帮你解决[bzoj3545]Peaks所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。