当前位置:首页 > 智能硬件 > 人工智能AI
[导读]   题意:   一共n个位置,每个位置一个属性k[i],表示在i位置会被瞬间转移到i+k[i](然后又依次转移)。问从一个点开始多少次会出界。并且支持修改k[i]。   题解:

  题意:

  一共n个位置,每个位置一个属性k[i],表示在i位置会被瞬间转移到i+k[i](然后又依次转移)。问从一个点开始多少次会出界。并且支持修改k[i]。

  题解:

  把i向i+k[i]连边,若i+k[i]出界就向外面的总根连边。询问就是求深度。

  把一个节点splay到根之后(前提是根是原树最开始的根),左边一定是比它浅的(且一定是它到原树根的一条链(因为access操作)),所以左儿子的size就是它的深度(根的深度为0)。

  居然以前要写一天的LCT半个小时就写好了,要不是BZOJ的编译器栈空间不够就1A了

  /**************************************************************

  Problem: 2002

  User: Lazer2001

  Language: C++

  Result: Accepted

  TIme:1988 ms

  Memory:22324 kb

  ****************************************************************/

  # include 《bits/stdc++.h》

  inline int read ( ) {

  register int x, c ;

  while ( isspace ( c = getchar ( ) ) ) ;

  for ( x = -48 + c ; isdigit ( c = getchar ( ) ) ; ( x *= 10 ) += c - 48 ) ;

  return x ;

  }

  template 《 class T 》 inline T min ( const T& a, const T& b ) { return a 《 b ? a : b ; }

  template 《 class T 》 inline void swap ( T& a, T& b ) { T c ( a ) ; a = b, b = c ; }

  # define N 200010

  class LinkCutTree {

  private :

  struct node {

  int siz ;

  bool rev_flag ;

  node *ch [2], *fa ;

  inline void update ( ) {

  siz = ch [0] -》 siz + ch [1] -》 siz + 1 ;

  }

  } pool [N 《《 1], *root [N], *null ;

  int n ;

  inline void push_down ( node*& p ) {

  if ( p -》 rev_flag ) {

  swap ( p -》 ch [0], p -》 ch [1] ) ;

  if ( p -》 ch [0] != null ) p -》 ch [0] -》 rev_flag ^= 1 ;

  if ( p -》 ch [1] != null ) p -》 ch [1] -》 rev_flag ^= 1 ;

  p -》 rev_flag = 0 ;

  }

  }

  inline node* newnode ( node*& fa ) {

  staTIc node* tp ( pool + 1 ) ;

  tp -》 siz = 1 ; tp -》 rev_flag = 0 ;

  return tp -》 fa = fa, tp -》 ch [0] = tp -》 ch [1] = null, tp ++ ;

  }

  # define isroot( p ) ( p -》 fa == null || ( p -》 fa -》 ch [0] != p && p -》 fa -》 ch [1] != p ) )

  # define isrs( p ) ( p == p -》 fa -》 ch [1] )

  inline void rotate ( node* p ) {

  if ( p == null || isroot ( p ) ) return ;

  bool d ( isrs ( p ) ) ;

  node* par = p -》 fa ;

  par -》 ch [d] = p -》 ch [! d] ;

  if ( p -》 ch [! d] != null ) p -》 ch [! d] -》 fa = par ;

  if ( ! isroot ( par ) ) par -》 fa -》 ch [isrs ( par )] = p ; // !isroot(par)

  p -》 fa = par -》 fa ;

  par -》 fa = p ;

  p -》 ch [! d] = par ;

  par -》 update ( ) ; p -》 update ( ) ;

  }

  node* st [N 《《 1] ;

  inline void splay ( node* p ) {

  if ( p == null ) return ;

  // staTIc node* st [N 《《 1] ; staTIc int tp ( 0 ) ; RE!!!!

  int tp ;

  st [tp = 1] = p ;

  for ( node* t = p ; ! isroot ( t ) ; t = t -》 fa ) st [++ tp] = t -》 fa ;

  while ( tp ) push_down ( st [tp --] ) ;

  while ( ! isroot ( p ) ) {

  if ( isrs ( p ) == isrs ( p -》 fa ) && ! isroot ( p -》 fa ) ) rotate ( p -》 fa ) ;

  rotate ( p ) ;

  }

  }

本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
换一批
延伸阅读

罗德与施瓦茨与SmartViser携手开发了一种用于测试符合欧盟销售的智能手机和平板电脑的新Energy Efficiency Index(EEI)标签法规的解决方案。该解决方案的核心是R&S CMX500,这是...

关键字: 智能手机 Android iOS

(全球TMT2023年8月24日讯)2023年8月23日,时值实时3D引擎Unity在华设立合资公司Unity中国一周年之际,Unity中国正式推出Unity中国版引擎——团结引擎。Unity全球CEO John Ri...

关键字: UNITY CE Android 开发者

报告显示:全球电商 App 获客花费接近50亿美元 北京2023年8月23日 /美通社/ -- 全球营销衡量与体验管理平台 AppsFlyer 近日发布《2023 电商 App 营销现状报告》。尽管面临全球经...

关键字: APPS BSP iOS Android

数字机顶盒是一种数字技术下的多媒体娱乐中心,可以实现电视节目接收、播放、存储、网络应用等多种功能。随着科技的发展,数字机顶盒的设计方案也在不断进步和优化。本文将介绍数字机顶盒设计的几种实现方案。

关键字: 数字机顶盒 Android Linux

21ic 近日获悉,原小米 9 号创始员工李明在社交媒体平台公布了旗下首款产品乐天派桌面机器人,为全球首款 Android 桌面机器人,面向极客和发烧友的 AI + 机器人。据悉,李明两个月前宣布创业并进军 AI 领域,...

关键字: 小米 Android 桌面机器人 AI

尽管安装增长放缓,全球游戏 App 获客花费仍高达 267 亿美元 经济低迷导致 2023 游戏 App 营销优先考虑收入指标,用户增长次之 北京2023年3月9日 /美通社/ -- 今天,全球营销衡量与体验管理平台...

关键字: APPS iOS Android BSP

量子计算领域的新里程碑,来了! 谷歌科学家证明,通过增加量子比特的数量,就能降低量子计算的错误率。

关键字: 谷歌 Android Windows

「卫星通讯」正在被普及到每一台智能手机当中。普及的动机并非是消费市场的一个刚需,其实更像是将差异化的功能「抹平」成一个标配。时下,支持「卫星通讯」功能的智能手机只有苹果的 iPhone 14 系列与华为的 Mate 50...

关键字: 卫星通讯 Android 智能手机 iPhone

Android是Google开发的操作系统,支持多种指令集架构 (ISA),包括Arm和x86,多数使用Android的设备都采用Arm架构芯片组。新兴RISC-V架构是免费开放指令集架构,任何人都可用它设计芯片,且无需...

关键字: 谷歌 Android RISC-V架构

智能手机并非每年都取得重大进展,这导致越来越多的人将手机保留两年、三年或四年。不过,普通的 Android 手机能否在遇到问题之前使用那么久?

关键字: Android 安卓 谷歌 智能手机
关闭
关闭