schtonn
/
public


			
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293
							<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 4.2.0">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">


<link rel="stylesheet" href="/lib/font-awesome/css/font-awesome.min.css">
  <link rel="stylesheet" href="/lib/pace/pace-theme-minimal.min.css">
  <script src="/lib/pace/pace.min.js"></script>

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"schtonn.github.io","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":"flat"},"back2top":{"enable":true,"sidebar":false,"scrollpercent":true},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":true,"pangu":false,"comments":{"style":"tabs","active":"valine","storage":true,"lazyload":false,"nav":null,"activeClass":"valine"},"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"}}};
  </script>

  <meta name="description" content="The blog of a middle school OIer">
<meta property="og:type" content="website">
<meta property="og:title" content="Alex&#39;s Blog">
<meta property="og:url" content="https://schtonn.github.io/index.html">
<meta property="og:site_name" content="Alex&#39;s Blog">
<meta property="og:description" content="The blog of a middle school OIer">
<meta property="og:locale" content="en_US">
<meta property="article:author" content="Alex">
<meta name="twitter:card" content="summary">

<link rel="canonical" href="https://schtonn.github.io/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : true,
    isPost : false
  };
</script>

  <title>Alex's Blog</title>
  

  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="Toggle navigation bar">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <div>
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">Alex's Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
        <p class="site-subtitle">Middle school OIer</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
    </div>
  </div>
</div>


<nav class="site-nav">
  
  <ul id="menu" class="menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-fw fa-home"></i>Home</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="fa fa-fw fa-tags"></i>Tags</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="fa fa-fw fa-archive"></i>Archives</a>

  </li>
        <li class="menu-item menu-item-games">

    <a href="/games/" rel="section"><i class="fa fa-fw fa-gamepad"></i>games</a>

  </li>
        <li class="menu-item menu-item-sans">

    <a href="/sans/" rel="section"><i class="fa fa-fw fa-heart"></i>sans</a>

  </li>
  </ul>

</nav>
</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>
  <div class="reading-progress-bar"></div>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content">
            

  <div class="posts-expand">
        
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
    <link itemprop="mainEntityOfPage" href="https://schtonn.github.io/posts/2020/plan/">
<script>
    (function(){
        if(''){
            if (prompt('Password?') !== ''){
                alert('GOAWAY!');
                history.back();
            }
        }
    })();
</script>

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Alex">
      <meta itemprop="description" content="The blog of a middle school OIer">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Alex's Blog">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          
            <a href="/posts/2020/plan/" class="post-title-link" itemprop="url">plan</a>
        </h1>

        <div class="post-meta">
          
          
            <i class="fa fa-thumb-tack"></i>
            <font color=7D26CD>Pinned</font>
            <span class="post-meta-divider">|</span>
          
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">Posted on</span>

              <time title="Created: 2020-Mar-01 22:36:07" itemprop="dateCreated datePublished" datetime="2020-03-01T22:36:07+08:00">2020-Mar-01</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                <span class="post-meta-item-text">Edited on</span>
                <time title="Modified: 2020-Mar-21 22:17:17" itemprop="dateModified" datetime="2020-03-21T22:17:17+08:00">2020-Mar-21</time>
              </span>

          
        </div>
      </header>

    
    <div class="post-body" itemprop="articleBody">

      
          <p>This page is locked.</p>
          <!--noindex-->
            <div class="post-button">
              <a class="btn" href="/posts/2020/plan/#more" rel="contents">
                Read more &raquo;
              </a>
            </div>
          <!--/noindex-->
        
      
    </div>

    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
    <link itemprop="mainEntityOfPage" href="https://schtonn.github.io/posts/2020/matrix-pow/">
<script>
    (function(){
        if(''){
            if (prompt('Password?') !== ''){
                alert('GOAWAY!');
                history.back();
            }
        }
    })();
</script>

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Alex">
      <meta itemprop="description" content="The blog of a middle school OIer">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Alex's Blog">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          
            <a href="/posts/2020/matrix-pow/" class="post-title-link" itemprop="url">矩阵快速幂运用</a>
        </h1>

        <div class="post-meta">
          
          
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">Posted on</span>
              

              <time title="Created: 2020-Mar-21 19:20:08 / Modified: 22:47:29" itemprop="dateCreated datePublished" datetime="2020-03-21T19:20:08+08:00">2020-Mar-21</time>
            </span>

          
        </div>
      </header>

    
    <div class="post-body" itemprop="articleBody">

      
          <h3 id="引入"><a class="markdownIt-Anchor" href="#引入"></a> 引入</h3>
