hdu 6430 TeaTree 线段树合并_Dale_zero的博客-程序员秘密

技术标签: 线段树合并  

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6430

对每个节点开一颗线段树,标程的写法很节省空间:预处理出每个数字的因数,对题目中给定的权值建线段树,如果子树区间中没有根节点权值的因数,那么直接剪掉。然后通过改变每个根节点左右孩子数组的值,来改变其指向的子树根节点(即合并过程)。相当于是一棵精简的线段树。

因为权值最大为1e5,所以nlognlogn不会T。

合并时对每一对父子节点都尽可能地找到底(s==t)如果能到达底部,说明父子节点都有这个因数,s(或者t)就可能是gcd的最大值,将其与ans值比较更新。而因为每一个节点在以其为根的子树中总是最后被遍历的,所以在此过程中就符合了LCA的要求。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define mod 1000000007
#define For(i,m,n) for(int i=m;i<=n;i++)
#define Dor(i,m,n) for(int i=m;i>=n;i--)
#define LL long long
#define lan(a,b) memset(a,b,sizeof(a))
#define sqr(a) a*a
using namespace std;


const int maxn=100005;
int tot;

vector<int> d[maxn];
int ls[maxn*400],rs[maxn*400];
int ans[maxn],f[maxn],root[maxn];
int fa;
void init()
{
    For(i,1,maxn-5)
        for(int j=1;j*i<=maxn-5;j++)
            d[j*i].push_back(i);
}

void build(int& x,int s,int t,int pos)
{
    if(!x){x=++tot;ls[x]=rs[x]=0;}
    if(s==t)return;
    int mid=(s+t)>>1;
    if(pos>mid)build(rs[x],mid+1,t,pos);
    else build(ls[x],s,mid,pos);
}

int merge(int x,int y,int s,int t)
{
    if(!x||!y) return x^y;
    if(s==t){ans[fa]=max(ans[fa],s);return x;}
    int mid=(s+t)>>1;
    ls[x]=merge(ls[x],ls[y],s,mid);
    rs[x]=merge(rs[x],rs[y],mid+1,t);
    return x;
}

int main()
{
    int n;
    init();
    while(~scanf("%d",&n))
    {
        lan(ans,-1);
        For(i,2,n)
            scanf("%d",&f[i]);
            int x;
        tot=0;
        For(i,1,n)
        {
            scanf("%d",&x);
            root[i]=++tot;
            ls[tot]=rs[tot]=0;
            For(j,0,d[x].size()-1)
                build(root[i],1,1e5,d[x][j]);
        }
        Dor(i,n,1)
        {
            fa=f[i];
            root[fa]=merge(root[fa],root[i],1,1e5);
        }
        For(i,1,n)
            printf("%d\n",ans[i]);
    }
    return 0;
}

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Dale_zero/article/details/82027470

智能推荐

UE4 Datasmith 导入流程源码分析_wblong_cs的博客-程序员秘密_ue4源码分析

