3
28
2016
0

[bzoj]3551: [ONTAK2010]Peaks加强版

传送门-->http://www.lydsy.com/JudgeOnline/problem.php?id=3551

搞了一上午的系统总算是弄好了,颓

经典题,很早就想做了,正巧要给初三爷讲并$(zhu)$查$(xi)$集$(shu)$,然后发现这道题可以放作业题_(:зゝ∠)_

先是看了$Claris$的题解,瞬间变成猪,太神了和我的逗比做法完全不同


考虑$kruskal$重构树, 对于一条新加入的边$(x,y)$,新建一个节点$z$,把$x$的父亲指向$z$$y$也一样,$z$的点权为$(x,y)$的边权,用并查集维护,这样就构出了一棵新的树

这个树有什么性质呢,因为边是从小到大加的,于是深度越大点权越小,然后可以发现,对于询问从$v$出发边权小于$x$所能达到的联通块,也就是从$v$向上爬最高的点权小于$x$的点的子树,这个东西可以倍增找,由于我比较弱于是写了树剖,在重链里二分,然后就变成一道裸的$dfs$序主席树了

别问我为什么辣么快,我系不会告诉你的

#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 100010
int i,j,k,m,n,x,y,lastans,fa[N<<1],Q,id[N<<1],hs[N],rk[N<<1],top[N<<1],sz[N<<1],dep[N<<1],f[N<<1],in[N<<1],now,ot[N<<1],son[N<<1],tot,cnt,L,h[N],last[N<<1],v[N<<1];bool vis[N<<1];
struct edge{int to,next;}e[N<<2];
struct abc{
	int x,y,z;
	inline void in(){x=read(),y=read(),z=read();}
	inline bool operator<(const abc&b)const{return z<b.z;}
}o[N*5];
struct tree{int l,r,cnt;}T[(N<<1)*20];
inline void add(int u,int v){e[++cnt]=(edge){v,last[u]},last[u]=cnt;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void dfs1(int x,int d){
	dep[x]=d,sz[x]=1,vis[x]=1;
	for(int i=last[x],y;i;i=e[i].next){
		f[y=e[i].to]=x,dfs1(y,x),sz[x]+=sz[y];
		if(sz[y]>sz[son[x]])son[x]=y;
	}
}
void dfs2(int x,int d){
	top[x]=d,rk[in[x]=++now]=x;if(son[x])dfs2(son[x],d);
	for(int i=last[x],y;i;i=e[i].next)if((y=e[i].to)!=son[x])dfs2(y,y);ot[x]=now;
}
void insert(int&y,int k,int l,int r,int v){
	T[y=++L].cnt=T[k].cnt+1;if(l==r)return;
	T[y]=(tree){T[k].l,T[k].r,T[y].cnt};int m=l+r>>1;
	v<=m?insert(T[y].l,T[k].l,l,m,v):insert(T[y].r,T[k].r,m+1,r,v);
}
inline int ef(int l,int r,int x){
	while(l<=r){
		int m=l+r>>1;
		if(v[rk[m]]>x)l=m+1;else r=m-1;
	}return rk[r+1];
}
inline int up(int l,int r,int x){
	while(top[l]!=r)if(v[f[top[l]]]<=x)l=f[top[l]];else return ef(in[top[l]],in[l],x);
	return ef(in[r],in[l],x);
}
int ask(int l,int r,int o,int v,int kth){
	if(l==r)return l;int m=l+r>>1;
	int ret=T[T[v].l].cnt-T[T[o].l].cnt;
	if(kth<=ret)return ask(l,m,T[o].l,T[v].l,kth);
	else return ask(m+1,r,T[o].r,T[v].r,kth-ret);
}
int main(){
	for(n=read(),m=read(),Q=read(),i=1;i<=n;++i)hs[i]=h[i]=read();
	for(i=1;i<=m;++i)o[i].in();
	for(i=1;i<=n<<1;++i)fa[i]=i;
	for(tot=n,sort(o+1,o+m+1),i=1;i<=m;++i){
		int p=find(o[i].x),q=find(o[i].y);
		if(p!=q)fa[p]=fa[q]=++tot,v[tot]=o[i].z,add(tot,p),add(tot,q);
	}
	for(i=1;i<=n;++i)if(!vis[i])dfs1(find(i),1),dfs2(find(i),find(i));
	for(sort(hs+1,hs+n+1),i=1;i<=n;++i)h[i]=lower_bound(hs+1,hs+n+1,h[i])-hs;
	for(i=1;i<=now;++i)if(rk[i]<=n)insert(id[i],id[i-1],1,n,h[rk[i]]);
	else id[i]=id[i-1];
	for(i=1;i<=Q;++i){
		int v=read(),x=read(),k=read();
		if(lastans!=-1)v^=lastans,x^=lastans,k^=lastans;
		int t=up(v,find(v),x),a=id[in[t]],b=id[ot[t]];
		if(T[b].cnt-T[a].cnt<k)lastans=-1;
		else lastans=hs[ask(1,n,a,b,T[b].cnt-T[a].cnt-k+1)];
		printf("%d\n",lastans);
	}
}

 

$loading...$

Category: bzoj | Tags: 重构 DFS序 主席树 | Read Count: 517

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com