<p>想要了解矩阵快速幂，就不得不提到矩阵的概念。矩阵就像一个二维数组，存储了一组数据，如：</p>
<p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>M</mi><mo>=</mo><mrow><mo fence="true">[</mo><mtable rowspacing="0.15999999999999992em" columnspacing="1em"><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>1</mn></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>2</mn></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>3</mn></mstyle></mtd></mtr><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>4</mn></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>5</mn></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>6</mn></mstyle></mtd></mtr><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>7</mn></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>8</mn></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>9</mn></mstyle></mtd></mtr></mtable><mo fence="true">]</mo></mrow></mrow><annotation encoding="application/x-tex">M=\left[
 \begin{matrix}
  1&amp;2&amp;3\\
  4&amp;5&amp;6\\
  7&amp;8&amp;9\end{matrix}
\right]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.68333em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.10903em;">M</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:3.60004em;vertical-align:-1.55002em;"></span><span class="minner"><span class="mopen"><span class="delimsizing mult"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:2.05002em;"><span style="top:-2.2500000000000004em;"><span class="pstrut" style="height:3.1550000000000002em;"></span><span class="delimsizinginner delim-size4"><span>⎣</span></span></span><span style="top:-4.05002em;"><span class="pstrut" style="height:3.1550000000000002em;"></span><span class="delimsizinginner delim-size4"><span>⎡</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:1.55002em;"><span></span></span></span></span></span></span><span class="mord"><span class="mtable"><span class="col-align-c"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:2.05em;"><span style="top:-4.21em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">1</span></span></span><span style="top:-3.0099999999999993em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">4</span></span></span><span style="top:-1.8099999999999994em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">7</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:1.5500000000000007em;"><span></span></span></span></span></span><span class="arraycolsep" style="width:0.5em;"></span><span class="arraycolsep" style="width:0.5em;"></span><span class="col-align-c"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:2.05em;"><span style="top:-4.21em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">2</span></span></span><span style="top:-3.0099999999999993em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">5</span></span></span><span style="top:-1.8099999999999994em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">8</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:1.5500000000000007em;"><span></span></span></span></span></span><span class="arraycolsep" style="width:0.5em;"></span><span class="arraycolsep" style="width:0.5em;"></span><span class="col-align-c"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:2.05em;"><span style="top:-4.21em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">3</span></span></span><span style="top:-3.0099999999999993em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">6</span></span></span><span style="top:-1.8099999999999994em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">9</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:1.5500000000000007em;"><span></span></span></span></span></span></span></span><span class="mclose"><span class="delimsizing mult"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:2.05002em;"><span style="top:-2.2500000000000004em;"><span class="pstrut" style="height:3.1550000000000002em;"></span><span class="delimsizinginner delim-size4"><span>⎦</span></span></span><span style="top:-4.05002em;"><span class="pstrut" style="height:3.1550000000000002em;"></span><span class="delimsizinginner delim-size4"><span>⎤</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:1.55002em;"><span></span></span></span></span></span></span></span></span></span></span></span></p>
<p>用 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>M</mi><mrow><mi>i</mi><mi>j</mi></mrow></msub></mrow><annotation encoding="application/x-tex">M_{ij}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.969438em;vertical-align:-0.286108em;"></span><span class="mord"><span class="mord mathdefault" style="margin-right:0.10903em;">M</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.311664em;"><span style="top:-2.5500000000000003em;margin-left:-0.10903em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight">i</span><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.286108em;"><span></span></span></span></span></span></span></span></span></span> 表示矩阵第 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.65952em;vertical-align:0em;"></span><span class="mord mathdefault">i</span></span></span></span> 行第 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span></span></span></span> 列的数据，如 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>M</mi><mn>23</mn></msub><mo>=</mo><mn>6</mn></mrow><annotation encoding="application/x-tex">M_{23}=6</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathdefault" style="margin-right:0.10903em;">M</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.10903em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span><span class="mord mtight">3</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">6</span></span></span></span>。</p>
          <!--noindex-->
            <div class="post-button">
              <a class="btn" href="/posts/2020/matrix-pow/#more" rel="contents">
                Read more &raquo;
              </a>
            </div>
          <!--/noindex-->
        
      
    </div>

    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
    <link itemprop="mainEntityOfPage" href="https://schtonn.github.io/posts/2020/computer/">
