BZOJ 2588 Count on a tree (COT) 是持久的段树

BZOJ 2588 Count on a tree (COT) 是持久的段树

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

标题效果:两棵树之间的首次查询k大点的权利。

思维:树木覆盖树,事实上,它是正常的树木覆盖了持久段树。

由于使用权值段树可以寻求区间k大,然后应用到持久段树思想,间隔可以做减法。详见代码。

CODE:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 100010
#define NIL (tree[0])
using namespace std;

pair<int,int> src[MAX];

struct Complex{
	Complex *son[2];
	int cnt;

	Complex(Complex *_,Complex *__,int ___):cnt(___) {
		son[0] = _;
		son[1] = __;
	}
	Complex() {}
}*tree[MAX];

int points,asks;
int xx[MAX];

int head[MAX],total;
int next[MAX << 1],aim[MAX << 1];

int father[MAX][20],deep[MAX];

inline void Add(int x,int y);
void DFS(int x);
void SparseTable();

Complex *BuildTree(Complex *pos,int x,int y,int val);
int GetAns(Complex *l,Complex *r,Complex *f,Complex *p,int x,int y,int k);
int GetLCA(int x,int y);
int Ask(int x,int y,int k);

int main()
{
	cin >> points >> asks;
	for(int i = 1;i <= points; ++i)
		scanf("%d",&src[i].first),src[i].second = i;
	sort(src + 1,src + points + 1);
	for(int i = 1;i <= points; ++i)
		xx[src[i].second] = i;
	for(int x,y,i = 1;i < points; ++i) {
		scanf("%d%d",&x,&y);
		Add(x,y),Add(y,x);
	}
	NIL = new Complex(NULL,NULL,0);
	NIL->son[0] = NIL->son[1] = NIL;
	DFS(1);
	SparseTable();
	int now = 0;
	for(int x,y,k,i = 1;i <= asks; ++i) {
		scanf("%d%d%d",&x,&y,&k);
		printf("%d",now = src[Ask(x ^ now,y,k)].first);
		if(i != asks)	puts("");
	}
	return 0;
}

inline void Add(int x,int y)
{
	next[++total] = head[x];
	aim[total] = y;
	head[x] = total;
}

void DFS(int x)
{
	deep[x] = deep[father[x][0]] + 1;
	tree[x] = BuildTree(tree[father[x][0]],1,points,xx[x]);
	for(int i = head[x];i;i = next[i]) {
		if(aim[i] == father[x][0])	continue;
		father[aim[i]][0] = x;
		DFS(aim[i]);
	}
}

void SparseTable()
{
	for(int j = 1;j <= 19; ++j)
		for(int i = 1;i <= points; ++i)
			father[i][j] = father[father[i][j - 1]][j - 1];
}

int Ask(int x,int y,int k)
{
	int lca = GetLCA(x,y);
	return GetAns(tree[x],tree[y],tree[lca],tree[father[lca][0]],1,points,k);
}

Complex *BuildTree(Complex *pos,int x,int y,int val)
{
	int mid = (x + y) >> 1;
	if(x == y)	return new Complex(NIL,NIL,pos->cnt + 1);
	if(val <= mid)	return new Complex(BuildTree(pos->son[0],x,mid,val),pos->son[1],pos->cnt + 1);
	return new Complex(pos->son[0],BuildTree(pos->son[1],mid + 1,y,val),pos->cnt + 1);	
}

int GetLCA(int x,int y)
{
	if(deep[x] < deep[y])	swap(x,y);
	for(int i = 19; ~i; --i)
		if(deep[father[x][i]] >= deep[y])
			x = father[x][i];
	if(x == y)	return x;
	for(int i = 19; ~i; --i)
		if(father[x][i] != father[y][i])
			x = father[x][i],y = father[y][i];
	return father[x][0];
}

int GetAns(Complex *l,Complex *r,Complex *f,Complex *p,int x,int y,int k)
{
	if(x == y)	return x;
	int mid = (x + y) >> 1;
	int temp = l->son[0]->cnt + r->son[0]->cnt - f->son[0]->cnt - p->son[0]->cnt;
	if(k <= temp)	return GetAns(l->son[0],r->son[0],f->son[0],p->son[0],x,mid,k);
	return GetAns(l->son[1],r->son[1],f->son[1],p->son[1],mid + 1,y,k - temp);
}

版权声明:本文博客原创文章。博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117451.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • zabbix===》使用模板监控nginx、php-fpm、redis「建议收藏」

    zabbix===》使用模板监控nginx、php-fpm、redis「建议收藏」一、使用模板监控nginx1.下载nginx(要监控的主机也就是客户端)#1.有CentOS-Base.repo和epel.repo这两个源就可以直接yum下载nginx[root@db01~]#cd/etc/yum.repos.d/[root@db01yum.repos.d]#ll总用量16-rw-r–r–.1rootroot252311月1803:23CentOS-Base.repo-rw-r–r–.1rootroot66411月1803

  • java当前时间的时间戳_java获取当前时间(时间戳)的方法

    java当前时间的时间戳_java获取当前时间(时间戳)的方法获取当前时间戳(毫秒级)//方法一System.currentTimeMillis();//方法二Calendar.getInstance().getTimeInMillis();//方法三newDate().getTime();获取当前时间SimpleDateFormatdf=newSimpleDateFormat(“yyyy-MM-ddHH:mm:ss”);//设置日期格式S…

  • 不能逃避的分离「建议收藏」

    生命的意义是什么,我一直在探索 !对我来说,刚刚过往一个年,过年在家的状态是简单单纯的,不用去思考很多事情,就是享受家的感觉,享受和家人一切的幸福。2018这个年在家待的时间比较久,因为外出工作,现在也在外面生活,和家人在一起的时间真的很少,从2015年毕业后到外面工作一直是一年回家一次,2017还算多,回家两次,但是即便是回家两次,真正在家里待的时间也是不多的,仔细算算在父母有限…

  • Linux-dosbox使用「建议收藏」

    2019独角兽企业重金招聘Python工程师标准>>>…

  • 大数据平台的元数据管理

    大数据平台的元数据管理【概念解释】1,大数据平台——是指服务于大数据计算或存储的平台,包括大数据的计算集群(hive、spark、flink、storm等等)和存储集群(如hadoop、hbase等等)。2,大数据平台涉及的元数据——由大数据作业的业务逻辑直接读写处理的业务数据,都不是元数据,除此之外的数据都是元数据。例如数据表的schema信息、任务之间的血缘关系、任务的权限映射关系、数据的业务属性、数据占用的磁…

  • 服务器安装linux系统安装教程_linux服务器重装系统

    服务器安装linux系统安装教程_linux服务器重装系统一、linux镜像的刻录1.首先打开电脑上面任意浏览器(IE、MicrosoftEdge、chrome、Firefox),输入网址https://www.centos.org/我们可以看到如下界面选择立即获取centos下载最新的安装镜像,复制下载链接(http://isoredirect.centos.org/centos/7/isos/x86_64/CentOS-7-x86_64…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号