UE4 Datasmith 导入流程源码分析导入入口函数:Engine\Plugins\Enterprise\DatasmithImporter\DatasmithImporter\Private\DatasmithImporterModule.cppvoid FDatasmithImporterModule::SetupMenuEntry(){ if (!IsRunningCommandlet()) { FDatasmithUIManager::Get().AddM

SpringBoot博客系统之后台登陆和拦截器配置_今天你学习了么的博客-程序员秘密

登陆的实现逻辑很简单,只需要根据传入的用户名和密码做出相应的判断并和数据库中数据匹配即可基本实现1. controller层,先对传入的用户名和密码进行非空判断再调用Service层进行数据库匹配,如果匹配成功则把用户信息存到session域中,并且重定向到admin/index请求,返回index页主要,因为这里涉及到了表单的提交所以再跳转页的时候一定要使用重定向请求转发和直接返回inde...

IT互联网的一些职位的简称_szh199317的博客-程序员秘密_互联网产品经理简称

互联网各职位的简称 :PM&amp;nbsp;(&amp;nbsp;Product Manager&amp;nbsp;)&amp;nbsp;产品经理:&amp;nbsp; &amp;nbsp;&amp;nbsp; &amp;nbsp; 产品的构想、框架的设计、用户的调研等。UE(User&amp;nbsp;Experience,简称UX或&amp;nbsp;UE)用户体验:&amp;nbsp; &amp;nbsp;&amp;nbsp; &amp;nbsp; 还有个组合叫法:UED(产品交互设计师,用

04 | 语法分析_LALAAYANG的博客-程序员秘密_语法分析是什么

04 | 语法分析语法分析程序(语法分析器)概述自上而下分析法前述递归下降分析法预测分析法( LL(1)分析法 )自下而上分析法前述算符优先分析法LR分析法LR(0)语法分析程序(语法分析器)概述输入:词法分析器生成的单词符号序列输出:语法树详述:语法分析器的功能是以词法分析器生成的单词符号序列作为输入,根据语言的语法规则(描述程序语言语法结构的上下文无关文法),识别出各种语法成分(如表达式、语句、程序段以及整个程序等),并在分析过程中进行语法检查,检查所给单词符号序列是否是该语言的文法的一个句子

工作七八载,初次写博客。开源受益多,而今且交互。前路长又漫,且行且珍惜。_Linux运维小兵的博客-程序员秘密

杂写感想感想本人网络系统专业学渣一个,毕业已经7、8年了。刚毕业时年轻好玩,社会上随波逐流,天南地北只求快乐、义气。跟着朋友吃吃喝喝,饭馆、电网销之类都做过。慢慢发现人和人是不一样的,有的人直接就生在终点,有些人自带气运,有些人天赋出众;自己呐?既非豪富之家、又无天降横财,只是个普普通通的农村娃,吃穿住行自有一套,但是想要提高,还是要靠自己的努力。后来做运维,桌面运维、软件运维、Linux运维,一步步走到现在。计算机行业的专业性还是蛮大的,工作以后发现学的东西早就忘得一干二净,这几年来网上各种博客论

【渝粤题库】陕西师范大学200971教育经济学 作业(专升本、高起本)_yuyueshool的博客-程序员秘密

《教育经济学》作业一、单选题1.我国多数学者认为,应该把教育经济学隶属于经济科学体系,属于( )。A.宏观经济学 B.微观经济学 C.部门经济学 D.产业经济学2.教育经济学是现代经济和现代教育的产物,它在西方萌芽于20世纪20年代,形成于( )年代。A.40 B.60 D.703.人力资本这一概念是由美国的( )于1935年首先使用的A.舒尔茨 B.丹尼森 C.贝克

随便推点

Android开发实战“基于环信的通信工具”——01.账号模块的实现_赈川的博客-程序员秘密

文章目录1.内容介绍2.环信sdk集成以及初始化3.闪屏页面的实现4.MVP介绍5.ButterKnife集成以及使用6.登录页面的实现7.注册页面的实现1.内容介绍IM,Instance message,QQ、微信都是属于这方面(指代通信App,下文一样)的应用此外,直播类、电商类、通讯类都属于这类应用开发这类项目时可以借用已经编写好的第三方平台,节省编写相关逻辑的花销,当前主要有融云、...

C#使用第三方控件ReoGrid实现将Excel嵌套在程序中,方便数据的导入,可以直接粘贴数据,加载Excel模板样式_平平淡淡才是true的博客-程序员秘密_reogrid

1、引用dll2、将生成的控件拖入到窗体中3、加载Excel模板,含有主要代码,实现cellvaluechange功能,类似datagridviewpath = Util.Pub.DownloadFile("重庆模组成本模型.xlsx"); reoGridControl1.Load(path, unvell.ReoGrid.IO.FileFormat.Excel2007);reoGridControl1.Worksheets[0].Ce

ClassLoader加载机制深入分析_taiyang5946的博客-程序员秘密_classloader加载原理

我们知道在java程序中,需要将我们写的java文件编译为class文件才能被使用,一个java程序也是由许许多多的class文件组成。在程序运行的时候是需要将这些class文件加载到内存中才能被我们使用的,而且这些class文件也不是一次性的被加载进内存的,它是什么时候需要就什么时候加载,加载这些class文件到内存中就需要使用ClassLoader类加载器来完成。一般情况下我们不需要关系Cla...

主流分布式存储技术的对比分析与应用_诸葛钢铁云的博客-程序员秘密_分布式存储技术

摘 要:随着数字化转型的深入,海量数据对存储提出了新的要求。传统存储虽然有技术成熟、性能良好、可用性高等优点,但面对海量数据,其缺点也越来越明显:如扩展性差、成本高等。为了克服上述缺点,满足海量数据的存储需求,市场上出现了分布式存储技术。分布式存储系统,通常包括主控服务器、存储服务器,以及多个客户端组成。其本质是将大量的文件,均匀分布到多个存储服务器上。当前,分布式存储有多种实现技术,如HDFS、Ceph、GFS、Switf等。在实际工作中,为了更好地引入分布式存储技术,我们需了解各种分布式存储

tensorflow入门与实践_听雨322的博客-程序员秘密

Tensorflow一些常用基本概念与函数1、tensorflow的基本运作为了快速的熟悉TensorFlow编程,下面从一段简单的代码开始:import tensorflow as tf #定义‘符号’变量,也称为占位符 a = tf.placeholder(&quot;float&quot;) b = tf.placeholder(&quot;float&quot;) y = tf.mul(a, b) #构造一个op节点...

7 赫斯曼网管软件industrial hivision告警事件设置_恋上邻居家的猫咪的博客-程序员秘密

文章目录前言一、事件转发1.Forward events to syslog server2.Event Type3.新建日志服务器设备二、事件操作1.告警提示框设置2.告警音设置3.添加事件类型和动作4.查看效果总结前言当网络有告警事件时,该如何向系统日志服务器发送告警日志?事件告警如何以设置警示框、声音告警、邮件发送告警信息?以下步骤将详细介绍赫斯曼网管软件的告警事件设置。一、事件转发1.Forward events to syslog server通过 “Forward event

推荐文章

热门文章

相关标签