<script>
    (function(){
        if(''){
            if (prompt('Password?') !== ''){
                alert('GOAWAY!');
                history.back();
            }
        }
    })();
</script>

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Alex">
      <meta itemprop="description" content="The blog of a middle school OIer">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Alex's Blog">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          
            <a href="/posts/2020/computer/" class="post-title-link" itemprop="url">How do computers work?</a>
        </h1>

        <div class="post-meta">
          
          
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">Posted on</span>

              <time title="Created: 2020-Mar-04 12:53:05" itemprop="dateCreated datePublished" datetime="2020-03-04T12:53:05+08:00">2020-Mar-04</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                <span class="post-meta-item-text">Edited on</span>
                <time title="Modified: 2020-Mar-25 21:41:26" itemprop="dateModified" datetime="2020-03-25T21:41:26+08:00">2020-Mar-25</time>
              </span>

          
        </div>
      </header>

    
    <div class="post-body" itemprop="articleBody">

      
          <p>This page is locked</p>
          <!--noindex-->
            <div class="post-button">
              <a class="btn" href="/posts/2020/computer/#more" rel="contents">
                Read more &raquo;
              </a>
            </div>
          <!--/noindex-->
        
      
    </div>

    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
    <link itemprop="mainEntityOfPage" href="https://schtonn.github.io/posts/2020/segment-tree/">
<script>
    (function(){
        if(''){
            if (prompt('Password?') !== ''){
                alert('GOAWAY!');
                history.back();
            }
        }
    })();
</script>

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Alex">
      <meta itemprop="description" content="The blog of a middle school OIer">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Alex's Blog">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          
            <a href="/posts/2020/segment-tree/" class="post-title-link" itemprop="url">线段树</a>
        </h1>

        <div class="post-meta">
          
          
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">Posted on</span>

              <time title="Created: 2020-Mar-02 11:37:36" itemprop="dateCreated datePublished" datetime="2020-03-02T11:37:36+08:00">2020-Mar-02</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                <span class="post-meta-item-text">Edited on</span>
                <time title="Modified: 2020-Mar-06 18:43:32" itemprop="dateModified" datetime="2020-03-06T18:43:32+08:00">2020-Mar-06</time>
              </span>

          
        </div>
      </header>

    
    <div class="post-body" itemprop="articleBody">

      
          <h3 id="前置知识"><a class="markdownIt-Anchor" href="#前置知识"></a> 前置知识</h3>
<p>数组，结构体，二叉树</p>
<h3 id="引入"><a class="markdownIt-Anchor" href="#引入"></a> 引入</h3>
<p>有时候我们会遇到一些大规模的区间查找和区间修改问题，比如让你维护一个 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup></mrow><annotation encoding="application/x-tex">10^5</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">5</span></span></span></span></span></span></span></span></span></span></span> 长度的数列，要求操作有区间求和、区间加（区间每个数加上一个值），让你在一秒内完成 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup></mrow><annotation encoding="application/x-tex">10^5</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">5</span></span></span></span></span></span></span></span></span></span></span> 次操作。<br />
暴力是肯定不行的，数据范围太大，操作太多，会超时。<br />
所以我们就有一种专门解决大范围区间修改查询的数据结构：线段树。</p>
          <!--noindex-->
            <div class="post-button">
              <a class="btn" href="/posts/2020/segment-tree/#more" rel="contents">
                Read more &raquo;
              </a>
            </div>
          <!--/noindex-->
        
      
    </div>

    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
    <link itemprop="mainEntityOfPage" href="https://schtonn.github.io/posts/2020/ferbonacci/">
<script>
    (function(){
        if(''){
            if (prompt('Password?') !== ''){
                alert('GOAWAY!');
                history.back();
            }
        }
    })();
</script>

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Alex">
      <meta itemprop="description" content="The blog of a middle school OIer">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Alex's Blog">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          
            <a href="/posts/2020/ferbonacci/" class="post-title-link" itemprop="url">斐波那契数列-O(1)</a>
        </h1>

        <div class="post-meta">
          
          
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">Posted on</span>

              <time title="Created: 2020-Mar-02 11:35:44" itemprop="dateCreated datePublished" datetime="2020-03-02T11:35:44+08:00">2020-Mar-02</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                <span class="post-meta-item-text">Edited on</span>
                <time title="Modified: 2020-Mar-03 20:40:56" itemprop="dateModified" datetime="2020-03-03T20:40:56+08:00">2020-Mar-03</time>
              </span>

          
        </div>
      </header>

    
    <div class="post-body" itemprop="articleBody">

      
          <p>引自：《信息学奥赛之-数学一本通》<br />
