题面
Solution
这题的确是可以用库鲁斯卡尔重构树+主席树来搞,但是本蒟蒻太菜了并不会,因此只能给大家讲讲离线+splay启发式合并的搞法。
首先,我们考虑把询问离线下来并按限制从小到大排序。然后我们可以考虑把边一条一条插入到图里面去,直到某个询问的限制。这样子,问题就变为了询问某一个连通块的K小值,连通块可以合并。
这个问题就肥肠简单了,我们可以用各种各样的数据结构来处理,线段树合并,splay启发式合并都可以。
考虑到每个点期望加入$logn$次,时间复杂度为$O(nlogn)$
Code
我这题因为TLE调了很久,原因是我在查询的时候没有splay,导致势能分析失效,请各位读者引以为戒
//Luogu P4197 Peaks
//Mar,7th,2019
//splay启发式合并
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long read()
{
long long x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int N=100000+100;
const int M=50*N;
struct SPLAY
{
#define root son[r][1]
int son[M][2],size[M],cnt[M],fa[M],w[M],to,toUse[M],top;
inline void update(int x)
{
size[x]=size[son[x][0]]+size[son[x][1]]+cnt[x];
}
inline void rotate(int x,int type)
{
int y=fa[x],z=fa[y];
fa[x]=z,son[z][y==son[z][1]]=x;
fa[son[x][type]]=y,son[y][!type]=son[x][type];
fa[y]=x,son[x][type]=y;
update(y),update(x);
}
void splay(int x,int to)
{
while(fa[x]!=to)
{
if(fa[fa[x]]!=to and x==son[fa[x]][fa[x]==son[fa[fa[x]]][1]])
rotate(fa[x],x==son[fa[x]][0]),
rotate(x,x==son[fa[x]][0]);
else
rotate(x,x==son[fa[x]][0]);
}
}
int newNode()
{
if(top!=0)
{
son[toUse[top]][0]=son[toUse[top]][1]=0;
size[toUse[top]]=fa[toUse[top]]=cnt[toUse[top]]=w[toUse[top]]=0;
return toUse[top--];
}
return ++to;
}
void Insert(int num,int r)
{
if(root==0)
{
root=newNode(),fa[root]=r;
w[root]=num,cnt[root]=1;
update(root);
return;
}
int now=root,last=r;
while(now!=0)
{
if(w[now]==num)
{
cnt[now]++,update(now);
splay(now,r);
return;
}
last=now,now=son[now][num>w[now]];
}
now=newNode();
fa[now]=last,son[last][num>w[last]]=now;
w[now]=num,cnt[now]=1,update(now);
splay(now,r);
}
int Query(int now,int r,int K)
{
if(size[son[now][1]]>=K)
return Query(son[now][1],r,K);
K-=(cnt[now]+size[son[now][1]]);
if(K<=0)
{
splay(now,r);
return w[now];
}
return Query(son[now][0],r,K);
}
void dfs(int now,int r)
{
if(now==0) return;
for(int i=1;i<=cnt[now];i++)//有可能一个点上有多个数字
Insert(w[now],r);
dfs(son[now][0],r);
dfs(son[now][1],r);
toUse[++top]=now;
}
#undef root
}splay;
int fa[N],size[N],root[N];
int FindFather(int x)
{
if(fa[x]==0) return x;
return fa[x]=FindFather(fa[x]);
}
void Merge(int x,int y)
{
if(FindFather(x)==FindFather(y)) return;
if(size[FindFather(x)]>size[FindFather(y)]) swap(x,y);
splay.dfs(splay.son[root[FindFather(x)]][1],root[FindFather(y)]);
//cerr<<x<<" "<<y<<" "<<size[FindFather(x)]<<" "<<size[FindFather(y)]<<" "<<splay.size[splay.son[root[FindFather(y)]][1]]<<endl;
size[FindFather(y)]+=size[FindFather(x)];
fa[FindFather(x)]=FindFather(y);
}
struct edge
{
int s,t,w;
friend bool operator < (edge x,edge y)
{
return x.w<y.w;
}
}e[M];
struct Query
{
int x,K,w,ans,no;
friend bool operator < (Query a,Query b)
{
return a.w<b.w;
}
}query[M];
bool cmp(Query a,Query b)
{
return a.no<b.no;
}
int Ask(int x,int K)
{
if(size[FindFather(x)]<K) return -1;
return splay.Query(splay.son[root[FindFather(x)]][1],root[FindFather(x)],K);
}
int n,m,q,h[N];
int main()
{
int t=clock();
freopen("4197.in","r",stdin);
freopen("4197.out","w",stdout);
n=read(),m=read(),q=read();
for(int i=1;i<=n;i++)
h[i]=read();
for(int i=1;i<=n;i++)
root[i]=splay.newNode(),size[i]=1;
for(int i=1;i<=n;i++)
splay.Insert(h[i],root[i]);
for(int i=1;i<=m;i++)
e[i].s=read(),e[i].t=read(),e[i].w=read();
for(int i=1;i<=q;i++)
query[i].x=read(),query[i].w=read(),query[i].K=read(),query[i].no=i;
sort(e+1,e+1+m);
sort(query+1,query+1+q);
int w_to=1;
for(int i=1;i<=q;i++)
{
//cerr<<i<<endl;
for(;e[w_to].w<=query[i].w and w_to<=m;w_to++)
Merge(e[w_to].s,e[w_to].t);
query[i].ans=Ask(query[i].x,query[i].K);
}
sort(query+1,query+1+q,cmp);
for(int i=1;i<=q;i++)
printf("%d\n",query[i].ans);
cerr<<clock()-t<<endl;
return 0;
}
文章评论