BZOJ3545：[ONTAK2010]Peaks

浅谈线段树合并：https://www.cnblogs.com/AKMer/p/10251001.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=3545

离线，按照权值排序之后就跟[HNOI2012]永无乡一样了。

时间复杂度：\(O(nlogn)\)

空间复杂度：\(O(nlogn)\)

代码如下：

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn=1e5+5,maxm=5e5+5;

int n,m,Q,cnt;

int tmp[maxn],h[maxn];

int fa[maxn],rt[maxn],ans[maxm];

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

struct edge {

	int a,b,v;

	bool operator<(const edge &a)const {

		return v<a.v;

	}

}e[maxm];

struct Query {

	int u,rk,limit,id;

	bool operator<(const Query &a)const {

		return limit<a.limit;

	}

}q[maxm];

int find(int x) {

	if(fa[x]==x)return x;

	return fa[x]=find(fa[x]);

}

struct segment_tree {

	int tot;

	int sum[maxn*20],ls[maxn*20],rs[maxn*20];

	void change(int &p,int l,int r,int pos) {

		p=++tot,sum[p]=1;

		if(l==r)return;

		int mid=(l+r)>>1;

		if(pos<=mid)change(ls[p],l,mid,pos);

		else change(rs[p],mid+1,r,pos);

	}

	int merge(int a,int b) {

		if(!a||!b)return a+b;

		if(!ls[a]&&!rs[a]&&!ls[b]&&!rs[b]) {

			sum[a]+=sum[b];return a;

		}

		ls[a]=merge(ls[a],ls[b]);

		rs[a]=merge(rs[a],rs[b]);

		sum[a]=sum[ls[a]]+sum[rs[a]];

		return a;

	}

	int query(int p,int l,int r,int rk) {

		if(l==r)return l;

		int mid=(l+r)>>1;

		if(sum[rs[p]]>=rk)return query(rs[p],mid+1,r,rk);

		else return query(ls[p],l,mid,rk-sum[rs[p]]);

	}

}T;

int main() {

	n=read(),m=read(),Q=read();

	for(int i=1;i<=n;i++)

		tmp[i]=h[i]=read();

	sort(tmp+1,tmp+n+1);

	cnt=unique(tmp+1,tmp+n+1)-tmp-1;

	for(int i=1;i<=n;i++)

		h[i]=lower_bound(tmp+1,tmp+cnt+1,h[i])-tmp;

	for(int i=1;i<=m;i++)

		e[i].a=read(),e[i].b=read(),e[i].v=read();

	for(int i=1;i<=Q;i++)

		q[i].u=read(),q[i].limit=read(),q[i].rk=read(),q[i].id=i;

	sort(e+1,e+m+1),sort(q+1,q+Q+1);

	for(int i=1;i<=n;i++)

		fa[i]=i,T.change(rt[i],1,cnt,h[i]);

	int st=1;

	for(int i=1;i<=Q;i++) {

		while(st<=m&&e[st].v<=q[i].limit) {

			int a=find(e[st].a),b=find(e[st].b);

			if(a!=b)fa[a]=b,rt[b]=T.merge(rt[b],rt[a]);st++;

		}

		int u=find(q[i].u);

		if(T.sum[rt[u]]<q[i].rk)ans[q[i].id]=-1;

		else ans[q[i].id]=tmp[T.query(rt[u],1,cnt,q[i].rk)];

	}

	for(int i=1;i<=Q;i++)

		printf("%d\n",ans[i]);

	return 0;

}

巴特西

BZOJ3545：[ONTAK2010]Peaks

最新文章

热门文章