揍是这样：</p>
<p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi mathvariant="normal">F</mi><mo>⁡</mo><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo>=</mo><mfrac><msqrt><mn>5</mn></msqrt><mn>5</mn></mfrac><mo>⋅</mo><mrow><mo fence="true">[</mo><msup><mrow><mo fence="true">(</mo><mn>1</mn><mo>+</mo><msqrt><mn>5</mn></msqrt><mo fence="true">)</mo></mrow><mi>n</mi></msup><mo>−</mo><msup><mrow><mo fence="true">(</mo><mn>1</mn><mo>−</mo><msqrt><mn>5</mn></msqrt><mo fence="true">)</mo></mrow><mi>n</mi></msup><mo fence="true">]</mo></mrow></mrow><annotation encoding="application/x-tex">\operatorname{F}(n)=\dfrac{\sqrt{5}}{5}\cdot\left[\left(1+\sqrt{5}\right)^n-\left(1-\sqrt{5}\right)^n\right]
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mop"><span class="mord mathrm">F</span></span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:2.27022em;vertical-align:-0.686em;"></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.5842200000000002em;"><span style="top:-2.314em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">5</span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.677em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord sqrt"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.90722em;"><span class="svg-align" style="top:-3em;"><span class="pstrut" style="height:3em;"></span><span class="mord" style="padding-left:0.833em;"><span class="mord">5</span></span></span><span style="top:-2.86722em;"><span class="pstrut" style="height:3em;"></span><span class="hide-tail" style="min-width:0.853em;height:1.08em;"><svg width='400em' height='1.08em' viewBox='0 0 400000 1080' preserveAspectRatio='xMinYMin slice'><path d='M95,702c-2.7,0,-7.17,-2.7,-13.5,-8c-5.8,-5.3,-9.5,
-10,-9.5,-14c0,-2,0.3,-3.3,1,-4c1.3,-2.7,23.83,-20.7,67.5,-54c44.2,-33.3,65.8,
-50.3,66.5,-51c1.3,-1.3,3,-2,5,-2c4.7,0,8.7,3.3,12,10s173,378,173,378c0.7,0,
35.3,-71,104,-213c68.7,-142,137.5,-285,206.5,-429c69,-144,104.5,-217.7,106.5,
-221c5.3,-9.3,12,-14,20,-14H400000v40H845.2724s-225.272,467,-225.272,467
s-235,486,-235,486c-2.7,4.7,-9,7,-19,7c-6,0,-10,-1,-12,-3s-194,-422,-194,-422
s-65,47,-65,47z M834 80H400000v40H845z'/></svg></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.13278em;"><span></span></span></span></span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.686em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">⋅</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1.854312em;vertical-align:-0.65002em;"></span><span class="minner"><span class="mopen delimcenter" style="top:0em;"><span class="delimsizing size2">[</span></span><span class="minner"><span class="minner"><span class="mopen delimcenter" style="top:0em;"><span class="delimsizing size2">(</span></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord sqrt"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.956095em;"><span class="svg-align" style="top:-3em;"><span class="pstrut" style="height:3em;"></span><span class="mord" style="padding-left:0.833em;"><span class="mord">5</span></span></span><span style="top:-2.916095em;"><span class="pstrut" style="height:3em;"></span><span class="hide-tail" style="min-width:0.853em;height:1.08em;"><svg width='400em' height='1.08em' viewBox='0 0 400000 1080' preserveAspectRatio='xMinYMin slice'><path d='M95,702c-2.7,0,-7.17,-2.7,-13.5,-8c-5.8,-5.3,-9.5,
-10,-9.5,-14c0,-2,0.3,-3.3,1,-4c1.3,-2.7,23.83,-20.7,67.5,-54c44.2,-33.3,65.8,
-50.3,66.5,-51c1.3,-1.3,3,-2,5,-2c4.7,0,8.7,3.3,12,10s173,378,173,378c0.7,0,
35.3,-71,104,-213c68.7,-142,137.5,-285,206.5,-429c69,-144,104.5,-217.7,106.5,
-221c5.3,-9.3,12,-14,20,-14H400000v40H845.2724s-225.272,467,-225.272,467
s-235,486,-235,486c-2.7,4.7,-9,7,-19,7c-6,0,-10,-1,-12,-3s-194,-422,-194,-422
s-65,47,-65,47z M834 80H400000v40H845z'/></svg></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.08390500000000001em;"><span></span></span></span></span></span><span class="mclose delimcenter" style="top:0em;"><span class="delimsizing size2">)</span></span></span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:1.204292em;"><span style="top:-3.6029em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">n</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="minner"><span class="minner"><span class="mopen delimcenter" style="top:0em;"><span class="delimsizing size2">(</span></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord sqrt"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.956095em;"><span class="svg-align" style="top:-3em;"><span class="pstrut" style="height:3em;"></span><span class="mord" style="padding-left:0.833em;"><span class="mord">5</span></span></span><span style="top:-2.916095em;"><span class="pstrut" style="height:3em;"></span><span class="hide-tail" style="min-width:0.853em;height:1.08em;"><svg width='400em' height='1.08em' viewBox='0 0 400000 1080' preserveAspectRatio='xMinYMin slice'><path d='M95,702c-2.7,0,-7.17,-2.7,-13.5,-8c-5.8,-5.3,-9.5,
-10,-9.5,-14c0,-2,0.3,-3.3,1,-4c1.3,-2.7,23.83,-20.7,67.5,-54c44.2,-33.3,65.8,
-50.3,66.5,-51c1.3,-1.3,3,-2,5,-2c4.7,0,8.7,3.3,12,10s173,378,173,378c0.7,0,
35.3,-71,104,-213c68.7,-142,137.5,-285,206.5,-429c69,-144,104.5,-217.7,106.5,
-221c5.3,-9.3,12,-14,20,-14H400000v40H845.2724s-225.272,467,-225.272,467
s-235,486,-235,486c-2.7,4.7,-9,7,-19,7c-6,0,-10,-1,-12,-3s-194,-422,-194,-422
s-65,47,-65,47z M834 80H400000v40H845z'/></svg></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.08390500000000001em;"><span></span></span></span></span></span><span class="mclose delimcenter" style="top:0em;"><span class="delimsizing size2">)</span></span></span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:1.204292em;"><span style="top:-3.6029em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">n</span></span></span></span></span></span></span></span><span class="mclose delimcenter" style="top:0em;"><span class="delimsizing size2">]</span></span></span></span></span></span></span></p>
<p>代码揍这么简单：</p>
<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>要是再加个快速幂就更棒了（够快了，懒得写）</p>

      
    </div>

    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
    <link itemprop="mainEntityOfPage" href="https://schtonn.github.io/posts/2020/dinic/">
