index.html 32 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947
  1. <!DOCTYPE html>
  2. <html lang="en">
  3. <head>
  4. <meta charset="UTF-8">
  5. <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
  6. <meta name="theme-color" content="#222">
  7. <meta name="generator" content="Hexo 4.2.0">
  8. <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  9. <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
  10. <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
  11. <link rel="mask-icon" href="/images/logo.svg" color="#222">
  12. <link rel="stylesheet" href="/css/main.css">
  13. <link rel="stylesheet" href="/lib/font-awesome/css/font-awesome.min.css">
  14. <link rel="stylesheet" href="/lib/pace/pace-theme-minimal.min.css">
  15. <script src="/lib/pace/pace.min.js"></script>
  16. <script id="hexo-configurations">
  17. var NexT = window.NexT || {};
  18. var CONFIG = {"hostname":"yoursite.com","root":"/","scheme":"Muse","version":"7.7.2","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":true,"show_result":true,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":true},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":false,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideLeftIn"}}};
  19. </script>
  20. <meta property="og:type" content="website">
  21. <meta property="og:title" content="Schtonn&#39;s Blog">
  22. <meta property="og:url" content="http://yoursite.com/index.html">
  23. <meta property="og:site_name" content="Schtonn&#39;s Blog">
  24. <meta property="og:locale" content="en_US">
  25. <meta property="article:author" content="Schtonn">
  26. <meta name="twitter:card" content="summary">
  27. <link rel="canonical" href="http://yoursite.com/">
  28. <script id="page-configurations">
  29. // https://hexo.io/docs/variables.html
  30. CONFIG.page = {
  31. sidebar: "",
  32. isHome : true,
  33. isPost : false
  34. };
  35. </script>
  36. <title>Schtonn's Blog</title>
  37. <noscript>
  38. <style>
  39. .use-motion .brand,
  40. .use-motion .menu-item,
  41. .sidebar-inner,
  42. .use-motion .post-block,
  43. .use-motion .pagination,
  44. .use-motion .comments,
  45. .use-motion .post-header,
  46. .use-motion .post-body,
  47. .use-motion .collection-header { opacity: initial; }
  48. .use-motion .site-title,
  49. .use-motion .site-subtitle {
  50. opacity: initial;
  51. top: initial;
  52. }
  53. .use-motion .logo-line-before i { left: initial; }
  54. .use-motion .logo-line-after i { right: initial; }
  55. </style>
  56. </noscript>
  57. </head>
  58. <body itemscope itemtype="http://schema.org/WebPage">
  59. <div class="container use-motion">
  60. <div class="headband"></div>
  61. <header class="header" itemscope itemtype="http://schema.org/WPHeader">
  62. <div class="header-inner"><div class="site-brand-container">
  63. <div class="site-nav-toggle">
  64. <div class="toggle" aria-label="Toggle navigation bar">
  65. <span class="toggle-line toggle-line-first"></span>
  66. <span class="toggle-line toggle-line-middle"></span>
  67. <span class="toggle-line toggle-line-last"></span>
  68. </div>
  69. </div>
  70. <div class="site-meta">
  71. <div>
  72. <a href="/" class="brand" rel="start">
  73. <span class="logo-line-before"><i></i></span>
  74. <span class="site-title">Schtonn's Blog</span>
  75. <span class="logo-line-after"><i></i></span>
  76. </a>
  77. </div>
  78. <p class="site-subtitle">Schtonn's blog</p>
  79. </div>
  80. <div class="site-nav-right">
  81. <div class="toggle popup-trigger">
  82. </div>
  83. </div>
  84. </div>
  85. <nav class="site-nav">
  86. <ul id="menu" class="menu">
  87. <li class="menu-item menu-item-home">
  88. <a href="/" rel="section"><i class="fa fa-fw fa-home"></i>Home</a>
  89. </li>
  90. <li class="menu-item menu-item-tags">
  91. <a href="/tags/" rel="section"><i class="fa fa-fw fa-tags"></i>Tags</a>
  92. </li>
  93. <li class="menu-item menu-item-archives">
  94. <a href="/archives/" rel="section"><i class="fa fa-fw fa-archive"></i>Archives</a>
  95. </li>
  96. </ul>
  97. </nav>
  98. </div>
  99. </header>
  100. <div class="back-to-top">
  101. <i class="fa fa-arrow-up"></i>
  102. <span>0%</span>
  103. </div>
  104. <div class="reading-progress-bar"></div>
  105. <main class="main">
  106. <div class="main-inner">
  107. <div class="content-wrap">
  108. <div class="content">
  109. <div class="posts-expand">
  110. <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
  111. <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/03/01/plan/">
  112. <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
  113. <meta itemprop="image" content="/images/avatar.gif">
  114. <meta itemprop="name" content="Schtonn">
  115. <meta itemprop="description" content="">
  116. </span>
  117. <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
  118. <meta itemprop="name" content="Schtonn's Blog">
  119. </span>
  120. <header class="post-header">
  121. <h1 class="post-title" itemprop="name headline">
  122. <a href="/2020/03/01/plan/" class="post-title-link" itemprop="url">plan</a>
  123. </h1>
  124. <div class="post-meta">
  125. <i class="fa fa-thumb-tack"></i>
  126. <font color=7D26CD>Top</font>
  127. <span class="post-meta-divider">|</span>
  128. <span class="post-meta-item">
  129. <span class="post-meta-item-icon">
  130. <i class="fa fa-calendar-o"></i>
  131. </span>
  132. <span class="post-meta-item-text">Posted on</span>
  133. <time title="Created: 2020-Mar-01 22:36:07" itemprop="dateCreated datePublished" datetime="2020-03-01T22:36:07+08:00">2020-Mar-01</time>
  134. </span>
  135. <span class="post-meta-item">
  136. <span class="post-meta-item-icon">
  137. <i class="fa fa-calendar-check-o"></i>
  138. </span>
  139. <span class="post-meta-item-text">Edited on</span>
  140. <time title="Modified: 2020-Mar-03 20:40:32" itemprop="dateModified" datetime="2020-03-03T20:40:32+08:00">2020-Mar-03</time>
  141. </span>
  142. </div>
  143. </header>
  144. <div class="post-body" itemprop="articleBody">
  145. <h3 id="薄弱项">薄弱项</h3>
  146. <ol type="1">
  147. <li><strong>作文</strong>
  148. <ol type="1">
  149. <li>写日记
  150. <ul>
  151. <li>每天固定 9:00-9:30</li>
  152. <li>内容不必精美</li>
  153. <li>一周写五天,两天机动</li>
  154. </ul></li>
  155. <li>读书
  156. <ul>
  157. <li>作文辅导书为主 <code>作文大全等</code></li>
  158. <li>其他书籍为辅</li>
  159. </ul></li>
  160. <li>录音</li>
  161. </ol></li>
  162. </ol>
  163. <!--noindex-->
  164. <div class="post-button">
  165. <a class="btn" href="/2020/03/01/plan/#more" rel="contents">
  166. Read more &raquo;
  167. </a>
  168. </div>
  169. <!--/noindex-->
  170. </div>
  171. <footer class="post-footer">
  172. <div class="post-eof"></div>
  173. </footer>
  174. </article>
  175. <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
  176. <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/03/02/segment-tree/">
  177. <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
  178. <meta itemprop="image" content="/images/avatar.gif">
  179. <meta itemprop="name" content="Schtonn">
  180. <meta itemprop="description" content="">
  181. </span>
  182. <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
  183. <meta itemprop="name" content="Schtonn's Blog">
  184. </span>
  185. <header class="post-header">
  186. <h1 class="post-title" itemprop="name headline">
  187. <a href="/2020/03/02/segment-tree/" class="post-title-link" itemprop="url">线段树</a>
  188. </h1>
  189. <div class="post-meta">
  190. <span class="post-meta-item">
  191. <span class="post-meta-item-icon">
  192. <i class="fa fa-calendar-o"></i>
  193. </span>
  194. <span class="post-meta-item-text">Posted on</span>
  195. <time title="Created: 2020-Mar-02 11:37:36" itemprop="dateCreated datePublished" datetime="2020-03-02T11:37:36+08:00">2020-Mar-02</time>
  196. </span>
  197. <span class="post-meta-item">
  198. <span class="post-meta-item-icon">
  199. <i class="fa fa-calendar-check-o"></i>
  200. </span>
  201. <span class="post-meta-item-text">Edited on</span>
  202. <time title="Modified: 2020-Mar-03 20:40:21" itemprop="dateModified" datetime="2020-03-03T20:40:21+08:00">2020-Mar-03</time>
  203. </span>
  204. </div>
  205. </header>
  206. <div class="post-body" itemprop="articleBody">
  207. <h3 id="前置知识">前置知识</h3>
  208. <p>数组,结构体,二叉树</p>
  209. <h3 id="引入">引入</h3>
  210. <p>有时候我们会遇到一些大规模的区间查找和区间修改问题,比如让你维护一个 <span class="math inline">\(10^5\)</span> 长度的数列,要求操作有区间求和、区间加(区间每个数加上一个值),让你在一秒内完成 <span class="math inline">\(10^5\)</span> 次操作。 暴力是肯定不行的,数据范围太大,会超时。 所以我们就有一种专门解决大范围区间修改查询的数据结构:线段树。</p>
  211. <!--noindex-->
  212. <div class="post-button">
  213. <a class="btn" href="/2020/03/02/segment-tree/#more" rel="contents">
  214. Read more &raquo;
  215. </a>
  216. </div>
  217. <!--/noindex-->
  218. </div>
  219. <footer class="post-footer">
  220. <div class="post-eof"></div>
  221. </footer>
  222. </article>
  223. <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
  224. <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/03/02/ferbonacci/">
  225. <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
  226. <meta itemprop="image" content="/images/avatar.gif">
  227. <meta itemprop="name" content="Schtonn">
  228. <meta itemprop="description" content="">
  229. </span>
  230. <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
  231. <meta itemprop="name" content="Schtonn's Blog">
  232. </span>
  233. <header class="post-header">
  234. <h1 class="post-title" itemprop="name headline">
  235. <a href="/2020/03/02/ferbonacci/" class="post-title-link" itemprop="url">斐波那契数列-O(1)</a>
  236. </h1>
  237. <div class="post-meta">
  238. <span class="post-meta-item">
  239. <span class="post-meta-item-icon">
  240. <i class="fa fa-calendar-o"></i>
  241. </span>
  242. <span class="post-meta-item-text">Posted on</span>
  243. <time title="Created: 2020-Mar-02 11:35:44" itemprop="dateCreated datePublished" datetime="2020-03-02T11:35:44+08:00">2020-Mar-02</time>
  244. </span>
  245. <span class="post-meta-item">
  246. <span class="post-meta-item-icon">
  247. <i class="fa fa-calendar-check-o"></i>
  248. </span>
  249. <span class="post-meta-item-text">Edited on</span>
  250. <time title="Modified: 2020-Mar-03 20:40:56" itemprop="dateModified" datetime="2020-03-03T20:40:56+08:00">2020-Mar-03</time>
  251. </span>
  252. </div>
  253. </header>
  254. <div class="post-body" itemprop="articleBody">
  255. <p>引自:《信息学奥赛之-数学一本通》 揍是这样: <span class="math display">\[\operatorname{F}(n)=\dfrac{\sqrt{5}}{5}\cdot\left[\left(1+\sqrt{5}\right)^n-\left(1-\sqrt{5}\right)^n\right]\]</span> 代码揍这么简单: <figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">ferbo</span><span class="params">(<span class="keyword">int</span> n)</span></span>&#123;</span><br><span class="line"> <span class="keyword">return</span> (<span class="built_in">sqrt</span>(<span class="number">5</span>)/<span class="number">5</span>)*(<span class="built_in">pow</span>((<span class="number">1</span>+<span class="built_in">sqrt</span>(<span class="number">5</span>))/<span class="number">2</span>,n)-<span class="built_in">pow</span>((<span class="number">1</span>-<span class="built_in">sqrt</span>(<span class="number">5</span>))/<span class="number">2</span>,n));</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure> 要是再加个快速幂就更棒了(够快了,懒得写)</p>
  256. </div>
  257. <footer class="post-footer">
  258. <div class="post-eof"></div>
  259. </footer>
  260. </article>
  261. <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
  262. <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/03/02/dinic/">
  263. <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
  264. <meta itemprop="image" content="/images/avatar.gif">
  265. <meta itemprop="name" content="Schtonn">
  266. <meta itemprop="description" content="">
  267. </span>
  268. <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
  269. <meta itemprop="name" content="Schtonn's Blog">
  270. </span>
  271. <header class="post-header">
  272. <h1 class="post-title" itemprop="name headline">
  273. <a href="/2020/03/02/dinic/" class="post-title-link" itemprop="url">网络最大流-Dinic</a>
  274. </h1>
  275. <div class="post-meta">
  276. <span class="post-meta-item">
  277. <span class="post-meta-item-icon">
  278. <i class="fa fa-calendar-o"></i>
  279. </span>
  280. <span class="post-meta-item-text">Posted on</span>
  281. <time title="Created: 2020-Mar-02 11:31:22" itemprop="dateCreated datePublished" datetime="2020-03-02T11:31:22+08:00">2020-Mar-02</time>
  282. </span>
  283. <span class="post-meta-item">
  284. <span class="post-meta-item-icon">
  285. <i class="fa fa-calendar-check-o"></i>
  286. </span>
  287. <span class="post-meta-item-text">Edited on</span>
  288. <time title="Modified: 2020-Mar-03 20:41:19" itemprop="dateModified" datetime="2020-03-03T20:41:19+08:00">2020-Mar-03</time>
  289. </span>
  290. </div>
  291. </header>
  292. <div class="post-body" itemprop="articleBody">
  293. <h3 id="前置知识">前置知识</h3>
  294. <p>存图方式(<a href="http://baidu.physton.com/?q=邻接表" target="_blank" rel="noopener" title="简单">邻接表</a>,<a href="http://baidu.physton.com/?q=邻接矩阵" target="_blank" rel="noopener" title="都太简单了">邻接矩阵</a>),图的遍历(<a href="http://baidu.physton.com/?q=dfs" target="_blank" rel="noopener" title="简单">dfs</a>,<a href="http://baidu.physton.com/?q=bfs" target="_blank" rel="noopener" title="简单">bfs</a>)</p>
  295. <h3 id="引入">引入</h3>
  296. <p>我们举个例子吧: 有一个毒瘤水管工,他会造水管,有一天他造了一个水管网络,就像一个图。其中有一个点只有出边,就是起点,还有一个点只有入边,是终点。 点之间有一些管子,这些管子都有单位时间内的容量,现在毒瘤水管工想知道,他的管子在<strong>单位时间内</strong>在起点终点之间最多能流多少水。
  297. <!--noindex-->
  298. <div class="post-button">
  299. <a class="btn" href="/2020/03/02/dinic/#more" rel="contents">
  300. Read more &raquo;
  301. </a>
  302. </div>
  303. <!--/noindex-->
  304. </div>
  305. <footer class="post-footer">
  306. <div class="post-eof"></div>
  307. </footer>
  308. </article>
  309. <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
  310. <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/03/01/min-span-tree/">
  311. <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
  312. <meta itemprop="image" content="/images/avatar.gif">
  313. <meta itemprop="name" content="Schtonn">
  314. <meta itemprop="description" content="">
  315. </span>
  316. <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
  317. <meta itemprop="name" content="Schtonn's Blog">
  318. </span>
  319. <header class="post-header">
  320. <h1 class="post-title" itemprop="name headline">
  321. <a href="/2020/03/01/min-span-tree/" class="post-title-link" itemprop="url">最小生成树</a>
  322. </h1>
  323. <div class="post-meta">
  324. <span class="post-meta-item">
  325. <span class="post-meta-item-icon">
  326. <i class="fa fa-calendar-o"></i>
  327. </span>
  328. <span class="post-meta-item-text">Posted on</span>
  329. <time title="Created: 2020-Mar-01 22:45:44" itemprop="dateCreated datePublished" datetime="2020-03-01T22:45:44+08:00">2020-Mar-01</time>
  330. </span>
  331. <span class="post-meta-item">
  332. <span class="post-meta-item-icon">
  333. <i class="fa fa-calendar-check-o"></i>
  334. </span>
  335. <span class="post-meta-item-text">Edited on</span>
  336. <time title="Modified: 2020-Mar-04 09:11:55" itemprop="dateModified" datetime="2020-03-04T09:11:55+08:00">2020-Mar-04</time>
  337. </span>
  338. </div>
  339. </header>
  340. <div class="post-body" itemprop="articleBody">
  341. <h3 id="前置知识">前置知识</h3>
  342. <p>存图方式(<a href="http://baidu.physton.com/?q=邻接表" target="_blank" rel="noopener" title="简单">邻接表</a>,<a href="http://baidu.physton.com/?q=邻接矩阵" target="_blank" rel="noopener" title="都太简单了,没有一个打得过的">邻接矩阵</a>),<a href="https://schtonn.github.io/2020/03/01/union-find" target="_blank" rel="noopener">并查集</a>。 不会的快进入链接学习吧!</p>
  343. <h3 id="引入">引入</h3>
  344. <p>生成树,就是从一个图中选中<span class="math inline">\(n-1\)</span>条边,使得这些边构成一棵树,并包含图中的所有节点。 最小生成树,就是找到一种生成树,使得这个生成树的边权和最小。
  345. <!--noindex-->
  346. <div class="post-button">
  347. <a class="btn" href="/2020/03/01/min-span-tree/#more" rel="contents">
  348. Read more &raquo;
  349. </a>
  350. </div>
  351. <!--/noindex-->
  352. </div>
  353. <footer class="post-footer">
  354. <div class="post-eof"></div>
  355. </footer>
  356. </article>
  357. <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
  358. <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/03/01/union-find/">
  359. <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
  360. <meta itemprop="image" content="/images/avatar.gif">
  361. <meta itemprop="name" content="Schtonn">
  362. <meta itemprop="description" content="">
  363. </span>
  364. <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
  365. <meta itemprop="name" content="Schtonn's Blog">
  366. </span>
  367. <header class="post-header">
  368. <h1 class="post-title" itemprop="name headline">
  369. <a href="/2020/03/01/union-find/" class="post-title-link" itemprop="url">并查集</a>
  370. </h1>
  371. <div class="post-meta">
  372. <span class="post-meta-item">
  373. <span class="post-meta-item-icon">
  374. <i class="fa fa-calendar-o"></i>
  375. </span>
  376. <span class="post-meta-item-text">Posted on</span>
  377. <time title="Created: 2020-Mar-01 22:44:33" itemprop="dateCreated datePublished" datetime="2020-03-01T22:44:33+08:00">2020-Mar-01</time>
  378. </span>
  379. <span class="post-meta-item">
  380. <span class="post-meta-item-icon">
  381. <i class="fa fa-calendar-check-o"></i>
  382. </span>
  383. <span class="post-meta-item-text">Edited on</span>
  384. <time title="Modified: 2020-Mar-03 20:39:35" itemprop="dateModified" datetime="2020-03-03T20:39:35+08:00">2020-Mar-03</time>
  385. </span>
  386. </div>
  387. </header>
  388. <div class="post-body" itemprop="articleBody">
  389. <h3 id="前置知识">前置知识</h3>
  390. <p>哈哈,简单到爆,没有。</p>
  391. <h3 id="引入">引入</h3>
  392. <p>并查集是一种快到爆炸的集合算法,可以进行两项基本操作:合并两个集合(并)、查询两个参数是否在一个集合内(查)。这也是它名字的由来。
  393. <!--noindex-->
  394. <div class="post-button">
  395. <a class="btn" href="/2020/03/01/union-find/#more" rel="contents">
  396. Read more &raquo;
  397. </a>
  398. </div>
  399. <!--/noindex-->
  400. </div>
  401. <footer class="post-footer">
  402. <div class="post-eof"></div>
  403. </footer>
  404. </article>
  405. <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
  406. <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/03/01/tree-link/">
  407. <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
  408. <meta itemprop="image" content="/images/avatar.gif">
  409. <meta itemprop="name" content="Schtonn">
  410. <meta itemprop="description" content="">
  411. </span>
  412. <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
  413. <meta itemprop="name" content="Schtonn's Blog">
  414. </span>
  415. <header class="post-header">
  416. <h1 class="post-title" itemprop="name headline">
  417. <a href="/2020/03/01/tree-link/" class="post-title-link" itemprop="url">树链剖分</a>
  418. </h1>
  419. <div class="post-meta">
  420. <span class="post-meta-item">
  421. <span class="post-meta-item-icon">
  422. <i class="fa fa-calendar-o"></i>
  423. </span>
  424. <span class="post-meta-item-text">Posted on</span>
  425. <time title="Created: 2020-Mar-01 22:41:02" itemprop="dateCreated datePublished" datetime="2020-03-01T22:41:02+08:00">2020-Mar-01</time>
  426. </span>
  427. <span class="post-meta-item">
  428. <span class="post-meta-item-icon">
  429. <i class="fa fa-calendar-check-o"></i>
  430. </span>
  431. <span class="post-meta-item-text">Edited on</span>
  432. <time title="Modified: 2020-Mar-03 20:39:51" itemprop="dateModified" datetime="2020-03-03T20:39:51+08:00">2020-Mar-03</time>
  433. </span>
  434. </div>
  435. </header>
  436. <div class="post-body" itemprop="articleBody">
  437. <h3 id="前置知识">前置知识</h3>
  438. <p>必备:存图方式(<a href="http://baidu.physton.com/?q=邻接表" target="_blank" rel="noopener" title="简单">邻接表</a>,<a href="http://baidu.physton.com/?q=邻接矩阵" target="_blank" rel="noopener" title="都太简单了,没有一个打得过的">邻接矩阵</a>),<a href="http://baidu.physton.com/?q=dfs%E5%BA%8F" target="_blank" rel="noopener">dfs序</a>。 维护:<a href="http://baidu.physton.com/?q=%E7%BA%BF%E6%AE%B5%E6%A0%91" target="_blank" rel="noopener">线段树</a>、<a href="http://baidu.physton.com/?q=%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84" target="_blank" rel="noopener">树状数组</a>、<a href="http://baidu.physton.com/?q=BST" target="_blank" rel="noopener">BST</a>。 不会的快进入链接学习吧!</p>
  439. <h3 id="引入">引入</h3>
  440. <p>树链剖分,简单来说就是把树分割成链,然后维护每一条链。一般的维护算法有线段树,树状数组和BST。复杂度为<span class="math inline">\(O(log n)\)</span>。
  441. <!--noindex-->
  442. <div class="post-button">
  443. <a class="btn" href="/2020/03/01/tree-link/#more" rel="contents">
  444. Read more &raquo;
  445. </a>
  446. </div>
  447. <!--/noindex-->
  448. </div>
  449. <footer class="post-footer">
  450. <div class="post-eof"></div>
  451. </footer>
  452. </article>
  453. <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
  454. <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/03/01/test/">
  455. <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
  456. <meta itemprop="image" content="/images/avatar.gif">
  457. <meta itemprop="name" content="Schtonn">
  458. <meta itemprop="description" content="">
  459. </span>
  460. <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
  461. <meta itemprop="name" content="Schtonn's Blog">
  462. </span>
  463. <header class="post-header">
  464. <h1 class="post-title" itemprop="name headline">
  465. <a href="/2020/03/01/test/" class="post-title-link" itemprop="url">test</a>
  466. </h1>
  467. <div class="post-meta">
  468. <span class="post-meta-item">
  469. <span class="post-meta-item-icon">
  470. <i class="fa fa-calendar-o"></i>
  471. </span>
  472. <span class="post-meta-item-text">Posted on</span>
  473. <time title="Created: 2020-Mar-01 11:06:43" itemprop="dateCreated datePublished" datetime="2020-03-01T11:06:43+08:00">2020-Mar-01</time>
  474. </span>
  475. <span class="post-meta-item">
  476. <span class="post-meta-item-icon">
  477. <i class="fa fa-calendar-check-o"></i>
  478. </span>
  479. <span class="post-meta-item-text">Edited on</span>
  480. <time title="Modified: 2020-Mar-03 20:40:09" itemprop="dateModified" datetime="2020-03-03T20:40:09+08:00">2020-Mar-03</time>
  481. </span>
  482. </div>
  483. </header>
  484. <div class="post-body" itemprop="articleBody">
  485. <p><span class="math inline">\(\texttt{Is KaTeX working?-IT WORKED!NICE!}\)</span> <span class="math display">\[a^b\]</span> <span class="math display">\[\left(\dfrac{a}{b}\right)\]</span></p>
  486. </div>
  487. <footer class="post-footer">
  488. <div class="post-eof"></div>
  489. </footer>
  490. </article>
  491. </div>
  492. </div>
  493. <script>
  494. window.addEventListener('tabs:register', () => {
  495. let activeClass = CONFIG.comments.activeClass;
  496. if (CONFIG.comments.storage) {
  497. activeClass = localStorage.getItem('comments_active') || activeClass;
  498. }
  499. if (activeClass) {
  500. let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
  501. if (activeTab) {
  502. activeTab.click();
  503. }
  504. }
  505. });
  506. if (CONFIG.comments.storage) {
  507. window.addEventListener('tabs:click', event => {
  508. if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
  509. let commentClass = event.target.classList[1];
  510. localStorage.setItem('comments_active', commentClass);
  511. });
  512. }
  513. </script>
  514. </div>
  515. <div class="toggle sidebar-toggle">
  516. <span class="toggle-line toggle-line-first"></span>
  517. <span class="toggle-line toggle-line-middle"></span>
  518. <span class="toggle-line toggle-line-last"></span>
  519. </div>
  520. <aside class="sidebar">
  521. <div class="sidebar-inner">
  522. <ul class="sidebar-nav motion-element">
  523. <li class="sidebar-nav-toc">
  524. Table of Contents
  525. </li>
  526. <li class="sidebar-nav-overview">
  527. Overview
  528. </li>
  529. </ul>
  530. <!--noindex-->
  531. <div class="post-toc-wrap sidebar-panel">
  532. </div>
  533. <!--/noindex-->
  534. <div class="site-overview-wrap sidebar-panel">
  535. <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
  536. <p class="site-author-name" itemprop="name">Schtonn</p>
  537. <div class="site-description" itemprop="description"></div>
  538. </div>
  539. <div class="site-state-wrap motion-element">
  540. <nav class="site-state">
  541. <div class="site-state-item site-state-posts">
  542. <a href="/archives/">
  543. <span class="site-state-item-count">8</span>
  544. <span class="site-state-item-name">posts</span>
  545. </a>
  546. </div>
  547. <div class="site-state-item site-state-tags">
  548. <a href="/tags/">
  549. <span class="site-state-item-count">4</span>
  550. <span class="site-state-item-name">tags</span></a>
  551. </div>
  552. </nav>
  553. </div>
  554. <div class="links-of-blogroll motion-element">
  555. <div class="links-of-blogroll-title">
  556. <i class="fa fa-fw fa-link"></i>
  557. Links
  558. </div>
  559. <ul class="links-of-blogroll-list">
  560. <li class="links-of-blogroll-item">
  561. <a href="https://yonghong.github.io/" title="https:&#x2F;&#x2F;yonghong.github.io" rel="noopener" target="_blank">Yonghong</a>
  562. </li>
  563. </ul>
  564. </div>
  565. </div>
  566. <div id="treefrog" style="text-align: center;margin-top: 18px;">
  567. <object type="application/x-shockwave-flash" style="outline:none;" data="/js/treefrog.swf?up_bodyColor=444444&up_pattern=0&up_flyColor=777777&up_tongueColor=555555&up_patternColor=000000&up_releaseFly=0&up_frogName=Froggie&up_backgroundImage=http://&up_bellySize=.5&up_footColor=444444&up_eyeColor=444444&up_backgroundColor=222222&" width="300" height="600"><param name="movie" value="http://cdn.abowman.com/widgets/treefrog/treefrog.swf?up_bodyColor=444444&up_pattern=0&up_flyColor=777777&up_tongueColor=555555&up_patternColor=000000&up_releaseFly=0&up_frogName=Froggie&up_backgroundImage=http://&up_bellySize=.5&up_footColor=444444&up_eyeColor=444444&up_backgroundColor=222222&"></param><param name="AllowScriptAccess" value="always"></param><param name="wmode" value="opaque"></param><param name="scale" value="noscale"/><param name="salign" value="tl"/></object>
  568. </div>
  569. </div>
  570. </aside>
  571. <div id="sidebar-dimmer"></div>
  572. </div>
  573. </main>
  574. <footer class="footer">
  575. <div class="footer-inner">
  576. <div class="copyright">
  577. &copy;
  578. <span itemprop="copyrightYear">2020</span>
  579. <span class="with-love">
  580. <i class="fa fa-user"></i>
  581. </span>
  582. <span class="author" itemprop="copyrightHolder">Alex Xiang</span>
  583. </div>
  584. <div class="powered-by">Powered by <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a>
  585. </div>
  586. <span class="post-meta-divider">|</span>
  587. <div class="theme-info">Theme – <a href="https://muse.theme-next.org/" class="theme-link" rel="noopener" target="_blank">NexT.Muse</a>
  588. </div>
  589. </div>
  590. </footer>
  591. </div>
  592. <script src="/lib/anime.min.js"></script>
  593. <script src="/lib/velocity/velocity.min.js"></script>
  594. <script src="/lib/velocity/velocity.ui.min.js"></script>
  595. <script src="/js/utils.js"></script>
  596. <script src="/js/motion.js"></script>
  597. <script src="/js/schemes/muse.js"></script>
  598. <script src="/js/next-boot.js"></script>
  599. <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/katex@0/dist/katex.min.css">
  600. </body>
  601. </html>