<script>
    (function(){
        if(''){
            if (prompt('Password?') !== ''){
                alert('GOAWAY!');
                history.back();
            }
        }
    })();
</script>

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Alex">
      <meta itemprop="description" content="The blog of a middle school OIer">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Alex's Blog">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          
            <a href="/posts/2020/dinic/" class="post-title-link" itemprop="url">网络最大流-Dinic</a>
        </h1>

        <div class="post-meta">
          
          
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">Posted on</span>

              <time title="Created: 2020-Mar-02 11:31:22" itemprop="dateCreated datePublished" datetime="2020-03-02T11:31:22+08:00">2020-Mar-02</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                <span class="post-meta-item-text">Edited on</span>
                <time title="Modified: 2020-Mar-03 20:41:19" itemprop="dateModified" datetime="2020-03-03T20:41:19+08:00">2020-Mar-03</time>
              </span>

          
        </div>
      </header>

    
    <div class="post-body" itemprop="articleBody">

      
          <h3 id="前置知识"><a class="markdownIt-Anchor" href="#前置知识"></a> 前置知识</h3>
<p>存图方式（<a href="http://baidu.physton.com/?q=%E9%82%BB%E6%8E%A5%E8%A1%A8" target="_blank" rel="noopener" title="简单">邻接表</a>，<a href="http://baidu.physton.com/?q=%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5" 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>
<h3 id="引入"><a class="markdownIt-Anchor" href="#引入"></a> 引入</h3>
<p>我们举个例子吧：<br />
有一个毒瘤水管工，他会造水管，有一天他造了一个水管网络，就像一个图。其中有一个点只有出边，就是起点，还有一个点只有入边，是终点。<br />
点之间有一些管子，这些管子都有单位时间内的容量，现在毒瘤水管工想知道，他的管子在<strong>单位时间内</strong>在起点终点之间最多能流多少水。</p>
          <!--noindex-->
            <div class="post-button">
              <a class="btn" href="/posts/2020/dinic/#more" rel="contents">
                Read more &raquo;
              </a>
            </div>
          <!--/noindex-->
        
      
    </div>

    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
    <link itemprop="mainEntityOfPage" href="https://schtonn.github.io/posts/2020/min-span-tree/">
<script>
    (function(){
        if(''){
            if (prompt('Password?') !== ''){
                alert('GOAWAY!');
                history.back();
            }
        }
    })();
</script>

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Alex">
      <meta itemprop="description" content="The blog of a middle school OIer">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Alex's Blog">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          
            <a href="/posts/2020/min-span-tree/" class="post-title-link" itemprop="url">最小生成树</a>
        </h1>

        <div class="post-meta">
          
          
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">Posted on</span>

              <time title="Created: 2020-Mar-01 22:45:44" itemprop="dateCreated datePublished" datetime="2020-03-01T22:45:44+08:00">2020-Mar-01</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                <span class="post-meta-item-text">Edited on</span>
                <time title="Modified: 2020-Mar-05 21:16:57" itemprop="dateModified" datetime="2020-03-05T21:16:57+08:00">2020-Mar-05</time>
              </span>

          
        </div>
      </header>

    
    <div class="post-body" itemprop="articleBody">

      
          <h3 id="前置知识"><a class="markdownIt-Anchor" href="#前置知识"></a> 前置知识</h3>
<p>存图方式（<a href="http://baidu.physton.com/?q=%E9%82%BB%E6%8E%A5%E8%A1%A8" target="_blank" rel="noopener" title="简单">邻接表</a>，<a href="http://baidu.physton.com/?q=%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5" target="_blank" rel="noopener" title="都太简单了，没有一个打得过的">邻接矩阵</a>），<a href="https://schtonn.github.io/2020/03/01/union-find">并查集</a>。<br />
不会的快进入链接学习吧！</p>
<h3 id="引入"><a class="markdownIt-Anchor" href="#引入"></a> 引入</h3>
<p>生成树，就是从一个图中选中<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">n-1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span>条边，使得这些边构成一棵树，并包含图中的所有节点。<br />
最小生成树，就是找到一种生成树，使得这个生成树的边权和最小。</p>
          <!--noindex-->
            <div class="post-button">
              <a class="btn" href="/posts/2020/min-span-tree/#more" rel="contents">
                Read more &raquo;
              </a>
            </div>
          <!--/noindex-->
        
      
    </div>

    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
    <link itemprop="mainEntityOfPage" href="https://schtonn.github.io/posts/2020/union-find/">
<script>
    (function(){
        if(''){
            if (prompt('Password?') !== ''){
                alert('GOAWAY!');
                history.back();
            }
        }
    })();
</script>

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Alex">
      <meta itemprop="description" content="The blog of a middle school OIer">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Alex's Blog">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          
            <a href="/posts/2020/union-find/" class="post-title-link" itemprop="url">并查集</a>
        </h1>

        <div class="post-meta">
          
          
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">Posted on</span>

              <time title="Created: 2020-Mar-01 22:44:33" itemprop="dateCreated datePublished" datetime="2020-03-01T22:44:33+08:00">2020-Mar-01</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                <span class="post-meta-item-text">Edited on</span>
                <time title="Modified: 2020-Mar-03 20:39:35" itemprop="dateModified" datetime="2020-03-03T20:39:35+08:00">2020-Mar-03</time>
              </span>

          
        </div>
      </header>

    
    <div class="post-body" itemprop="articleBody">

      
          <h3 id="前置知识"><a class="markdownIt-Anchor" href="#前置知识"></a> 前置知识</h3>
<p>哈哈，简单到爆，没有。</p>
<h3 id="引入"><a class="markdownIt-Anchor" href="#引入"></a> 引入</h3>
<p>并查集是一种快到爆炸的集合算法，可以进行两项基本操作：合并两个集合（并）、查询两个参数是否在一个集合内（查）。这也是它名字的由来。</p>
          <!--noindex-->
            <div class="post-button">
              <a class="btn" href="/posts/2020/union-find/#more" rel="contents">
                Read more &raquo;
              </a>
            </div>
          <!--/noindex-->
        
      
    </div>

    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
    <link itemprop="mainEntityOfPage" href="https://schtonn.github.io/posts/2020/tree-link/">
<script>
    (function(){
        if(''){
            if (prompt('Password?') !== ''){
                alert('GOAWAY!');
                history.back();
            }
        }
    })();
</script>

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Alex">
      <meta itemprop="description" content="The blog of a middle school OIer">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Alex's Blog">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          
            <a href="/posts/2020/tree-link/" class="post-title-link" itemprop="url">树链剖分</a>
        </h1>

        <div class="post-meta">
          
          
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">Posted on</span>

              <time title="Created: 2020-Mar-01 22:41:02" itemprop="dateCreated datePublished" datetime="2020-03-01T22:41:02+08:00">2020-Mar-01</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                <span class="post-meta-item-text">Edited on</span>
                <time title="Modified: 2020-Mar-03 20:39:51" itemprop="dateModified" datetime="2020-03-03T20:39:51+08:00">2020-Mar-03</time>
              </span>

          
        </div>
      </header>

    
    <div class="post-body" itemprop="articleBody">

      
          <h3 id="前置知识"><a class="markdownIt-Anchor" href="#前置知识"></a> 前置知识</h3>
<p>必备：存图方式（<a href="http://baidu.physton.com/?q=%E9%82%BB%E6%8E%A5%E8%A1%A8" target="_blank" rel="noopener" title="简单">邻接表</a>，<a href="http://baidu.physton.com/?q=%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5" target="_blank" rel="noopener" title="都太简单了，没有一个打得过的">邻接矩阵</a>），<a href="http://baidu.physton.com/?q=dfs%E5%BA%8F" target="_blank" rel="noopener">dfs序</a>。<br />
维护：<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>。<br />
不会的快进入链接学习吧！</p>
<h3 id="引入"><a class="markdownIt-Anchor" href="#引入"></a> 引入</h3>
<p>树链剖分，简单来说就是把树分割成链，然后维护每一条链。一般的维护算法有线段树，树状数组和BST。复杂度为<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>l</mi><mi>o</mi><mi>g</mi><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(log n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mord mathdefault">o</span><span class="mord mathdefault" style="margin-right:0.03588em;">g</span><span class="mord mathdefault">n</span><span class="mclose">)</span></span></span></span>。</p>
          <!--noindex-->
            <div class="post-button">
              <a class="btn" href="/posts/2020/tree-link/#more" rel="contents">
                Read more &raquo;
              </a>
            </div>
          <!--/noindex-->
        
      
    </div>

    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
    <link itemprop="mainEntityOfPage" href="https://schtonn.github.io/posts/2020/test/">
<script>
    (function(){
        if(''){
            if (prompt('Password?') !== ''){
                alert('GOAWAY!');
                history.back();
            }
        }
    })();
</script>

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Alex">
      <meta itemprop="description" content="The blog of a middle school OIer">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Alex's Blog">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          
            <a href="/posts/2020/test/" class="post-title-link" itemprop="url">test</a>
        </h1>

        <div class="post-meta">
          
          
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">Posted on</span>

              <time title="Created: 2020-Mar-01 11:06:43" itemprop="dateCreated datePublished" datetime="2020-03-01T11:06:43+08:00">2020-Mar-01</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                <span class="post-meta-item-text">Edited on</span>
                <time title="Modified: 2020-Mar-05 21:01:44" itemprop="dateModified" datetime="2020-03-05T21:01:44+08:00">2020-Mar-05</time>
              </span>

          
        </div>
      </header>

    
    <div class="post-body" itemprop="articleBody">

      
          <p><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mtext mathvariant="monospace">Is</mtext><mtext> </mtext><mtext mathvariant="monospace">KaTeX</mtext><mtext> </mtext><mtext mathvariant="monospace">working?-IT</mtext><mtext> </mtext><mtext mathvariant="monospace">WORKED!NICE!</mtext></mrow><annotation encoding="application/x-tex">\texttt{Is KaTeX working?-IT WORKED!NICE!}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.22222em;"></span><span class="mord text"><span class="mord texttt">Is KaTeX working?-IT WORKED!NICE!</span></span></span></span></span></p>
<p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><msup><mi>a</mi><mi>b</mi></msup></mrow><annotation encoding="application/x-tex">a^b
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8991079999999999em;vertical-align:0em;"></span><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8991079999999999em;"><span style="top:-3.113em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">b</span></span></span></span></span></span></span></span></span></span></span></span></p>
<p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo fence="true">(</mo><mfrac><mi>a</mi><mi>b</mi></mfrac><mo fence="true">)</mo></mrow><annotation encoding="application/x-tex">\left(\dfrac{a}{b}\right)
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.8359999999999999em;vertical-align:-0.686em;"></span><span class="minner"><span class="mopen delimcenter" style="top:0em;"><span class="delimsizing size2">(</span></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.10756em;"><span style="top:-2.314em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord mathdefault">b</span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.677em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord mathdefault">a</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.686em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span><span class="mclose delimcenter" style="top:0em;"><span class="delimsizing size2">)</span></span></span></span></span></span></span></p>

      
    </div>

    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  </div>

  
          </div>
          

<script>
  window.addEventListener('tabs:register', () => {
    let activeClass = CONFIG.comments.activeClass;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          Table of Contents
        </li>
        <li class="sidebar-nav-overview">
          Overview
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">Alex</p>
  <div class="site-description" itemprop="description">The blog of a middle school OIer</div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">10</span>
          <span class="site-state-item-name">posts</span>
        </a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">4</span>
        <span class="site-state-item-name">tags</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
        <a href="https://github.com/schtonn" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;schtonn" rel="noopener" target="_blank"><i class="fa fa-fw fa-github"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="skype:alex?call|chat" title="Skype → skype:alex?call|chat" rel="noopener" target="_blank"><i class="fa fa-fw fa-skype"></i>Skype</a>
      </span>
  </div>


  <div class="links-of-blogroll motion-element">
    <div class="links-of-blogroll-title">
      <i class="fa fa-fw fa-link"></i>
      Links
    </div>
    <ul class="links-of-blogroll-list">
        <li class="links-of-blogroll-item">
          <a href="https://yonghong.github.io/" title="https:&#x2F;&#x2F;yonghong.github.io" rel="noopener" target="_blank">Yonghong</a>
        </li>
        <li class="links-of-blogroll-item">
          <a href="https://source.unsplash.com/random/1600x900" title="https:&#x2F;&#x2F;source.unsplash.com&#x2F;random&#x2F;1600x900" rel="noopener" target="_blank">Background</a>
        </li>
    </ul>
  </div>

      </div>
      <div id="treefrog" style="text-align: center;margin-top: 18px;">
        <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>
      </div>
    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

<div class="copyright">
  
  &copy; 
  <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Alex Xiang</span>
</div>

        
      </div>
    </footer>
  </div>

  
  <script src="/lib/anime.min.js"></script>
  <script src="//cdn.jsdelivr.net/npm/lozad@1/dist/lozad.min.js"></script>
  <script src="/lib/velocity/velocity.min.js"></script>
  <script src="/lib/velocity/velocity.ui.min.js"></script>

<script src="/js/utils.js"></script>

<script src="/js/motion.js"></script>


<script src="/js/schemes/muse.js"></script>


<script src="/js/next-boot.js"></script>


  <script>
    (function(){
      var bp = document.createElement('script');
      var curProtocol = window.location.protocol.split(':')[0];
      bp.src = (curProtocol === 'https') ? 'https://zz.bdstatic.com/linksubmit/push.js' : 'http://push.zhanzhang.baidu.com/push.js';
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(bp, s);
    })();
  </script>


<link rel="stylesheet" href="//cdn.jsdelivr.net/npm/katex@0/dist/katex.min.css">


<script>
NexT.utils.loadComments(document.querySelector('#valine-comments'), () => {
  NexT.utils.getScript('//unpkg.com/valine/dist/Valine.min.js', () => {
    var GUEST = ['nick', 'mail', 'link'];
    var guest = 'nick,mail,link';
    guest = guest.split(',').filter(item => {
      return GUEST.includes(item);
    });
    new Valine({
      el         : '#valine-comments',
      verify     : true,
      notify     : true,
      appId      : 'BmologYYnRqCv0SLHDeDdA17-gzGzoHsz',
      appKey     : 'w9mVebFMdCmY6Nh9vfcBGaGt',
      placeholder: "Write your comment...",
      avatar     : 'mm',
      meta       : guest,
      pageSize   : '10' || 10,
      visitor    : false,
      lang       : 'en' || 'zh-cn',
      path       : location.pathname,
      recordIP   : false,
      serverURLs : ''
    });
  }, window.Valine);
});
</script>

</body>
</html>