1<!DOCTYPE html> 2<html> 3<head> 4 <meta charset="utf-8"/> 5<meta http-equiv="X-UA-Compatible" content="IE=edge"/> 6<meta name="viewport" content="width=device-width, initial-scale=1.0,user-scalable=no"/> 7 8 9<title>ë¼ì´ë¸ë¬ë¦¬</title> 10<meta name="title" content="ë¼ì´ë¸ë¬ë¦¬" /> 11<meta name="author" content="[email protected]"/> 12<meta name="description" content=""/> 13 14<meta property="fb:app_id" content="956026527861303"/> 15 16<meta property="og:site_name" content="Wookje blog"/> 17<meta property="og:type" content="article"/> 18<meta property="og:title" content="ë¼ì´ë¸ë¬ë¦¬"/> 19<meta property="og:description" content=""/> 20<meta property="og:url" content="http://wookje.dance/library/"/> 21<meta property="og:image" content="http://wookje.dance/assets/images/default_blog_cover.jpg"/> 22<meta name="twitter:card" content="summary_large_image"/> 23<meta name="twitter:title" content="ë¼ì´ë¸ë¬ë¦¬"/> 24<meta name="twitter:description" content=""/> 25<meta name="twitter:label1" content="Written by"/> 26<meta name="twitter:data1" content="[email protected]"/> 27<meta name="twitter:image:src" content="http://wookje.dance/assets/images/default_blog_cover.jpg"/> 28 29 30 31<link href="http://wookje.dance/rss/" rel="alternate" type="application/rss+xml" title="RSS"/> 32<link href="/assets/favicon.ico" rel="shortcut icon" type="image/vnd.microsoft.icon"/> 33<link href="/assets/apple-touch-icon.png" rel="apple-touch-icon" type="image/png"/> 34<link href="/assets/apple-touch-icon.png" rel="apple-touch-icon-precomposed" type="image/png"/> 35<link href="/assets/lib/normalize.css" rel="stylesheet" type="text/css"/> 36<link href="/assets/css/monokai.css" rel="stylesheet" type="text/css"/> 37<link href="/assets/lib/magnific-popup.min.css" rel="stylesheet" type="text/css"/> 38<link href="/assets/fonts/Kakao.css" rel="stylesheet" type="text/css"/> 39<link href="/assets/css/screen.css" rel="stylesheet" type="text/css"/> 40 41 <!-- Begin Jekyll SEO tag v2.8.0 --> 42<title>ë¼ì´ë¸ë¬ë¦¬ | Wookje blog</title> 43<meta name="generator" content="Jekyll v3.10.0" /> 44<meta property="og:title" content="ë¼ì´ë¸ë¬ë¦¬" /> 45<meta name="author" content="[email protected]" /> 46<meta property="og:locale" content="en_US" /> 47<meta name="description" content="ìê³ ë¦¬ì¦ ë¸ë¡ê·¸ìë ê²" /> 48<meta property="og:description" content="ìê³ ë¦¬ì¦ ë¸ë¡ê·¸ìë ê²" /> 49<link rel="canonical" href="http://wookje.dance/library/" /> 50<meta property="og:url" content="http://wookje.dance/library/" /> 51<meta property="og:site_name" content="Wookje blog" /> 52<meta property="og:type" content="website" /> 53<meta name="twitter:card" content="summary" /> 54<meta property="twitter:title" content="ë¼ì´ë¸ë¬ë¦¬" /> 55<meta property="fb:app_id" content="956026527861303" />
56<script type="application/ld+json"> 57{"@context":"https://schema.org","@type":"WebPage","author":{"@type":"Person","name":"[email protected]"},"description":"ìê³ ë¦¬ì¦ ë¸ë¡ê·¸ìë ê²","headline":"ë¼ì´ë¸ë¬ë¦¬","url":"http://wookje.dance/library/"}</script>
57 58<!-- End Jekyll SEO tag --> 59 60</head> 61<body class="page-template"> 62 63<div id="header"> 64 <button id="menu-toggle" type="button"> 65 <span class="sr-only">Toggle Navigation Menu</span> 66 </button> 67 <button id="search-toggle" type="button"> 68 <span class="sr-only">Toggle Search Form</span> 69 </button> 70 <a id="logo" href="/"> 71 <span class="sr-only">WookjeBlog</span> 72 </a> 73 <div id="search"> 74 <input id="search-input" type="search" placeholder="Search..." value="" /> 75 </div> 76 <ul class="search__results" id="results-container"></ul> 77 78 <ul id="menu" class="nav"> 79 <li class=" active "><a href="/">ë¸ë¡ê·¸</a></li> 80 <li class=""><a href="/whoami/">ìê°</a></li> 81 <li class=""><a href="/tags/">íê·¸</a></li> 82 <li class=""><a href="/2017/11/17/ê³¼ì¸/">ìì /ê°ì</a></li> 83 <li class=" active "><a href="/library/">ë¼ì´ë¸ë¬ë¦¬</a></li> 84 </ul> 85</div> 86
87<script src="https://unpkg.com/[email protected]/dest/simple-jekyll-search.min.js"></script>
vendor: 1 bytes, line 87
87
88<script type="text/javascript"> 89 SimpleJekyllSearch({ 90 searchInput: document.getElementById('search-input'), 91 resultsContainer: document.getElementById('results-container'), 92 json: '/search.json', 93 searchResultTemplate: '<li><a href="{url}" title="{desc}">{title}</a></li>', 94 noResultsText: '<li>No results found</li>', 95 limit: 15, 96 fuzzy: false, 97 exclude: ['Welcome'] 98 }) 99</script>
99<!-- #header --> 100 101<div id="wrapper"> 102 <div id="cover" class="container-fluid" 103 > 104 <div> 105 <h1>ë¼ì´ë¸ë¬ë¦¬</h1> 106 <p></p> 107 </div> 108</div> 109 110<div id="content" class="container"> 111 <div id="post-content" class="post page" role="main"> 112 <p>(ì ë°ì´í¸ ì¤)</p> 113 114<p>ìê³ ë¦¬ì¦/ìë£êµ¬ì¡° ë³µë¶ì© ë¼ì´ë¸ë¬ë¦¬</p> 115 116<p>ì½ëì ì¤ë¥ê° ìì ê°ë¥ì± ì주 ëìµëë¤</p> 117 118<p>ìì ë° ì¶ê° ì ì, ì¤ë¥ ì ë³´ íìí©ëë¤</p> 119 120<p>[email protected] ëë ê°ì¸ì ì¼ë¡ ì°ë½ 주ì¸ì</p> 121 122<h2 id="include-ì¸í´ë£¨ë">include ì¸í´ë£¨ë</h2> 123 124<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="c1">// http://wookje.dance/library/</span> 125<span class="cp">#include</span><span class="cpf"><cstdio></span><span class="cp"> 126#include</span><span class="cpf"><iostream></span><span class="cp"> 127#include</span><span class="cpf"><algorithm></span><span class="cp"> 128#include</span><span class="cpf"><vector></span><span class="cp"> 129#include</span><span class="cpf"><queue></span><span class="cp"> 130#include</span><span class="cpf"><deque></span><span class="cp"> 131#include</span><span class="cpf"><stack></span><span class="cp"> 132#include</span><span class="cpf"><string></span><span class="cp"> 133#include</span><span class="cpf"><list></span><span class="cp"> 134#include</span><span class="cpf"><map></span><span class="cp"> 135#include</span><span class="cpf"><set></span><span class="cp"> 136#include</span><span class="cpf"><unordered_map></span><span class="cp"> 137#include</span><span class="cpf"><unordered_set></span><span class="cp"> 138#include</span><span class="cpf"><bitset></span><span class="cp"> 139#include</span><span class="cpf"><tuple></span><span class="cp"> 140#include</span><span class="cpf"><functional></span><span class="cp"> 141#include</span><span class="cpf"><utility></span><span class="cp"> 142#include</span><span class="cpf"><cmath></span><span class="cp"> 143#include</span><span class="cpf"><cstdlib></span><span class="cp"> 144#include</span><span class="cpf"><cstring></span><span class="cp"> 145#include</span><span class="cpf"><complex></span><span class="cp"> 146#include</span><span class="cpf"><cassert></span><span class="cp"> 147#define y1 fuckfuckfuck 148#define fst first 149#define snd second 150#define pb push_back 151#define sz(v) ((int)(v).size()) 152#define all(v)) (v).begin(), (v).end() 153#define PQ priority_queue 154</span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> 155<span class="k">using</span> <span class="n">ll</span> <span class="o">=</span> <span class="kt">long</span> <span class="kt">long</span><span class="p">;</span> 156<span class="k">using</span> <span class="n">ull</span> <span class="o">=</span> <span class="kt">unsigned</span> <span class="kt">long</span> <span class="kt">long</span><span class="p">;</span> 157<span class="k">using</span> <span class="n">dbl</span> <span class="o">=</span> <span class="kt">double</span><span class="p">;</span> 158<span class="k">using</span> <span class="n">ldb</span> <span class="o">=</span> <span class="kt">long</span> <span class="kt">double</span><span class="p">;</span> 159<span class="k">using</span> <span class="n">pii</span> <span class="o">=</span> <span class="n">pair</span><span class="o"><</span><span class="kt">int</span><span class="p">,</span><span class="kt">int</span><span class="o">></span><span class="p">;</span> 160<span class="k">using</span> <span class="n">pll</span> <span class="o">=</span> <span class="n">pair</span><span class="o"><</span><span class="n">ll</span><span class="p">,</span><span class="n">ll</span><span class="o">></span><span class="p">;</span> 161<span class="k">using</span> <span class="n">vi</span> <span class="o">=</span> <span class="n">vector</span><span class="o"><</span><span class="kt">int</span><span class="o">></span><span class="p">;</span> 162<span class="n">ll</span> <span class="nf">gcd</span><span class="p">(</span><span class="n">ll</span> <span class="n">a</span><span class="p">,</span> <span class="n">ll</span> <span class="n">b</span><span class="p">){</span><span class="k">return</span> <span class="n">b</span><span class="o">?</span><span class="n">gcd</span><span class="p">(</span><span class="n">b</span><span class="p">,</span><span class="n">a</span><span class="o">%</span><span class="n">b</span><span class="p">)</span><span class="o">:</span><span class="n">a</span><span class="p">;}</span> 163<span class="n">ll</span> <span class="n">lcm</span><span class="p">(</span><span class="n">ll</span> <span class="n">a</span><span class="p">,</span> <span class="n">ll</span> <span class="n">b</span><span class="p">)</span> <span class="p">{</span><span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">a</span><span class="o">||!</span><span class="n">b</span><span class="p">)</span><span class="k">return</span> <span class="mi">0</span><span class="p">;</span><span class="k">return</span> <span class="n">a</span><span class="o">*</span><span class="p">(</span><span class="n">b</span><span class="o">/</span><span class="n">gcd</span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="n">b</span><span class="p">));}</span> 164<span class="n">pll</span> <span class="n">ext_gcd</span><span class="p">(</span><span class="n">ll</span> <span class="n">a</span><span class="p">,</span> <span class="n">ll</span> <span class="n">b</span><span class="p">){</span> 165 <span class="k">if</span> <span class="p">(</span><span class="n">b</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="k">return</span> <span class="p">{</span> <span class="mi">1</span><span class="p">,</span><span class="mi">0</span> <span class="p">};</span> 166 <span class="k">auto</span> <span class="n">t</span> <span class="o">=</span> <span class="n">ext_gcd</span><span class="p">(</span><span class="n">b</span><span class="p">,</span> <span class="n">a</span><span class="o">%</span><span class="n">b</span><span class="p">);</span> 167 <span class="k">return</span> <span class="p">{</span> <span class="n">t</span><span class="p">.</span><span class="n">second</span><span class="p">,</span><span class="n">t</span><span class="p">.</span><span class="n">first</span><span class="o">-</span><span class="p">(</span><span class="n">a</span><span class="o">/</span><span class="n">b</span><span class="p">)</span><span class="o">*</span><span class="n">t</span><span class="p">.</span><span class="n">second</span> <span class="p">};</span> 168<span class="p">}</span> 169<span class="k">const</span> <span class="kt">int</span> <span class="n">dx</span><span class="p">[]</span><span class="o">=</span><span class="p">{</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="o">-</span><span class="mi">1</span><span class="p">},</span><span class="n">dy</span><span class="p">[]</span><span class="o">=</span><span class="p">{</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">};</span> 170<span class="k">struct</span> <span class="nc">point</span> <span class="p">{</span> 171 <span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">;</span> 172 <span class="kt">bool</span> <span class="k">operator</span> <span class="o"><</span><span class="p">(</span><span class="n">point</span> <span class="n">a</span><span class="p">)</span><span class="k">const</span> <span class="p">{</span>
173 <span class="k">return</span> <span class="n">x</span> <span class="o">==</span> <span class="n">a</span><span class="p">.</span><span class="n">x</span> <span class="o">?</span> <span class="n">y</span> <span class="o"><</span> <span class="n">a</span><span class="p">.</span><span class="n">y</span> <span class="o">:</span> <span class="n">x</span> <span class="o"><</span> <span class="n">a</span><span class="p">.</span><span class="n">x</span><span class="p">;</span> 174 <span class="p">}</span> 175<span class="p">};</span> 176 177<span class="k">const</span> <span class="kt">int</span> <span class="n">powmod</span> <span class="o">=</span> <span class="mf">1e9</span><span class="o">+</span><span class="mi">7</span><span class="p">;</span> 178<span class="n">ll</span> <span class="n">fast_pow</span><span class="p">(</span><span class="n">ll</span> <span class="n">base</span><span class="p">,</span> <span class="n">ll</span> <span class="n">exp</span><span class="p">)</span> <span class="p">{</span> 179 <span class="k">if</span> <span class="p">(</span><span class="n">base</span> <span class="o">==</span> <span class="mi">1</span><span class="p">)</span> <span class="k">return</span> <span class="mi">1</span><span class="p">;</span> 180 <span class="n">ll</span> <span class="n">ans</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> 181 <span class="k">while</span> <span class="p">(</span><span class="n">exp</span><span class="p">)</span> <span class="p">{</span> 182 <span class="k">if</span> <span class="p">(</span><span class="n">exp</span> <span class="o">&</span> <span class="mi">1</span><span class="p">)</span> <span class="p">{</span> 183 <span class="n">ans</span> <span class="o">=</span> <span class="p">(</span><span class="n">ans</span> <span class="o">*</span> <span class="n">base</span><span class="p">)</span><span class="o">%</span><span class="n">powmod</span><span class="p">;</span> 184 <span class="p">}</span> 185 <span class="n">base</span> <span class="o">=</span> <span class="p">(</span><span class="n">base</span><span class="o">*</span><span class="n">base</span><span class="p">)</span><span class="o">%</span><span class="n">powmod</span><span class="p">;</span> 186 <span class="n">exp</span> <span class="o">>>=</span> <span class="mi">1</span><span class="p">;</span> 187 <span class="p">}</span> 188 <span class="k">return</span> <span class="n">ans</span><span class="p">;</span> 189<span class="p">}</span> 190 191 192<span class="kt">int</span> <span class="n">main</span><span class="p">()</span> <span class="p">{</span> 193 <span class="c1">//cin.tie(0);
193 ios_base::sync_with_stdio(0);</span> 194 195 196 197 <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> 198<span class="p">}</span> 199 200</code></pre></div></div> 201 202<h2 id="tree-í¸ë¦¬">Tree í¸ë¦¬</h2> 203 204<h3 id="fenwick-tree-íì -í¸ë¦¬">Fenwick Tree íì í¸ë¦¬</h3> 205 206<p>point update, range query</p> 207 208<p><code class="language-plaintext highlighter-rouge">qry(h): 1~hê¹ì§ì í©</code><br /> 209<code class="language-plaintext highlighter-rouge">upd(h, v): hì vë§í¼ ëí¨</code></p> 210 211<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> 212<span class="k">const</span> <span class="kt">int</span> <span class="n">MAXN</span> <span class="o">=</span> <span class="mf">1e6</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> 213 214<span class="kt">int</span> <span class="n">n</span><span class="p">;</span> 215<span class="n">ll</span> <span class="n">tree</span><span class="p">[</span><span class="n">MAXN</span><span class="p">];</span> 216 217<span class="kr">inline</span> <span class="kt">void</span> <span class="nf">upd</span><span class="p">(</span><span class="kt">int</span> <span class="n">h</span><span class="p">,</span> <span class="n">ll</span> <span class="n">v</span><span class="p">)</span> <span class="p">{</span> 218 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">h</span><span class="p">;</span> <span class="n">i</span> <span class="o"><=</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span> <span class="o">+=</span> <span class="n">i</span><span class="o">&-</span><span class="n">i</span><span class="p">)</span> <span class="n">tree</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+=</span> <span class="n">v</span><span class="p">;</span> 219<span class="p">}</span> 220 221<span class="n">ll</span> <span class="n">qry</span><span class="p">(</span><span class="kt">int</span> <span class="n">h</span><span class="p">)</span> <span class="p">{</span> 222 <span class="n">ll</span> <span class="n">ret</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> 223 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">h</span><span class="p">;</span> <span class="n">i</span><span class="p">;</span> <span class="n">i</span> <span class="o">-=</span> <span class="n">i</span><span class="o">&-</span><span class="n">i</span><span class="p">)</span> <span class="n">ret</span> <span class="o">+=</span> <span class="n">tree</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> 224 <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> 225<span class="p">}</span> 226</code></pre></div></div> 227 228<p>range update, point query</p> 229 230<p><code class="language-plaintext highlighter-rouge">qry(h): hì ëì í©</code><br /> 231<code class="language-plaintext highlighter-rouge">upd(s, e, x): [s, e]ì xë§í¼ ëí¨</code></p> 232 233<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> 234<span class="k">const</span> <span class="kt">int</span> <span class="n">MAXN</span> <span class="o">=</span> <span class="mf">1e6</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> 235 236<span class="kt">int</span> <span class="n">n</span><span class="p">;</span> 237<span class="n">ll</span> <span class="n">tree</span><span class="p">[</span><span class="n">MAXN</span><span class="p">];</span> 238 239<span class="kr">inline</span> <span class="kt">void</span> <span class="nf">upd</span><span class="p">(</span><span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="kt">int</span> <span class="n">e</span><span class="p">,</span> <span class="n">ll</span> <span class="n">x</span><span class="p">)</span> <span class="p">{</span> 240 <span class="k">if</span> <span class="p">(</span><span class="n">s</span> <span class="o"><=</span> <span class="n">e</span><span class="p">)</span> <span class="p">{</span>
241 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">s</span><span class="p">;</span> <span class="n">i</span> <span class="o"><=</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span> <span class="o">+=</span> <span class="n">i</span><span class="o">&-</span><span class="n">i</span><span class="p">)</span> <span class="n">tree</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+=</span> <span class="n">x</span><span class="p">;</span> 242 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">e</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o"><=</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span> <span class="o">+=</span> <span class="n">i</span><span class="o">&-</span><span class="n">i</span><span class="p">)</span> <span class="n">tree</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">-=</span> <span class="n">x</span><span class="p">;</span> 243 <span class="p">}</span> 244 <span class="k">else</span> <span class="p">{</span> 245 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o"><=</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span> <span class="o">+=</span> <span class="n">i</span><span class="o">&-</span><span class="n">i</span><span class="p">)</span> <span class="n">tree</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+=</span> <span class="n">x</span><span class="p">;</span> 246 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">s</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o"><=</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span> <span class="o">+=</span> <span class="n">i</span><span class="o">&-</span><span class="n">i</span><span class="p">)</span> <span class="n">tree</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">-=</span> <span class="n">x</span><span class="p">;</span> 247 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">e</span><span class="p">;</span> <span class="n">i</span> <span class="o"><=</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span> <span class="o">+=</span> <span class="n">i</span><span class="o">&-</span><span class="n">i</span><span class="p">)</span> <span class="n">tree</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+=</span> <span class="n">x</span><span class="p">;</span> 248 <span class="p">}</span> 249<span class="p">}</span> 250 251<span class="n">ll</span> <span class="n">qry</span><span class="p">(</span><span class="kt">int</span> <span class="n">h</span><span class="p">)</span> <span class="p">{</span> 252 <span class="n">ll</span> <span class="n">ret</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> 253 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">h</span><span class="p">;</span> <span class="n">i</span><span class="p">;</span> <span class="n">i</span> <span class="o">-=</span> <span class="n">i</span><span class="o">&-</span><span class="n">i</span><span class="p">)</span> <span class="n">ret</span> <span class="o">+=</span> <span class="n">bit</span><span class="p">[</span><span class="n">i</span><span class="p">];
253</span> 254 <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> 255<span class="p">}</span> 256</code></pre></div></div> 257 258<h3 id="non-recursive-segment-tree-ë¹ì¬ê·-ì¸ê·¸ë¨¼í¸-í¸ë¦¬">Non Recursive Segment Tree ë¹ì¬ê· ì¸ê·¸ë¨¼í¸ í¸ë¦¬</h3> 259 260<p>sum, point update, range query</p> 261 262<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> 263 264<span class="k">const</span> <span class="kt">int</span> <span class="n">MAXN</span> <span class="o">=</span> <span class="p">(</span><span class="mi">1</span> <span class="o"><<</span> <span class="mi">20</span><span class="p">);</span> 265<span class="n">ll</span> <span class="n">tree</span><span class="p">[</span><span class="n">MAXN</span><span class="o">*</span><span class="mi">2</span><span class="o">+</span><span class="mi">10</span><span class="p">];</span> 266 267<span class="kt">void</span> <span class="nf">update</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="n">ll</span> <span class="n">v</span><span class="p">)</span> <span class="p">{</span> 268 <span class="n">i</span> <span class="o">+=</span> <span class="n">MAXN</span><span class="p">;</span> 269 <span class="k">while</span> <span class="p">(</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span> 270 <span class="n">tree</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+=</span> <span class="n">v</span><span class="p">;</span> 271 <span class="n">i</span> <span class="o">/=</span> <span class="mi">2</span><span class="p">;</span> 272 <span class="p">}</span> 273<span class="p">}</span> 274 275<span class="n">ll</span> <span class="n">query</span><span class="p">(</span><span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="kt">int</span> <span class="n">e</span><span class="p">)</span> <span class="p">{</span> 276 <span class="n">ll</span> <span class="n">sum</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> 277 <span class="n">s</span> <span class="o">+=</span> <span class="n">MAXN</span><span class="p">;</span> <span class="n">e</span> <span class="o">+=</span> <span class="n">MAXN</span><span class="p">;</span> 278 <span class="k">while</span> <span class="p">(</span><span class="n">s</span> <span class="o"><=</span> <span class="n">e</span><span class="p">)</span> <span class="p">{</span> 279 <span class="k">if</span> <span class="p">(</span><span class="n">s</span> <span class="o">%</span> <span class="mi">2</span> <span class="o">==</span> <span class="mi">1</span><span class="p">)</span> <span class="n">sum</span> <span class="o">+=</span> <span class="n">tree</span><span class="p">[</span><span class="n">s</span><span class="p">];</span> 280 <span class="k">if</span> <span class="p">(</span><span class="n">e</span> <span class="o">%</span> <span class="mi">2</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="n">sum</span> <span class="o">+=</span> <span class="n">tree</span><span class="p">[</span><span class="n">e</span><span class="p">];</span> 281 <span class="n">s</span> <span class="o">=</span> <span class="p">(</span><span class="n">s</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span> 282 <span class="n">e</span> <span class="o">=</span> <span class="p">(</span><span class="n">e</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span> 283 <span class="p">}</span> 284 <span class="k">return</span> <span class="n">sum</span><span class="p">;</span> 285<span class="p">}</span> 286</code></pre></div></div> 287 288<p>min(max), point update, range query</p> 289 290<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">TODO</span> 291</code></pre></div></div> 292 293<h3 id="lazy-propagation-ë ì´ì§">Lazy Propagation ë ì´ì§</h3> 294 295<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">TODO</span> 296</code></pre></div></div> 297 298<h3 id="merge-sort-tree-머ì§-ìí¸-í¸ë¦¬">Merge Sort Tree ë¨¸ì§ ìí¸ í¸ë¦¬</h3> 299 300<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">TODO</span> 301</code></pre></div></div> 302 303<h3 id="pst-persistent-segment-tree-í¼ìì¤í°">PST Persistent Segment Tree í¼ìì¤í°</h3> 304 305<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="k">const</span> <span class="kt">int</span> <span class="n">MAXN</span> <span class="o">=</span> <span class="mi">1</span><span class="o"><<</span><span class="mi">17</span><span class="p">;</span> 306<span class="kt">int</span> <span class="n">root</span><span class="p">[</span><span class="n">MAXN</span><span class="p">];
306</span> 307<span class="k">struct</span> <span class="nc">PST</span> <span class="p">{</span> 308 <span class="kt">int</span> <span class="n">cnt</span> <span class="o">=</span> <span class="mi">1</span><span class="p">,</span> <span class="n">v</span><span class="p">[</span><span class="n">MAXN</span><span class="o">*</span><span class="mi">17</span><span class="p">],</span> <span class="n">l</span><span class="p">[</span><span class="n">MAXN</span><span class="o">*</span><span class="mi">17</span><span class="p">],</span> <span class="n">r</span><span class="p">[</span><span class="n">MAXN</span><span class="o">*</span><span class="mi">17</span><span class="p">];</span> 309 <span class="c1">// init(s,e) : ë¤ì í¸ë¦¬ë¤ì ë§ëë ë° ë² ì´ì¤ê° ë í¸ë¦¬ë¥¼ ë§ë ë¤. ì´ í¸ë¦¬ì 모ë ë ¸ëìë 0ì´ ë¤ì´ê° ìë¤. [s,e]ë ìì¼ë¡ì ì§ìë¤ì´ ë¤ì´ê° ë«í ë²ìì´ë¤.</span> 310 <span class="kt">int</span> <span class="n">init</span><span class="p">(</span><span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="kt">int</span> <span class="n">e</span><span class="p">)</span> <span class="p">{</span> 311 <span class="kt">int</span> <span class="n">idx</span> <span class="o">=</span> <span class="n">cnt</span><span class="o">++</span><span class="p">;</span> 312 <span class="k">if</span> <span class="p">(</span><span class="n">s</span> <span class="o"><</span> <span class="n">e</span><span class="p">)</span> <span class="p">{</span> 313 <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="p">(</span><span class="n">s</span><span class="o">+</span><span class="n">e</span><span class="p">)</span><span class="o">>></span><span class="mi">1</span><span class="p">;</span> 314 <span class="n">l</span><span class="p">[</span><span class="n">idx</span><span class="p">]</span> <span class="o">=</span> <span class="n">init</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="n">m</span><span class="p">);</span> 315 <span class="n">r</span><span class="p">[</span><span class="n">idx</span><span class="p">]</span> <span class="o">=</span> <span class="n">init</span><span class="p">(</span><span class="n">m</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">e</span><span class="p">);</span> 316 <span class="p">}</span> 317 <span class="k">return</span> <span class="n">idx</span><span class="p">;</span> 318 <span class="p">}</span> 319 <span class="c1">// update(root,s,e,pos,val) : rootê° ë£¨í¸ì¸ í¸ë¦¬ë¥¼ 기ë°ì¼ë¡ pos ìì¹ì valë§ì ì ë°ì´í¸(ë§ì )í í¸ë¦¬ë¥¼ ë§ë¤ì´, ê·¸ 루í¸ë¥¼ ë°íí´ ì¤ë¤.</span> 320 <span class="kt">int</span> <span class="n">update</span><span class="p">(</span><span class="kt">int</span> <span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="kt">int</span> <span class="n">e</span><span class="p">,</span> <span class="kt">int</span> <span class="n">pos</span><span class="p">,</span> <span class="kt">int</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span> 321 <span class="k">if</span> <span class="p">(</span><span class="n">pos</span> <span class="o"><</span> <span class="n">s</span> <span class="o">||</span> <span class="n">e</span> <span class="o"><</span> <span class="n">pos</span><span class="p">)</span> <span class="k">return</span> <span class="n">root</span><span class="p">;</span> 322 <span class="kt">int</span> <span class="n">idx</span> <span class="o">=</span> <span class="n">cnt</span><span class="o">++</span><span class="p">;</span> 323 <span class="k">if</span> <span class="p">(</span><span class="n">s</span> <span class="o">==</span> <span class="n">e</span><span class="p">)</span> <span class="p">{</span> 324 <span class="n">v</span><span class="p">[</span><span class="n">idx</span><span class="p">]</span> <span class="o">=</span> <span class="n">v</span><span class="p">[</span><span class="n">root</span><span class="p">]</span> <span class="o">+</span> <span class="n">val</span><span class="p">;</span>
325 <span class="p">}</span> 326 <span class="k">else</span> <span class="p">{</span> 327 <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="p">(</span><span class="n">s</span><span class="o">+</span><span class="n">e</span><span class="p">)</span><span class="o">>></span><span class="mi">1</span><span class="p">;</span> 328 <span class="n">l</span><span class="p">[</span><span class="n">idx</span><span class="p">]</span> <span class="o">=</span> <span class="n">update</span><span class="p">(</span><span class="n">l</span><span class="p">[</span><span class="n">root</span><span class="p">],</span> <span class="n">s</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">pos</span><span class="p">,</span> <span class="n">val</span><span class="p">);</span> 329 <span class="n">r</span><span class="p">[</span><span class="n">idx</span><span class="p">]</span> <span class="o">=</span> <span class="n">update</span><span class="p">(</span><span class="n">r</span><span class="p">[</span><span class="n">root</span><span class="p">],</span> <span class="n">m</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">e</span><span class="p">,</span> <span class="n">pos</span><span class="p">,</span> <span class="n">val</span><span class="p">);</span> 330 <span class="n">v</span><span class="p">[</span><span class="n">idx</span><span class="p">]</span> <span class="o">=</span> <span class="n">v</span><span class="p">[</span><span class="n">l</span><span class="p">[</span><span class="n">idx</span><span class="p">]]</span> <span class="o">+</span> <span class="n">v</span><span class="p">[</span><span class="n">r</span><span class="p">[</span><span class="n">idx</span><span class="p">]];</span> 331 <span class="p">}</span> <span class="k">return</span> <span class="n">idx</span><span class="p">;</span> 332 <span class="p">}</span> 333 <span class="c1">// query(idx,s,e,l,r) : idx를 루í¸ë¡ í í¸ë¦¬ìì [l,r] 구ê°ì ê°ì í©ì ë°íí´ ì¤ë¤.</span> 334 <span class="kt">int</span> <span class="n">query</span><span class="p">(</span><span class="kt">int</span> <span class="n">idx</span><span class="p">,</span> <span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="kt">int</span> <span class="n">e</span><span class="p">,</span> <span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="kt">int</span> <span class="n">y</span><span class="p">)</span> <span class="p">{</span> 335 <span class="k">if</span> <span class="p">(</span><span class="n">x</span> <span class="o"><=</span> <span class="n">s</span> <span class="o">&&</span> <span class="n">e</span> <span class="o"><=</span> <span class="n">y</span><span class="p">)</span> <span class="k">return</span> <span class="n">v</span><span class="p">[</span><span class="n">idx</span><span class="p">];</span> 336 <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="n">e</span> <span class="o"><</span> <span class="n">x</span> <span class="o">||</span> <span class="n">y</span> <span class="o"><</span> <span class="n">s</span><span class="p">)</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> 337 <span class="k">else</span> <span class="p">{</span> 338 <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="p">(</span><span class="n">s</span><span class="o">+</span><span class="n">e</span><span class="p">)</span><span class="o">>></span><span class="mi">1</span><span class="p">;</span> 339 <span class="k">return</span> <span class="n">query</span><span class="p">(</span><span class="n">l</span><span class="p">[</span><span class="n">idx</span><span class="p">],</span> <span class="n">s</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">)</span> <span class="o">+</span> <span class="n">query</span><span class="p">(</span><span class="n">r</span><span class="p">[</span><span class="n">idx</span><span class="p">],</span> <span class="n">m</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">e</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">);</span>
340 <span class="p">}</span> 341 <span class="p">}</span> 342<span class="p">}</span> <span class="n">pst</span><span class="p">;</span> 343</code></pre></div></div> 344 345<h3 id="li-chao-리차ì¤">Li Chao 리차ì¤</h3> 346 347<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">TODO</span> 348</code></pre></div></div> 349 350<h2 id="flow-íë¡ì°">Flow íë¡ì°</h2> 351 352<h3 id="dinic-ëë">Dinic ëë</h3> 353 354<p><code class="language-plaintext highlighter-rouge">O(V^2E)</code></p> 355 356<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include</span> <span class="cpf"><vector></span><span class="cp"> 357#include</span> <span class="cpf"><algorithm></span><span class="cp"> 358#include</span> <span class="cpf"><queue></span><span class="cp"> 359#include</span> <span class="cpf"><cstring></span><span class="cp"> 360</span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> 361<span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> 362<span class="k">const</span> <span class="kt">int</span> <span class="n">MAXN</span> <span class="o">=</span> <span class="mi">3333</span><span class="p">;</span> <span class="c1">// !!! enough MAXN required: src=MAXN-4, snk=MAXN-3 !!!</span> 363<span class="k">struct</span> <span class="nc">dinic</span> <span class="p">{</span> 364 <span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">src</span><span class="p">,</span> <span class="n">snk</span><span class="p">;</span> 365 <span class="kt">int</span> <span class="n">lr_src</span><span class="p">,</span> <span class="n">lr_snk</span><span class="p">,</span> <span class="n">lr_lsum</span><span class="p">;</span> <span class="c1">// !!! use this IFF use L-R flow !!!</span> 366 <span class="kt">int</span> <span class="n">cur</span><span class="p">[</span><span class="n">MAXN</span><span class="p">],</span> <span class="n">lvl</span><span class="p">[</span><span class="n">MAXN</span><span class="p">];</span> 367 <span class="k">struct</span> <span class="nc">edg</span> <span class="p">{</span> <span class="kt">int</span> <span class="n">idx</span><span class="p">,</span> <span class="n">cap</span><span class="p">,</span> <span class="n">rev</span><span class="p">;</span> <span class="p">};</span> 368 <span class="n">vector</span><span class="o"><</span><span class="n">edg</span><span class="o">></span> <span class="n">gph</span><span class="p">[</span><span class="n">MAXN</span><span class="p">];</span> 369 <span class="kt">void</span> <span class="n">add_edge</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">,</span> <span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">k</span><span class="p">)</span> <span class="p">{</span> 370 <span class="n">gph</span><span class="p">[</span><span class="n">u</span><span class="p">].</span><span class="n">push_back</span><span class="p">({</span> <span class="n">v</span><span class="p">,</span><span class="n">k</span><span class="p">,(</span><span class="kt">int</span><span class="p">)</span><span class="n">gph</span><span class="p">[</span><span class="n">v</span><span class="p">].</span><span class="n">size</span><span class="p">()</span> <span class="p">});</span> 371 <span class="n">gph</span><span class="p">[</span><span class="n">v</span><span class="p">].</span><span class="n">push_back</span><span class="p">({</span> <span class="n">u</span><span class="p">,</span><span class="mi">0</span><span class="p">,(</span><span class="kt">int</span><span class="p">)</span><span class="n">gph</span><span class="p">[</span><span class="n">u</span><span class="p">].</span><span class="n">size</span><span class="p">()</span><span class="o">-</span><span class="mi">1</span> <span class="p">});</span> 372 <span class="p">}</span> 373 <span class="c1">// !!! use this IFF use L-R flow !!!</span> 374 <span class="kt">void</span> <span class="n">add_lr_edge</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">,</span> <span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">l</span><span class="p">,</span> <span class="kt">int</span> <span class="n">r</span><span class="p">)</span> <span class="p">{</span>
375 <span class="n">add_edge</span><span class="p">(</span><span class="n">lr_src</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">l</span><span class="p">);</span> 376 <span class="n">add_edge</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">lr_snk</span><span class="p">,</span> <span class="n">l</span><span class="p">);</span> 377 <span class="n">add_edge</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">r</span><span class="o">-</span><span class="n">l</span><span class="p">);</span> 378 <span class="n">lr_lsum</span> <span class="o">+=</span> <span class="n">l</span><span class="p">;</span> 379 <span class="p">}</span> 380 <span class="kt">void</span> <span class="n">init</span><span class="p">()</span> <span class="p">{</span> 381 <span class="n">memset</span><span class="p">(</span><span class="n">cur</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="k">sizeof</span><span class="p">(</span><span class="n">cur</span><span class="p">));</span> 382 <span class="n">memset</span><span class="p">(</span><span class="n">lvl</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="k">sizeof</span><span class="p">(</span><span class="n">lvl</span><span class="p">));</span> 383 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">MAXN</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">gph</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">clear</span><span class="p">();</span> 384 <span class="n">src</span> <span class="o">=</span> <span class="n">MAXN</span><span class="o">-</span><span class="mi">4</span><span class="p">;</span> 385 <span class="n">snk</span> <span class="o">=</span> <span class="n">MAXN</span><span class="o">-</span><span class="mi">3</span><span class="p">;</span> 386 <span class="n">lr_src</span> <span class="o">=</span> <span class="n">MAXN</span><span class="o">-</span><span class="mi">2</span><span class="p">;</span> 387 <span class="n">lr_snk</span> <span class="o">=</span> <span class="n">MAXN</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span> 388 <span class="c1">//add_edge(snk, src, 2e9); // !!! use this IFF use L-R flow !!!</span> 389 <span class="p">}</span> 390 <span class="n">dinic</span><span class="p">()</span> <span class="p">{</span> 391 <span class="n">init</span><span class="p">();</span> 392 <span class="p">}</span> 393 <span class="kt">bool</span> <span class="n">bfs</span><span class="p">(</span><span class="kt">int</span> <span class="n">src</span><span class="p">,</span> <span class="kt">int</span> <span class="n">snk</span><span class="p">)</span> <span class="p">{</span> 394 <span class="n">queue</span><span class="o"><</span><span class="kt">int</span><span class="o">></span> <span class="n">que</span><span class="p">;</span> 395 <span class="n">memset</span><span class="p">(</span><span class="n">lvl</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="k">sizeof</span><span class="p">(</span><span class="n">lvl</span><span class="p">));</span> 396 <span class="n">lvl</span><span class="p">[</span><span class="n">src</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> 397 <span class="n">que</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">src</span><span class="p">);</span> 398 <span class="k">while</span> <span class="p">(</span><span class="o">!</span><span class="n">que</span><span class="p">.</span><span class="n">empty</span><span class="p">())</span> <span class="p">{</span>
399 <span class="kt">int</span> <span class="n">now</span> <span class="o">=</span> <span class="n">que</span><span class="p">.</span><span class="n">front</span><span class="p">();</span> <span class="n">que</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span> 400 <span class="k">for</span> <span class="p">(</span><span class="n">edg</span> <span class="n">nxt</span> <span class="o">:</span> <span class="n">gph</span><span class="p">[</span><span class="n">now</span><span class="p">])</span> <span class="p">{</span> 401 <span class="k">if</span> <span class="p">(</span><span class="n">nxt</span><span class="p">.</span><span class="n">cap</span> <span class="o">></span> <span class="mi">0</span> <span class="o">&&</span> <span class="n">lvl</span><span class="p">[</span><span class="n">nxt</span><span class="p">.</span><span class="n">idx</span><span class="p">]</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="p">{</span> 402 <span class="n">lvl</span><span class="p">[</span><span class="n">nxt</span><span class="p">.</span><span class="n">idx</span><span class="p">]</span> <span class="o">=</span> <span class="n">lvl</span><span class="p">[</span><span class="n">now</span><span class="p">]</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span> 403 <span class="n">que</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">nxt</span><span class="p">.</span><span class="n">idx</span><span class="p">);</span> 404 <span class="p">}</span> 405 <span class="p">}</span> 406 <span class="p">}</span> 407 <span class="k">return</span> <span class="n">lvl</span><span class="p">[</span><span class="n">snk</span><span class="p">]</span> <span class="o">!=</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span> 408 <span class="p">}</span> 409 <span class="n">ll</span> <span class="n">dfs</span><span class="p">(</span><span class="kt">int</span> <span class="n">now</span><span class="p">,</span> <span class="kt">int</span> <span class="n">snk</span><span class="p">,</span> <span class="kt">int</span> <span class="n">flw</span><span class="p">)</span> <span class="p">{</span> 410 <span class="k">if</span> <span class="p">(</span><span class="n">now</span> <span class="o">==</span> <span class="n">snk</span><span class="p">)</span> <span class="k">return</span> <span class="n">flw</span><span class="p">;</span> 411 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="o">&</span><span class="n">i</span> <span class="o">=</span> <span class="n">cur</span><span class="p">[</span><span class="n">now</span><span class="p">];</span> <span class="n">i</span> <span class="o"><</span> <span class="n">gph</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">size</span><span class="p">();</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> 412 <span class="n">edg</span> <span class="o">&</span><span class="n">nxt</span> <span class="o">=</span> <span class="n">gph</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="n">i</span><span class="p">];</span> 413 <span class="k">if</span> <span class="p">(</span><span class="n">nxt</span><span class="p">.</span><span class="n">cap</span> <span class="o">></span> <span class="mi">0</span> <span class="o">&&</span> <span class="n">lvl</span><span class="p">[</span><span class="n">nxt</span><span class="p">.</span><span class="n">idx</span><span class="p">]</span> <span class="o">==</span> <span class="n">lvl</span><span class="p">[</span><span class="n">now</span><span class="p">]</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
414 <span class="n">ll</span> <span class="n">ret</span> <span class="o">=</span> <span class="n">dfs</span><span class="p">(</span><span class="n">nxt</span><span class="p">.</span><span class="n">idx</span><span class="p">,</span> <span class="n">snk</span><span class="p">,</span> <span class="n">min</span><span class="p">(</span><span class="n">nxt</span><span class="p">.</span><span class="n">cap</span><span class="p">,</span> <span class="n">flw</span><span class="p">));</span> 415 <span class="k">if</span> <span class="p">(</span><span class="n">ret</span> <span class="o">></span> <span class="mi">0</span><span class="p">)</span> <span class="p">{</span> 416 <span class="n">nxt</span><span class="p">.</span><span class="n">cap</span> <span class="o">-=</span> <span class="n">ret</span><span class="p">;</span> 417 <span class="n">gph</span><span class="p">[</span><span class="n">nxt</span><span class="p">.</span><span class="n">idx</span><span class="p">][</span><span class="n">nxt</span><span class="p">.</span><span class="n">rev</span><span class="p">].</span><span class="n">cap</span> <span class="o">+=</span> <span class="n">ret</span><span class="p">;</span> 418 <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> 419 <span class="p">}</span> 420 <span class="p">}</span> 421 <span class="p">}</span> 422 <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> 423 <span class="p">}</span> 424 <span class="n">ll</span> <span class="n">match</span><span class="p">()</span> <span class="p">{</span> 425 <span class="n">ll</span> <span class="n">dap</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> 426 <span class="k">while</span> <span class="p">(</span><span class="n">bfs</span><span class="p">(</span><span class="n">src</span><span class="p">,</span> <span class="n">snk</span><span class="p">))</span> <span class="p">{</span> 427 <span class="n">memset</span><span class="p">(</span><span class="n">cur</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="k">sizeof</span><span class="p">(</span><span class="n">cur</span><span class="p">));</span> 428 <span class="n">ll</span> <span class="n">ret</span><span class="p">;</span> 429 <span class="k">while</span> <span class="p">(</span><span class="n">ret</span> <span class="o">=</span> <span class="n">dfs</span><span class="p">(</span><span class="n">src</span><span class="p">,</span> <span class="n">snk</span><span class="p">,</span> <span class="mf">2e9</span><span class="p">))</span> <span class="p">{</span> 430 <span class="n">dap</span> <span class="o">+=</span> <span class="n">ret</span><span class="p">;</span> 431 <span class="p">}</span> 432 <span class="p">}</span> 433 <span class="k">return</span> <span class="n">dap</span><span class="p">;</span> 434 <span class="p">}</span> 435 <span class="c1">// !!! use this IFF use L-R flow !!!</span> 436 <span class="kt">bool</span> <span class="n">lr_match</span><span class="p">()</span> <span class="p">{</span> 437 <span class="n">ll</span> <span class="n">dap</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> 438 <span class="k">while</span> <span class="p">(</span><span class="n">bfs</span><span class="p">(</span><span class="n">lr_src</span><span class="p">,</span> <span class="n">lr_snk</span><span class="p">))</span> <span class="p">{</span> 439 <span class="n">memset</span><span class="p">(</span><span class="n">cur</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="k">sizeof</span><span class="p">(</span><span class="n">cur</span><span class="p">));</span> 440 <span class="n">ll</span> <span class="n">ret</span><span class="p">;</span> 441 <span class="k">while</span> <span class="p">(</span><span class="n">ret</span> <span class="o">=</span> <span class="n">dfs</span><span class="p">(</span><span class="n">lr_src</span><span class="p">,</span> <span class="n">lr_snk</span><span class="p">,</span> <span class="mf">2e9</span><span class="p">))</span> <span class="p">{</span>
442 <span class="n">dap</span> <span class="o">+=</span> <span class="n">ret</span><span class="p">;</span> 443 <span class="p">}</span> 444 <span class="p">}</span> 445 <span class="k">return</span> <span class="p">(</span><span class="n">dap</span> <span class="o">==</span> <span class="n">lr_lsum</span><span class="p">);</span> <span class="c1">// true == L-R feasible</span> 446 <span class="p">}</span> 447<span class="p">}</span> <span class="n">flow</span><span class="p">;</span> 448</code></pre></div></div> 449 450<h3 id="lr-flow-ììíë¡ì°">LR Flow ììíë¡ì°</h3> 451 452<p>ì ì Aìì ì ì Bë¡, íí L, ìí Rì¸ ê°ì ì´ ìì ë íì´ë²</p> 453 454<p>(1) [ AâB ì ë L, ë¹ì© -1ì¸ ê°ì ], [ AâB ì ë R-L, ë¹ì© 0ì¸ ê°ì ] ì´í mincost-maxflow</p> 455<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="kt">void</span> <span class="nf">add_edge</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">,</span> <span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">l</span><span class="p">,</span> <span class="kt">int</span> <span class="n">r</span><span class="p">)</span> <span class="p">{</span> 456 <span class="n">addEdge</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">);</span> 457 <span class="n">addEdge</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">r</span> <span class="o">-</span> <span class="n">l</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span> 458<span class="p">}</span> 459</code></pre></div></div> 460 461<p>(2) [ ìë¡ì´ source â B, ì ë L ], [ A â ìë¡ì´ sink, ì ë L ], [ A â B, ì ë R-L ], [ 기존 sink â 기존 source, ì ë 무í ] ì´í, [ ìë¡ì´ source â ìë¡ì´ sink ]ì ìµë ì ëì´ Lì í©ì´ ëëì§ íì¸</p> 462<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="err">ëë</span> <span class="err">ì½ë</span> <span class="err">참조</span> 463</code></pre></div></div> 464 465<h3 id="mcmf-ì ì¨ì ìí-spfa">MCMF ì ì¨ì ìí (spfa)</h3> 466 467<p><code class="language-plaintext highlighter-rouge">O((V+E)f)</code></p> 468 469<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include</span> <span class="cpf"><vector></span><span class="cp"> 470#include</span> <span class="cpf"><algorithm></span><span class="cp"> 471#include</span> <span class="cpf"><queue></span><span class="cp"> 472#include</span> <span class="cpf"><cstring></span><span class="cp"> 473</span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> 474<span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> 475<span class="k">const</span> <span class="kt">int</span> <span class="n">MAXN</span> <span class="o">=</span> <span class="mi">1111</span><span class="p">;</span> 476<span class="k">struct</span> <span class="nc">mcmf</span> <span class="p">{</span> 477 <span class="kt">int</span> <span class="n">src</span><span class="p">,</span> <span class="n">snk</span><span class="p">;</span> 478 <span class="kt">int</span> <span class="n">prv_v</span><span class="p">[</span><span class="n">MAXN</span><span class="p">],</span> <span class="n">prv_e</span><span class="p">[</span><span class="n">MAXN</span><span class="p">],</span> <span class="n">dst</span><span class="p">[</span><span class="n">MAXN</span><span class="p">],</span> <span class="n">inq</span><span class="p">[</span><span class="n">MAXN</span><span class="p">];</span> 479 <span class="k">struct</span> <span class="nc">edg</span> <span class="p">{</span> <span class="kt">int</span> <span class="n">idx</span><span class="p">,</span> <span class="n">cap</span><span class="p">,</span> <span class="n">cst</span><span class="p">,</span> <span class="n">rev</span><span class="p">;</span> <span class="p">};</span> 480 <span class="n">vector</span><span class="o"><</span><span class="n">edg</span><span class="o">></span> <span class="n">gph</span><span class="p">[</span><span class="n">MAXN</span><span class="p">];
480</span> 481 <span class="kt">void</span> <span class="n">add_edge</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">,</span> <span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">f</span><span class="p">,</span> <span class="kt">int</span> <span class="n">c</span><span class="p">)</span> <span class="p">{</span> 482 <span class="n">gph</span><span class="p">[</span><span class="n">u</span><span class="p">].</span><span class="n">push_back</span><span class="p">({</span><span class="n">v</span><span class="p">,</span> <span class="n">f</span><span class="p">,</span> <span class="n">c</span><span class="p">,</span> <span class="n">gph</span><span class="p">[</span><span class="n">v</span><span class="p">].</span><span class="n">size</span><span class="p">()});</span> 483 <span class="n">gph</span><span class="p">[</span><span class="n">v</span><span class="p">].</span><span class="n">push_back</span><span class="p">({</span><span class="n">u</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="o">-</span><span class="n">c</span><span class="p">,</span> <span class="n">gph</span><span class="p">[</span><span class="n">u</span><span class="p">].</span><span class="n">size</span><span class="p">()</span> <span class="o">-</span> <span class="mi">1</span><span class="p">});</span> 484 <span class="p">}</span> 485 <span class="kt">void</span> <span class="n">init</span><span class="p">()</span> <span class="p">{</span> 486 <span class="n">memset</span><span class="p">(</span><span class="n">prv_v</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="k">sizeof</span><span class="p">(</span><span class="n">prv_v</span><span class="p">));</span> 487 <span class="n">memset</span><span class="p">(</span><span class="n">prv_e</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="k">sizeof</span><span class="p">(</span><span class="n">prv_e</span><span class="p">));</span> 488 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">MAXN</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">gph</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">clear</span><span class="p">();</span> 489 <span class="n">src</span> <span class="o">=</span> <span class="n">MAXN</span><span class="o">-</span><span class="mi">2</span><span class="p">;</span> 490 <span class="n">snk</span> <span class="o">=</span> <span class="n">MAXN</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span> 491 <span class="p">}</span> 492 <span class="n">mcmf</span><span class="p">()</span> <span class="p">{</span> 493 <span class="n">init</span><span class="p">();</span> 494 <span class="p">}</span> 495 <span class="kt">bool</span> <span class="n">spfa</span><span class="p">()</span> <span class="p">{</span> 496 <span class="n">memset</span><span class="p">(</span><span class="n">dst</span><span class="p">,</span> <span class="mh">0x3f</span><span class="p">,</span> <span class="k">sizeof</span><span class="p">(</span><span class="n">dst</span><span class="p">));</span> 497 <span class="n">memset</span><span class="p">(</span><span class="n">inq</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="k">sizeof</span><span class="p">(</span><span class="n">inq</span><span class="p">));</span> 498 <span class="n">queue</span><span class="o"><</span><span class="kt">int</span><span class="o">></span> <span class="n">que</span><span class="p">;</span> 499 <span class="n">que</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">src</span><span class="p">);</span>
500 <span class="n">inq</span><span class="p">[</span><span class="n">src</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> 501 <span class="n">dst</span><span class="p">[</span><span class="n">src</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> 502 <span class="k">while</span> <span class="p">(</span><span class="o">!</span><span class="n">que</span><span class="p">.</span><span class="n">empty</span><span class="p">())</span> <span class="p">{</span> 503 <span class="kt">int</span> <span class="n">now</span> <span class="o">=</span> <span class="n">que</span><span class="p">.</span><span class="n">front</span><span class="p">();</span> 504 <span class="n">que</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span> 505 <span class="n">inq</span><span class="p">[</span><span class="n">now</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> 506 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">gph</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">size</span><span class="p">();</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> 507 <span class="n">edg</span> <span class="o">&</span><span class="n">nxt</span> <span class="o">=</span> <span class="n">gph</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="n">i</span><span class="p">];</span> 508 <span class="k">if</span> <span class="p">(</span><span class="n">nxt</span><span class="p">.</span><span class="n">cap</span> <span class="o">></span> <span class="mi">0</span> <span class="o">&&</span> <span class="n">dst</span><span class="p">[</span><span class="n">nxt</span><span class="p">.</span><span class="n">idx</span><span class="p">]</span> <span class="o">></span> <span class="n">dst</span><span class="p">[</span><span class="n">now</span><span class="p">]</span> <span class="o">+</span> <span class="n">nxt</span><span class="p">.</span><span class="n">cst</span><span class="p">)</span> <span class="p">{</span> 509 <span class="n">dst</span><span class="p">[</span><span class="n">nxt</span><span class="p">.</span><span class="n">idx</span><span class="p">]</span> <span class="o">=</span> <span class="n">dst</span><span class="p">[</span><span class="n">now</span><span class="p">]</span> <span class="o">+</span> <span class="n">nxt</span><span class="p">.</span><span class="n">cst</span><span class="p">;</span> 510 <span class="n">prv_v</span><span class="p">[</span><span class="n">nxt</span><span class="p">.</span><span class="n">idx</span><span class="p">]</span> <span class="o">=</span> <span class="n">now</span><span class="p">;</span> 511 <span class="n">prv_e</span><span class="p">[</span><span class="n">nxt</span><span class="p">.</span><span class="n">idx</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span> 512 <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">inq</span><span class="p">[</span><span class="n">nxt</span><span class="p">.</span><span class="n">idx</span><span class="p">])</span> 513 <span class="n">que</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">nxt</span><span class="p">.</span><span class="n">idx</span><span class="p">),</span> <span class="n">inq</span><span class="p">[</span><span class="n">nxt</span><span class="p">.</span><span class="n">idx</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
514 <span class="p">}</span> 515 <span class="p">}</span> 516 <span class="p">}</span> 517 <span class="k">return</span> <span class="n">dst</span><span class="p">[</span><span class="n">snk</span><span class="p">]</span> <span class="o">!=</span> <span class="mh">0x3f3f3f3f</span><span class="p">;</span> 518 <span class="p">}</span> 519 <span class="n">pair</span><span class="o"><</span><span class="kt">int</span><span class="p">,</span> <span class="kt">int</span><span class="o">></span> <span class="n">match</span><span class="p">()</span> <span class="p">{</span> 520 <span class="kt">int</span> <span class="n">dap_cst</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">dap_flw</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> 521 <span class="k">while</span> <span class="p">(</span><span class="n">spfa</span><span class="p">())</span> <span class="p">{</span> 522 <span class="kt">int</span> <span class="n">mn_flw</span> <span class="o">=</span> <span class="mf">2e9</span><span class="p">;</span> 523 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">now</span> <span class="o">=</span> <span class="n">snk</span><span class="p">;</span> <span class="n">now</span> <span class="o">!=</span> <span class="n">src</span><span class="p">;</span> <span class="n">now</span> <span class="o">=</span> <span class="n">prv_v</span><span class="p">[</span><span class="n">now</span><span class="p">])</span> <span class="p">{</span> 524 <span class="kt">int</span> <span class="n">prv</span> <span class="o">=</span> <span class="n">prv_v</span><span class="p">[</span><span class="n">now</span><span class="p">],</span> <span class="n">idx</span> <span class="o">=</span> <span class="n">prv_e</span><span class="p">[</span><span class="n">now</span><span class="p">];</span> 525 <span class="n">mn_flw</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">mn_flw</span><span class="p">,</span> <span class="n">gph</span><span class="p">[</span><span class="n">prv</span><span class="p">][</span><span class="n">idx</span><span class="p">].</span><span class="n">cap</span><span class="p">);</span> 526 <span class="p">}</span> 527 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">now</span> <span class="o">=</span> <span class="n">snk</span><span class="p">;</span> <span class="n">now</span> <span class="o">!=</span> <span class="n">src</span><span class="p">;</span> <span class="n">now</span> <span class="o">=</span> <span class="n">prv_v</span><span class="p">[</span><span class="n">now</span><span class="p">])</span> <span class="p">{</span> 528 <span class="kt">int</span> <span class="n">prv</span> <span class="o">=</span> <span class="n">prv_v</span><span class="p">[</span><span class="n">now</span><span class="p">],</span> <span class="n">idx</span> <span class="o">=</span> <span class="n">prv_e</span><span class="p">[</span><span class="n">now</span><span class="p">];</span> 529 <span class="n">gph</span><span class="p">[</span><span class="n">prv</span><span class="p">][</span><span class="n">idx</span><span class="p">].</span><span class="n">cap</span> <span class="o">-=</span> <span class="n">mn_flw</span><span class="p">;</span> 530 <span class="n">gph</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="n">gph</span><span class="p">[</span><span class="n">prv</span><span class="p">][</span><span class="n">idx</span><span class="p">].</span><span class="n">rev</span><span class="p">].</span><span class="n">cap</span> <span class="o">+=</span> <span class="n">mn_flw</span><span class="p">;</span> 531 <span class="n">dap_cst</span> <span class="o">+=</span> <span class="n">mn_flw</span> <span class="o">*</span> <span class="n">gph</span><span class="p">[</span><span class="n">prv</span><span class="p">][</span><span class="n">idx</span><span class="p">].</span><span class="n">cst</span><span class="p">;</span>
532 <span class="p">}</span> 533 <span class="n">dap_flw</span> <span class="o">+=</span> <span class="n">mn_flw</span><span class="p">;</span> 534 <span class="p">}</span> 535 <span class="k">return</span> <span class="n">make_pair</span><span class="p">(</span><span class="n">dap_flw</span><span class="p">,</span> <span class="n">dap_cst</span><span class="p">);</span> 536 <span class="p">}</span> 537<span class="p">};</span> 538</code></pre></div></div> 539 540<h2 id="ê·¸ëí-ë°-í¸ë¦¬-graph-and-tree">ê·¸ëí ë° í¸ë¦¬ Graph and Tree</h2> 541 542<h3 id="lca-ìµì-ê³µíµ-ì¡°ì">LCA ìµì ê³µíµ ì¡°ì</h3> 543 544<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include</span> <span class="cpf"><algorithm></span><span class="cp"> 545#include</span> <span class="cpf"><vector></span><span class="cp"> 546</span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> 547<span class="k">const</span> <span class="kt">int</span> <span class="n">n_</span> <span class="o">=</span> <span class="mf">1e5</span> <span class="o">+</span> <span class="mi">5</span><span class="p">;</span> 548<span class="k">const</span> <span class="kt">int</span> <span class="n">d_</span> <span class="o">=</span> <span class="mi">17</span><span class="p">;</span> <span class="c1">// 2^d > n</span> 549<span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">d</span><span class="p">;</span> 550<span class="kt">int</span> <span class="n">dph</span><span class="p">[</span><span class="n">n_</span><span class="p">],</span> <span class="n">par</span><span class="p">[</span><span class="n">n_</span><span class="p">][</span><span class="n">d_</span><span class="p">];</span> 551<span class="n">vector</span><span class="o"><</span><span class="kt">int</span><span class="o">></span> <span class="n">gph</span><span class="p">[</span><span class="n">n_</span><span class="p">];</span> 552<span class="kt">void</span> <span class="nf">setLCA</span><span class="p">(</span><span class="kt">int</span> <span class="n">now</span><span class="p">,</span> <span class="kt">int</span> <span class="n">cnt</span><span class="p">)</span> <span class="p">{</span> 553 <span class="n">dph</span><span class="p">[</span><span class="n">now</span><span class="p">]</span> <span class="o">=</span> <span class="n">cnt</span><span class="o">++</span><span class="p">;</span> 554 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o"><=</span> <span class="n">d</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> 555 <span class="n">par</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">par</span><span class="p">[</span><span class="n">par</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]][</span><span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">];</span> 556 <span class="k">for</span> <span class="p">(</span><span class="k">auto</span> <span class="n">nxt</span> <span class="o">:</span> <span class="n">gph</span><span class="p">[</span><span class="n">now</span><span class="p">])</span> <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">dph</span><span class="p">[</span><span class="n">nxt</span><span class="p">])</span> 557 <span class="n">par</span><span class="p">[</span><span class="n">nxt</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="n">now</span><span class="p">,</span> <span class="n">setLCA</span><span class="p">(</span><span class="n">nxt</span><span class="p">,</span> <span class="n">cnt</span><span class="p">);</span> 558<span class="p">}</span> 559<span class="kt">int</span> <span class="n">getLCA</span><span class="p">(</span><span class="kt">int</span> <span class="n">a</span><span class="p">,</span> <span class="kt">int</span> <span class="n">b</span><span class="p">)</span> <span class="p">{</span> 560 <span class="k">if</span> <span class="p">(</span><span class="n">dph</span><span class="p">[</span><span class="n">a</span><span class="p">]</span> <span class="o"><</span> <span class="n">dph</span><span class="p">[</span><span class="n">b</span><span class="p">])</span> <span class="n">swap</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">);</span> 561 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">d</span><span class="p">;</span> <span class="n">i</span> <span class="o">>=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">)</span> <span class="k">if</span> <span class="p">(</span><span class="n">dph</span><span class="p">[</span><span class="n">b</span><span class="p">]</span> <span class="o"><=</span> <span class="n">dph</span><span class="p">[</span><span class="n">par</span><span class="p">[</span><span class="n">a</span><span class="p">][</span><span class="n">i</span><span class="p">]])</span>
562 <span class="n">a</span> <span class="o">=</span> <span class="n">par</span><span class="p">[</span><span class="n">a</span><span class="p">][</span><span class="n">i</span><span class="p">];</span> 563 <span class="k">if</span> <span class="p">(</span><span class="n">a</span> <span class="o">==</span> <span class="n">b</span><span class="p">)</span> <span class="k">return</span> <span class="n">a</span><span class="p">;</span> 564 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">d</span><span class="p">;</span> <span class="n">i</span> <span class="o">>=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">)</span> <span class="k">if</span> <span class="p">(</span><span class="n">par</span><span class="p">[</span><span class="n">a</span><span class="p">][</span><span class="n">i</span><span class="p">]</span> <span class="o">!=</span> <span class="n">par</span><span class="p">[</span><span class="n">b</span><span class="p">][</span><span class="n">i</span><span class="p">])</span> 565 <span class="n">a</span> <span class="o">=</span> <span class="n">par</span><span class="p">[</span><span class="n">a</span><span class="p">][</span><span class="n">i</span><span class="p">],</span> <span class="n">b</span> <span class="o">=</span> <span class="n">par</span><span class="p">[</span><span class="n">b</span><span class="p">][</span><span class="n">i</span><span class="p">];</span> 566 <span class="k">return</span> <span class="n">par</span><span class="p">[</span><span class="n">a</span><span class="p">][</span><span class="mi">0</span><span class="p">];</span> 567<span class="p">}</span> 568<span class="kt">int</span> <span class="n">main</span><span class="p">()</span> <span class="p">{</span> 569 <span class="k">for</span> <span class="p">(</span><span class="n">d</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="p">(</span><span class="mi">1</span> <span class="o"><<</span> <span class="n">d</span><span class="p">)</span> <span class="o"><=</span> <span class="n">n</span><span class="p">;</span> <span class="n">d</span><span class="o">++</span><span class="p">);</span> <span class="n">d</span><span class="o">--</span><span class="p">;</span> 570 <span class="n">setLCA</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">);</span> 571<span class="p">}</span> 572</code></pre></div></div> 573 574<h3 id="lca-í¸ë¦¬ìì-ë-ë ¸ë-ì¬ì´ì-거리">LCA í¸ë¦¬ìì ë ë ¸ë ì¬ì´ì 거리</h3> 575 576<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include</span> <span class="cpf"><algorithm></span><span class="cp"> 577#include</span> <span class="cpf"><vector></span><span class="cp"> 578</span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> 579<span class="k">const</span> <span class="kt">int</span> <span class="n">n_</span> <span class="o">=</span> <span class="mf">1e5</span> <span class="o">+</span> <span class="mi">5</span><span class="p">;</span> 580<span class="k">const</span> <span class="kt">int</span> <span class="n">d_</span> <span class="o">=</span> <span class="mi">17</span><span class="p">;</span> <span class="c1">// 2^d > n</span> 581<span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">d</span><span class="p">;</span> 582<span class="kt">int</span> <span class="n">dph</span><span class="p">[</span><span class="n">n_</span><span class="p">],</span> <span class="n">par</span><span class="p">[</span><span class="n">n_</span><span class="p">][</span><span class="n">d_</span><span class="p">];</span> 583<span class="n">vector</span><span class="o"><</span><span class="kt">int</span><span class="o">></span> <span class="n">gph</span><span class="p">[</span><span class="n">n_</span><span class="p">];
583</span> 584<span class="kt">void</span> <span class="nf">setLCA</span><span class="p">(</span><span class="kt">int</span> <span class="n">now</span><span class="p">,</span> <span class="kt">int</span> <span class="n">cnt</span><span class="p">)</span> <span class="p">{</span> 585 <span class="n">dph</span><span class="p">[</span><span class="n">now</span><span class="p">]</span> <span class="o">=</span> <span class="n">cnt</span><span class="o">++</span><span class="p">;</span> 586 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o"><=</span> <span class="n">d</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> 587 <span class="n">par</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">par</span><span class="p">[</span><span class="n">par</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]][</span><span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">];</span> 588 <span class="k">for</span> <span class="p">(</span><span class="k">auto</span> <span class="n">nxt</span> <span class="o">:</span> <span class="n">gph</span><span class="p">[</span><span class="n">now</span><span class="p">])</span> <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">dph</span><span class="p">[</span><span class="n">nxt</span><span class="p">])</span> 589 <span class="n">par</span><span class="p">[</span><span class="n">nxt</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="n">now</span><span class="p">,</span> <span class="n">setLCA</span><span class="p">(</span><span class="n">nxt</span><span class="p">,</span> <span class="n">cnt</span><span class="p">);</span> 590<span class="p">}</span> 591<span class="kt">int</span> <span class="n">dst</span><span class="p">(</span><span class="kt">int</span> <span class="n">a</span><span class="p">,</span> <span class="kt">int</span> <span class="n">b</span><span class="p">)</span> <span class="p">{</span> 592 <span class="kt">int</span> <span class="n">ret</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> 593 <span class="k">if</span> <span class="p">(</span><span class="n">dph</span><span class="p">[</span><span class="n">a</span><span class="p">]</span> <span class="o"><</span> <span class="n">dph</span><span class="p">[</span><span class="n">b</span><span class="p">])</span> <span class="n">swap</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">);</span> 594 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">d</span><span class="p">;</span> <span class="n">i</span> <span class="o">>=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">)</span> <span class="k">if</span> <span class="p">(</span><span class="n">dph</span><span class="p">[</span><span class="n">b</span><span class="p">]</span> <span class="o"><=</span> <span class="n">dph</span><span class="p">[</span><span class="n">par</span><span class="p">[</span><span class="n">a</span><span class="p">][</span><span class="n">i</span><span class="p">]])</span> <span class="p">{</span> 595 <span class="n">a</span> <span class="o">=</span> <span class="n">par</span><span class="p">[</span><span class="n">a</span><span class="p">][</span><span class="n">i</span><span class="p">];</span> 596 <span class="n">ret</span> <span class="o">+=</span> <span class="p">(</span><span class="mi">1</span><span class="o"><<</span><span class="n">i</span><span class="p">);</span> 597 <span class="p">}</span> 598 <span class="k">if</span> <span class="p">(</span><span class="n">a</span> <span class="o">==</span> <span class="n">b</span><span class="p">)</span> <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> 599 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">d</span><span class="p">;</span> <span class="n">i</span> <span class="o">>=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">)</span> <span class="k">if</span> <span class="p">(</span><span class="n">par</span><span class="p">[</span><span class="n">a</span><span class="p">][</span><span class="n">i</span><span class="p">]</span> <span class="o">!=</span> <span class="n">par</span><span class="p">[</span><span class="n">b</span><span class="p">][</span><span class="n">i</span><span class="p">])</span> <span class="p">{</span>
600 <span class="n">a</span> <span class="o">=</span> <span class="n">par</span><span class="p">[</span><span class="n">a</span><span class="p">][</span><span class="n">i</span><span class="p">],</span> <span class="n">b</span> <span class="o">=</span> <span class="n">par</span><span class="p">[</span><span class="n">b</span><span class="p">][</span><span class="n">i</span><span class="p">];</span> 601 <span class="n">ret</span> <span class="o">+=</span> <span class="p">(</span><span class="mi">1</span><span class="o"><<</span><span class="n">i</span><span class="p">)</span><span class="o">*</span><span class="mi">2</span><span class="p">;</span> 602 <span class="p">}</span> 603 <span class="k">return</span> <span class="n">ret</span><span class="o">+</span><span class="mi">2</span><span class="p">;</span> 604<span class="p">}</span> 605<span class="kt">int</span> <span class="n">main</span><span class="p">()</span> <span class="p">{</span> 606 <span class="k">for</span> <span class="p">(</span><span class="n">d</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="p">(</span><span class="mi">1</span> <span class="o"><<</span> <span class="n">d</span><span class="p">)</span> <span class="o"><=</span> <span class="n">n</span><span class="p">;</span> <span class="n">d</span><span class="o">++</span><span class="p">);</span> <span class="n">d</span><span class="o">--</span><span class="p">;</span> 607 <span class="n">setLCA</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">);</span> 608<span class="p">}</span> 609</code></pre></div></div> 610 611<h3 id="cut-node-ë¨ì ì ">Cut Node ë¨ì ì </h3> 612 613<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include</span> <span class="cpf"><algorithm></span><span class="cp"> 614#include</span> <span class="cpf"><vector></span><span class="cp"> 615</span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> 616 617<span class="kt">int</span> <span class="n">cnt</span><span class="p">,</span> <span class="n">chk</span><span class="p">[</span><span class="mi">10001</span><span class="p">],</span> <span class="n">isCutNode</span><span class="p">[</span><span class="mi">10001</span><span class="p">];</span> 618<span class="n">vector</span><span class="o"><</span><span class="kt">int</span><span class="o">></span> <span class="n">gph</span><span class="p">[</span><span class="mi">10001</span><span class="p">];</span> 619 620<span class="kt">void</span> <span class="nf">findCutNode</span><span class="p">(</span><span class="kt">int</span> <span class="n">now</span><span class="p">,</span> <span class="kt">int</span> <span class="n">isRoot</span><span class="p">)</span> <span class="p">{</span> 621 <span class="kt">int</span> <span class="n">vcnt</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">vmin</span> <span class="o">=</span> <span class="n">n</span><span class="p">;</span> 622 <span class="n">chk</span><span class="p">[</span><span class="n">now</span><span class="p">]</span> <span class="o">=</span> <span class="o">++</span><span class="n">cnt</span><span class="p">;</span> 623 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">nxt</span> <span class="o">:</span> <span class="n">gph</span><span class="p">[</span><span class="n">now</span><span class="p">])</span> <span class="p">{</span> 624 <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">chk</span><span class="p">[</span><span class="n">nxt</span><span class="p">])</span> <span class="p">{</span> 625 <span class="n">findCutNode</span><span class="p">(</span><span class="n">nxt</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span> 626 <span class="k">if</span> <span class="p">(</span><span class="n">chk</span><span class="p">[</span><span class="n">nxt</span><span class="p">]</span> <span class="o">==</span> <span class="n">chk</span><span class="p">[</span><span class="n">now</span><span class="p">])</span> <span class="n">
626isCutNode</span><span class="p">[</span><span class="n">now</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> 627 <span class="n">vcnt</span><span class="o">++</span><span class="p">;</span> 628 <span class="p">}</span> 629 <span class="n">vmin</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">vmin</span><span class="p">,</span> <span class="n">chk</span><span class="p">[</span><span class="n">nxt</span><span class="p">]);</span> 630 <span class="p">}</span> 631 <span class="n">chk</span><span class="p">[</span><span class="n">now</span><span class="p">]</span> <span class="o">=</span> <span class="n">vmin</span><span class="p">;</span> 632 <span class="k">if</span> <span class="p">(</span><span class="n">isRoot</span><span class="p">)</span> <span class="n">isCutNode</span><span class="p">[</span><span class="n">now</span><span class="p">]</span> <span class="o">=</span> <span class="n">vcnt</span> <span class="o">>=</span> <span class="mi">2</span><span class="p">;</span> 633<span class="p">}</span> 634 635<span class="kt">int</span> <span class="n">main</span><span class="p">()</span> <span class="p">{</span> 636 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o"><=</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> 637 <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">chk</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">findCutNode</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="mi">1</span><span class="p">);</span> 638 <span class="p">}</span> 639<span class="p">}</span> 640</code></pre></div></div> 641 642<h3 id="cut-edge-ë¨ì ì ">Cut Edge ë¨ì ì </h3> 643 644<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include</span> <span class="cpf"><vector></span><span class="cp"> 645#include</span> <span class="cpf"><algorithm></span><span class="cp"> 646</span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> 647 648<span class="kt">int</span> <span class="n">cnt</span><span class="p">,</span> <span class="n">chk</span><span class="p">[</span><span class="mi">100001</span><span class="p">];</span> 649<span class="n">vector</span><span class="o"><</span><span class="kt">int</span><span class="o">></span> <span class="n">gph</span><span class="p">[</span><span class="mi">100001</span><span class="p">];</span> 650<span class="n">vector</span><span class="o"><</span><span class="n">pair</span><span class="o"><</span><span class="kt">int</span><span class="p">,</span> <span class="kt">int</span><span class="o">></span> <span class="o">></span> <span class="n">cutEdge</span><span class="p">;</span> 651 652<span class="kt">int</span> <span class="nf">findCutEdge</span><span class="p">(</span><span class="kt">int</span> <span class="n">now</span><span class="p">,</span> <span class="kt">int</span> <span class="n">par</span><span class="p">)</span> <span class="p">{</span> 653 <span class="kt">int</span> <span class="n">ret</span> <span class="o">=</span> <span class="n">chk</span><span class="p">[</span><span class="n">now</span><span class="p">]</span> <span class="o">=</span> <span class="o">++</span><span class="n">cnt</span><span class="p">;</span> 654 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">nxt</span> <span class="o">:</span> <span class="n">gph</span><span class="p">[</span><span class="n">now</span><span class="p">])</span> <span class="p">{</span> 655 <span class="k">if</span> <span class="p">(</span><span class="n">par</span> <span class="o">==</span> <span class="n">nxt</span><span class="p">)</span> <span class="k">continue</span><span class="p">;</span>
656 <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">chk</span><span class="p">[</span><span class="n">nxt</span><span class="p">])</span> <span class="p">{</span> 657 <span class="kt">int</span> <span class="n">low</span> <span class="o">=</span> <span class="n">findCutEdge</span><span class="p">(</span><span class="n">nxt</span><span class="p">,</span> <span class="n">now</span><span class="p">);</span> 658 <span class="k">if</span> <span class="p">(</span><span class="n">low</span> <span class="o">></span> <span class="n">chk</span><span class="p">[</span><span class="n">now</span><span class="p">])</span> <span class="p">{</span> 659 <span class="n">cutEdge</span><span class="p">.</span><span class="n">push_back</span><span class="p">({</span> <span class="n">min</span><span class="p">(</span><span class="n">now</span><span class="p">,</span><span class="n">nxt</span><span class="p">),</span><span class="n">max</span><span class="p">(</span><span class="n">now</span><span class="p">,</span><span class="n">nxt</span><span class="p">)</span> <span class="p">});</span> 660 <span class="p">}</span> 661 <span class="n">ret</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">ret</span><span class="p">,</span> <span class="n">low</span><span class="p">);</span> 662 <span class="p">}</span> 663 <span class="k">else</span> <span class="p">{</span> 664 <span class="n">ret</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">ret</span><span class="p">,</span> <span class="n">chk</span><span class="p">[</span><span class="n">nxt</span><span class="p">]);</span> 665 <span class="p">}</span> 666 <span class="p">}</span> 667 <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> 668<span class="p">}</span> 669 670<span class="kt">int</span> <span class="n">main</span><span class="p">()</span> <span class="p">{</span> 671 <span class="n">findCutEdge</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">);</span> 672<span class="p">}</span> 673</code></pre></div></div> 674 675<h2 id="dp-dynamic-programming-ëí¼-ëì ê³íë²">DP Dynamic Programming ëí¼ ëì ê³íë²</h2> 676 677<h3 id="convex-hull-trick-cht-컨벡ì¤-í-í¸ë¦">Convex Hull Trick CHT ì»¨ë²¡ì¤ í í¸ë¦</h3> 678 679<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">TODO</span> 680</code></pre></div></div> 681 682<h2 id="math-ìí">Math ìí</h2> 683 684<h3 id="eratos-get-prime-ìë¼í ì¤í ë¤ì¤ì-ì²´-ìì">Eratos Get Prime ìë¼í ì¤í ë¤ì¤ì ì²´ ìì</h3> 685 686<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="c1">// [s, e] 구ê°ì ììë¤ì ì¤ë¦ì°¨ìì¼ë¡ 리í´í¨</span> 687<span class="kt">bool</span> <span class="n">chkP</span><span class="p">[</span><span class="mi">10000001</span><span class="p">];</span> <span class="c1">// ë°°ì´ í¬ê¸° 주ì</span> 688<span class="n">vector</span><span class="o"><</span><span class="n">ll</span><span class="o">></span> <span class="n">getPrimes</span><span class="p">(</span><span class="n">ll</span> <span class="n">s</span><span class="p">,</span> <span class="n">ll</span> <span class="n">e</span><span class="p">)</span> <span class="p">{</span> 689 <span class="n">vector</span><span class="o"><</span><span class="n">ll</span><span class="o">></span> <span class="n">ret</span><span class="p">;</span> 690 <span class="k">for</span> <span class="p">(</span><span class="n">ll</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span> <span class="n">i</span><span class="o">*</span><span class="n">i</span> <span class="o"><=</span> <span class="n">e</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">chkP</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>
691 <span class="k">for</span> <span class="p">(</span><span class="n">ll</span> <span class="n">j</span> <span class="o">=</span> <span class="n">i</span><span class="o">*</span><span class="n">i</span><span class="p">;</span> <span class="n">j</span> <span class="o"><=</span> <span class="n">e</span><span class="p">;</span> <span class="n">j</span><span class="o">+=</span><span class="n">i</span><span class="p">)</span> <span class="n">chkP</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> 692 <span class="k">for</span> <span class="p">(</span><span class="n">ll</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span> <span class="n">i</span> <span class="o"><=</span> <span class="n">e</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">chkP</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&&</span> <span class="n">s</span> <span class="o"><=</span> <span class="n">i</span> <span class="o">&&</span> <span class="n">i</span> <span class="o"><=</span> <span class="n">e</span><span class="p">)</span> 693 <span class="n">ret</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> 694 <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> 695<span class="p">}</span> 696</code></pre></div></div> 697 698<h3 id="prime-factorization-soinsu-ìì¸ì-ë¶í´">Prime Factorization Soinsu ìì¸ì ë¶í´</h3> 699 700<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="c1">// ë°ë§ 리í´í¨, ì¤ë³µ ìì</span> 701<span class="n">vector</span><span class="o"><</span><span class="n">ll</span><span class="o">></span> <span class="n">getSoinsu</span><span class="p">(</span><span class="n">ll</span> <span class="n">x</span><span class="p">)</span> <span class="p">{</span> 702 <span class="n">ll</span> <span class="n">y</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span> 703 <span class="n">vector</span><span class="o"><</span><span class="n">ll</span><span class="o">></span> <span class="n">ret</span><span class="p">;</span> 704 <span class="k">for</span> <span class="p">(</span><span class="n">ll</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span> <span class="n">i</span><span class="o">*</span><span class="n">i</span> <span class="o"><=</span> <span class="n">x</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> 705 <span class="k">if</span> <span class="p">(</span><span class="n">y</span><span class="o">%</span><span class="n">i</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="p">{</span> 706 <span class="n">ret</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> 707 <span class="k">while</span> <span class="p">(</span><span class="n">y</span><span class="o">%</span><span class="n">i</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="n">y</span> <span class="o">/=</span> <span class="n">i</span><span class="p">;</span> 708 <span class="p">}</span> 709 <span class="p">}</span> 710 <span class="k">if</span> <span class="p">(</span><span class="n">y</span> <span class="o">!=</span> <span class="mi">1</span><span class="p">)</span> <span class="n">ret</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">y</span><span class="p">);</span> 711 <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> 712<span class="p">}</span> 713</code></pre></div></div> 714 715<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="c1">// (ë°, ì§ì) ìë¤ì 리í´í¨, ë°ì ëí´ì ì¤ë¦ì°¨ìì¼ë¡ 리í´í¨</span> 716<span class="n">vector</span><span class="o"><</span><span class="n">pair</span><span class="o"><</span><span class="n">ll</span><span class="p">,</span> <span class="kt">int</span><span class="o">></span> <span class="o">></span> <span class="n">getSoinsu</span><span class="p">(</span><span class="n">ll</span> <span class="n">x</span><span class="p">)</span> <span class="p">{</span> 717 <span class="n">ll</span> <span class="n">y</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span> 718 <span class="n">vector</span><span class="o"><</span><span class="n">pair</span><span class="o"><</span><span class="n">ll</span><span class="p">,</span> <span class="kt">int</span><span class="o">></span> <span class="o">></span> <span class="n">ret</span><span class="p">;</span> 719 <span class="k">for</span> <span class="p">(</span><span class="n">ll</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span> <span class="n">i</span><span class="o">*</span><span class="n">i</span> <span class="o"><=</span> <span class="n">x</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
720 <span class="k">if</span> <span class="p">(</span><span class="n">y</span><span class="o">%</span><span class="n">i</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="p">{</span> 721 <span class="kt">int</span> <span class="n">cnt</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> 722 <span class="k">while</span> <span class="p">(</span><span class="n">y</span><span class="o">%</span><span class="n">i</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="n">y</span> <span class="o">/=</span> <span class="n">i</span><span class="p">,</span> <span class="n">cnt</span><span class="o">++</span><span class="p">;</span> 723 <span class="n">ret</span><span class="p">.</span><span class="n">push_back</span><span class="p">({</span> <span class="n">i</span><span class="p">,</span><span class="n">cnt</span> <span class="p">});</span> 724 <span class="p">}</span> 725 <span class="p">}</span> 726 <span class="k">if</span> <span class="p">(</span><span class="n">y</span> <span class="o">!=</span> <span class="mi">1</span><span class="p">)</span> <span class="n">ret</span><span class="p">.</span><span class="n">push_back</span><span class="p">({</span> <span class="n">y</span><span class="p">,</span><span class="mi">1</span> <span class="p">});</span> 727 <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> 728<span class="p">}</span> 729</code></pre></div></div> 730 731<h3 id="gcd-ìµëê³µì½ì">GCD ìµëê³µì½ì</h3> 732 733<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="kt">int</span> <span class="nf">gcd</span><span class="p">(</span><span class="kt">int</span> <span class="n">a</span><span class="p">,</span> <span class="kt">int</span> <span class="n">b</span><span class="p">){</span> <span class="k">return</span> <span class="n">b</span><span class="o">?</span><span class="n">gcd</span><span class="p">(</span><span class="n">b</span><span class="p">,</span><span class="n">a</span><span class="o">%</span><span class="n">b</span><span class="p">)</span><span class="o">:</span><span class="n">a</span><span class="p">;</span> <span class="p">}</span> 734</code></pre></div></div> 735 736<h3 id="lcm-ìµì공배ì">LCM ìµì공배ì</h3> 737 738<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="kt">int</span> <span class="nf">gcd</span><span class="p">(</span><span class="kt">int</span> <span class="n">a</span><span class="p">,</span> <span class="kt">int</span> <span class="n">b</span><span class="p">){</span> <span class="k">return</span> <span class="n">b</span><span class="o">?</span><span class="n">gcd</span><span class="p">(</span><span class="n">b</span><span class="p">,</span><span class="n">a</span><span class="o">%</span><span class="n">b</span><span class="p">)</span><span class="o">:</span><span class="n">a</span><span class="p">;</span> <span class="p">}</span> 739<span class="kt">int</span> <span class="n">lcm</span><span class="p">(</span><span class="kt">int</span> <span class="n">a</span><span class="p">,</span> <span class="kt">int</span> <span class="n">b</span><span class="p">)</span> <span class="p">{</span><span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">a</span><span class="o">||!</span><span class="n">b</span><span class="p">)</span><span class="k">return</span> <span class="n">a</span><span class="o">+</span><span class="n">b</span><span class="p">;</span><span class="k">return</span> <span class="n">a</span><span class="o">*</span><span class="p">(</span><span class="n">b</span><span class="o">/</span><span class="n">gcd</span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="n">b</span><span class="p">));}</span> 740</code></pre></div></div> 741 742<h3 id="extended-gcd-íì¥-ì í´ë¦¬ë">Extended GCD íì¥ ì í´ë¦¬ë</h3> 743 744<p><code class="language-plaintext highlighter-rouge">ax+by = gcd(a, b)</code>ê° ëë ì ìì <code class="language-plaintext highlighter-rouge">(x, y)</code>를 ì°¾ëë¤.</p> 745 746<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">pair</span><span class="o"><</span><span class="kt">int</span><span class="p">,</span><span class="kt">int</span><span class="o">></span> <span class="n">ext_gcd</span><span class="p">(</span><span class="kt">int</span> <span class="n">a</span><span class="p">,</span> <span class="kt">int</span> <span class="n">b</span><span class="p">){</span> 747 <span class="k">if</span> <span class="p">(</span><span class="n">b</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="k">return</span> <span class="p">{</span> <span class="mi">1</span><span class="p">,</span><span class="mi">0</span> <span class="p">};</span> 748 <span class="k">auto</span> <span class="n">t</span> <span class="o">=</span> <span class="n">ext_gcd</span><span class="p">(</span><span class="n">b</span><span class="p">,</span> <span class="n">a</span><span class="o">%</span><span class="n">b</span><span class="p">);</span> 749 <span class="k">return</span> <span class="p">{</span> <span class="n">t</span><span class="p">.</span><span class="n">second</span><span class="p">,</span><span class="n">t</span><span class="p">.</span><span class="n">first</span><span class="o">-</span><span class="p">(</span><span class="n">a</span><span class="o">/</span><span class="n">b</span><span class="p">)</span><span class="o">*</span><span class="n">t</span><span class="p">.</span><span class="n">second</span> <span class="p">};</span> 750<span class="p">}</span> 751</code></pre></div></div> 752 753<h3 id="modular-inverse-모ëë¬-ì¸ë²ì¤">Modular Inverse 모ëë¬ ì¸ë²ì¤</h3> 754 755<p><code class="language-plaintext highlighter-rouge">ax mod M = 1</code>ì¸ <code class="language-plaintext highlighter-rouge">x</code>를 ì°¾ëë¤.</p> 756 757<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="kt">int</span> <span class="nf">mod_inv</span><span class="p">(</span><span class="kt">int</span> <span class="n">a</span><span class="p">,</span> <span class="kt">int</span> <span class="n">M</span><span class="p">){</span> 758 <span class="k">return</span> <span class="p">(</span><span class="n">ext_gcd</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">M</span><span class="p">).</span><span class="n">first</span> <span class="o">+</span> <span class="n">M</span><span class="p">)</span> <span class="o">%</span> <span class="n">M</span><span class="p">;</span> 759<span class="p">}</span> 760</code></pre></div></div> 761 762<h3 id="kitamasa-í¤íë§ì¬">Kitamasa í¤íë§ì¬</h3> 763 764<p>ì íì íììì, <code class="language-plaintext highlighter-rouge">O(K^3logN)</code>ì íë ¬ê³±ì <code class="language-plaintext highlighter-rouge">O(K^2logN)</code>ì¼ë¡ ë¨êµ°ë¤.</p> 765 766<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">lint</span><span class="p">;</span> 767<span class="k">const</span> <span class="kt">int</span> <span class="n">mod</span> <span class="o">=</span> <span class="mi">1000000007</span><span class="p">;</span> 768<span class="kt">int</span> <span class="n">k</span><span class="p">,</span> <span class="n">a</span><span class="p">[</span><span class="mi">1004</span><span class="p">],</span> <span class="n">w</span><span class="p">[</span><span class="mi">1004</span><span class="p">];
768</span> 769 770<span class="kt">int</span> <span class="nf">add</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="kt">int</span> <span class="n">y</span><span class="p">)</span> <span class="p">{</span> <span class="k">return</span> <span class="p">(</span><span class="n">x</span><span class="o">+</span><span class="n">y</span><span class="p">)</span> <span class="o">%</span> <span class="n">mod</span><span class="p">;</span> <span class="p">}</span> 771<span class="kt">int</span> <span class="n">mul</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="kt">int</span> <span class="n">y</span><span class="p">)</span> <span class="p">{</span> <span class="k">return</span> <span class="p">(</span><span class="n">x</span><span class="o">*</span><span class="p">(</span><span class="n">lint</span><span class="p">)</span><span class="n">y</span><span class="p">)</span> <span class="o">%</span> <span class="n">mod</span><span class="p">;</span> <span class="p">}</span> 772 773<span class="kt">int</span> <span class="n">kitamasa</span><span class="p">(</span><span class="n">lint</span> <span class="n">n</span><span class="p">)</span> <span class="p">{</span> 774 <span class="n">vector</span><span class="o"><</span><span class="kt">int</span><span class="o">></span> <span class="n">c</span><span class="p">(</span><span class="n">k</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span> <span class="n">c</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> 775 776 <span class="c1">// n = 1 ë§ë¤ê¸°</span> 777 <span class="kt">int</span> <span class="n">b</span> <span class="o">=</span> <span class="mi">62</span><span class="p">;</span> 778 <span class="k">while</span> <span class="p">((</span><span class="n">n</span><span class="o">>></span><span class="n">b</span><span class="p">)</span><span class="o">%</span><span class="mi">2</span><span class="o">==</span><span class="mi">0</span><span class="p">)</span> <span class="n">b</span><span class="o">--</span><span class="p">;</span> 779 780 <span class="k">for</span> <span class="p">(</span><span class="n">b</span><span class="o">--</span><span class="p">;</span> <span class="o">~</span><span class="n">b</span><span class="p">;</span> <span class="n">b</span><span class="o">--</span><span class="p">)</span> <span class="p">{</span> 781 <span class="c1">// c(n) -> c(2n)</span> 782 <span class="n">vector</span><span class="o"><</span><span class="kt">int</span><span class="o">></span> <span class="n">d</span><span class="p">(</span><span class="mi">2</span><span class="o">*</span><span class="n">k</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span> 783 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o"><=</span><span class="n">k</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o"><=</span><span class="n">k</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">add</span><span class="p">(</span><span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="n">j</span><span class="p">],</span> <span class="n">mul</span><span class="p">(</span><span class="n">c</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">c</span><span class="p">[</span><span class="n">j</span><span class="p">]));
783</span> 784 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">2</span><span class="o">*</span><span class="n">k</span><span class="p">;</span> <span class="n">i</span><span class="o">></span><span class="n">k</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">)</span> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o"><=</span><span class="n">k</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">add</span><span class="p">(</span><span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="n">j</span><span class="p">],</span> <span class="n">mul</span><span class="p">(</span><span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">w</span><span class="p">[</span><span class="n">j</span><span class="p">]));</span> 785 <span class="n">d</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="n">k</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span> 786 <span class="n">c</span> <span class="o">=</span> <span class="n">d</span><span class="p">;</span> 787 <span class="c1">// c(n) -> c(n+1)</span> 788 <span class="k">if</span> <span class="p">((</span><span class="n">n</span><span class="o">>></span><span class="n">b</span><span class="p">)</span><span class="o">&</span><span class="mi">1</span><span class="p">)</span> <span class="p">{</span> 789 <span class="n">vector</span><span class="o"><</span><span class="kt">int</span><span class="o">></span> <span class="n">d</span><span class="p">(</span><span class="n">k</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span> 790 <span class="n">d</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="n">mul</span><span class="p">(</span><span class="n">c</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">w</span><span class="p">[</span><span class="n">k</span><span class="p">]);</span> 791 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">2</span><span class="p">;</span> <span class="n">i</span><span class="o"><=</span><span class="n">k</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">c</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">mul</span><span class="p">(</span><span class="n">c</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">w</span><span class="p">[</span><span class="n">k</span><span class="o">+</span><span class="mi">1</span><span class="o">-</span><span class="n">i</span><span class="p">]);</span> 792 <span class="n">c</span> <span class="o">=</span> <span class="n">d</span><span class="p">;</span> 793 <span class="p">}</span> 794 <span class="p">}</span> 795 796 <span class="kt">int</span> <span class="n">ans</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> 797 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o"><=</span><span class="n">k</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">ans</span> <span class="o">=</span> <span class="n">add</span><span class="p">(</span><span class="n">ans</span><span class="p">,</span> <span class="n">mul</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">c</span><span class="p">[</span><span class="n">i</span><span class="p">]));
797</span> 798 <span class="k">return</span> <span class="n">ans</span><span class="p">;</span> 799<span class="p">}</span> 800 801<span class="kt">int</span> <span class="n">main</span><span class="p">()</span> <span class="p">{</span> 802 <span class="n">lint</span> <span class="n">n</span><span class="p">;</span> 803 <span class="n">cin</span> <span class="o">>></span> <span class="n">n</span> <span class="o">>></span> <span class="n">k</span><span class="p">;</span> 804 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o"><=</span><span class="n">k</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cin</span> <span class="o">>></span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="c1">// 첫 kê°ì í</span> 805 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o"><=</span><span class="n">k</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cin</span> <span class="o">>></span> <span class="n">w</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="c1">// ì íìì ê³ì</span> 806 807 <span class="n">cout</span> <span class="o"><<</span> <span class="n">kitamasa</span><span class="p">(</span><span class="n">n</span><span class="p">);</span> 808<span class="p">}</span> 809</code></pre></div></div> 810 811<h3 id="fft-ë¹ ë¥¸-í¸ë¦¬ì-ë³í">FFT ë¹ ë¥¸ í¸ë¦¬ì ë³í</h3> 812 813<p><code class="language-plaintext highlighter-rouge">O(NlogN)</code>, <code class="language-plaintext highlighter-rouge">res[i] = for(j=0~i) a[j]*b[i-j]</code>,</p> 814 815<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#define _USE_MATH_DEFINES 816#include</span> <span class="cpf"><cstdio></span><span class="cp"> 817#include</span> <span class="cpf"><cmath></span><span class="cp"> 818#include</span> <span class="cpf"><complex></span><span class="cp"> 819#include</span> <span class="cpf"><vector></span><span class="cp"> 820#include</span> <span class="cpf"><algorithm></span><span class="cp"> 821</span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> 822<span class="k">typedef</span> <span class="n">complex</span><span class="o"><</span><span class="kt">double</span><span class="o">></span> <span class="n">base</span><span class="p">;</span> 823<span class="kt">void</span> <span class="nf">fft</span><span class="p">(</span><span class="n">vector</span><span class="o"><</span><span class="n">base</span><span class="o">></span> <span class="o">&</span><span class="n">a</span><span class="p">,</span> <span class="kt">bool</span> <span class="n">invert</span><span class="p">)</span> <span class="p">{</span> 824 <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="n">a</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> 825 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span><span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o"><</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span> 826 <span class="kt">int</span> <span class="n">bit</span> <span class="o">=</span> <span class="n">n</span> <span class="o">>></span> <span class="mi">1</span><span class="p">;</span> 827 <span class="k">for</span> <span class="p">(;</span><span class="n">j</span><span class="o">>=</span><span class="n">bit</span><span class="p">;</span><span class="n">bit</span><span class="o">>>=</span><span class="mi">1</span><span class="p">)</span> <span class="n">j</span> <span class="o">-=</span> <span class="n">bit</span><span class="p">;</span>
828 <span class="n">j</span> <span class="o">+=</span> <span class="n">bit</span><span class="p">;</span> 829 <span class="k">if</span> <span class="p">(</span><span class="n">i</span> <span class="o"><</span> <span class="n">j</span><span class="p">)</span> <span class="n">swap</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="p">]);</span> 830 <span class="p">}</span> 831 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">len</span><span class="o">=</span><span class="mi">2</span><span class="p">;</span><span class="n">len</span><span class="o"><=</span><span class="n">n</span><span class="p">;</span><span class="n">len</span><span class="o"><<=</span><span class="mi">1</span><span class="p">){</span> 832 <span class="kt">double</span> <span class="n">ang</span> <span class="o">=</span> <span class="mi">2</span><span class="o">*</span><span class="n">M_PI</span><span class="o">/</span><span class="n">len</span><span class="o">*</span><span class="p">(</span><span class="n">invert</span><span class="o">?-</span><span class="mi">1</span><span class="o">:</span><span class="mi">1</span><span class="p">);</span> 833 <span class="n">base</span> <span class="n">wlen</span><span class="p">(</span><span class="n">cos</span><span class="p">(</span><span class="n">ang</span><span class="p">),</span><span class="n">sin</span><span class="p">(</span><span class="n">ang</span><span class="p">));</span> 834 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o"><</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">+=</span><span class="n">len</span><span class="p">){</span> 835 <span class="n">base</span> <span class="n">w</span><span class="p">(</span><span class="mi">1</span><span class="p">);</span> 836 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">j</span><span class="o"><</span><span class="n">len</span><span class="o">/</span><span class="mi">2</span><span class="p">;</span><span class="n">j</span><span class="o">++</span><span class="p">){</span> 837 <span class="n">base</span> <span class="n">u</span> <span class="o">=</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="n">j</span><span class="p">],</span> <span class="n">v</span> <span class="o">=</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="n">j</span><span class="o">+</span><span class="n">len</span><span class="o">/</span><span class="mi">2</span><span class="p">]</span><span class="o">*</span><span class="n">w</span><span class="p">;</span> 838 <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">u</span><span class="o">+</span><span class="n">v</span><span class="p">;</span> 839 <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="n">j</span><span class="o">+</span><span class="n">len</span><span class="o">/</span><span class="mi">2</span><span class="p">]</span> <span class="o">=</span> <span class="n">u</span><span class="o">-</span><span class="n">v</span><span class="p">;</span> 840 <span class="n">w</span> <span class="o">*=</span> <span class="n">wlen</span><span class="p">;</span> 841 <span class="p">}</span> 842 <span class="p">}</span> 843 <span class="p">}</span> 844 <span class="k">if</span> <span class="p">(</span><span class="n">invert</span><span class="p">)</span> <span class="p">{</span>
845 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o"><</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">/=</span> <span class="n">n</span><span class="p">;</span> 846 <span class="p">}</span> 847<span class="p">}</span> 848<span class="n">vector</span><span class="o"><</span><span class="kt">int</span><span class="o">></span> <span class="n">multiply</span><span class="p">(</span><span class="k">const</span> <span class="n">vector</span><span class="o"><</span><span class="kt">int</span><span class="o">></span> <span class="o">&</span><span class="n">a</span><span class="p">,</span><span class="k">const</span> <span class="n">vector</span><span class="o"><</span><span class="kt">int</span><span class="o">></span> <span class="o">&</span><span class="n">b</span><span class="p">)</span> <span class="p">{</span> 849 <span class="n">vector</span> <span class="o"><</span><span class="n">base</span><span class="o">></span> <span class="n">fa</span><span class="p">(</span><span class="n">a</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span> <span class="n">a</span><span class="p">.</span><span class="n">end</span><span class="p">()),</span> <span class="n">fb</span><span class="p">(</span><span class="n">b</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span> <span class="n">b</span><span class="p">.</span><span class="n">end</span><span class="p">());</span> 850 <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> 851 <span class="k">while</span> <span class="p">(</span><span class="n">n</span> <span class="o"><</span> <span class="n">max</span><span class="p">(</span><span class="n">a</span><span class="p">.</span><span class="n">size</span><span class="p">(),</span><span class="n">b</span><span class="p">.</span><span class="n">size</span><span class="p">()))</span> <span class="n">n</span> <span class="o"><<=</span> <span class="mi">1</span><span class="p">;</span> 852 <span class="n">fa</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="n">n</span><span class="p">);</span> <span class="n">fb</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="n">n</span><span class="p">);</span> 853 <span class="n">fft</span><span class="p">(</span><span class="n">fa</span><span class="p">,</span><span class="nb">false</span><span class="p">);</span> <span class="n">fft</span><span class="p">(</span><span class="n">fb</span><span class="p">,</span><span class="nb">false</span><span class="p">);</span> 854 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o"><</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">fa</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">*=</span> <span class="n">fb</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> 855 <span class="n">fft</span><span class="p">(</span><span class="n">fa</span><span class="p">,</span><span class="nb">true</span><span class="p">);</span> 856 <span class="n">vector</span><span class="o"><</span><span class="kt">int</span><span class="o">></span> <span class="n">res</span><span class="p">;</span> 857 <span class="n">res</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="n">n</span><span class="p">);</span> 858 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o"><</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">res</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="kt">int</span><span class="p">(</span><span class="n">fa</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">real</span><span class="p">()</span><span class="o">+</span><span class="p">(</span><span class="n">fa</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">real</span><span class="p">()</span><span class="o">></span><span class="mi">0</span><span class="o">?</span><span class="mf">0.5</span><span class="o">:-</span><span class="mf">0.5</span><span class="p">));</span> 859 <span class="k">return</span> <span class="n">res</span><span class="p">;</span> 860<span class="p">}</span> 861<span class="kt">int</span> <span class="n">main</span><span class="p">()</span> <span class="p">{</span> 862 <span class="kt">int</span> <span class="n">n</span><span class="p">;</span>
862 <span class="c1">// Rotating Multiply Example</span> 863 <span class="n">vector</span><span class="o"><</span><span class="kt">int</span><span class="o">></span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">res</span><span class="p">;</span> 864 <span class="n">scanf</span><span class="p">(</span><span class="s">"%d"</span><span class="p">,</span> <span class="o">&</span><span class="n">n</span><span class="p">);</span> 865 <span class="n">a</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="n">n</span><span class="o">*</span><span class="mi">2</span><span class="p">);</span> <span class="n">b</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="n">n</span><span class="p">);</span> 866 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o"><</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> 867 <span class="n">scanf</span><span class="p">(</span><span class="s">"%d"</span><span class="p">,</span> <span class="o">&</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> 868 <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> 869 <span class="p">}</span> 870 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o"><</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> 871 <span class="n">scanf</span><span class="p">(</span><span class="s">"%d"</span><span class="p">,</span> <span class="o">&</span><span class="n">b</span><span class="p">[</span><span class="n">n</span><span class="o">-</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">]);</span> 872 <span class="p">}</span> 873 <span class="n">multiply</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">res</span><span class="p">);</span> 874 <span class="kt">int</span> <span class="n">ans</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> 875 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o"><</span><span class="n">n</span><span class="o">*</span><span class="mi">2</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> 876 <span class="n">ans</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">ans</span><span class="p">,</span> <span class="n">res</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> 877 <span class="p">}</span> 878 <span class="n">printf</span><span class="p">(</span><span class="s">"%d"</span><span class="p">,</span> <span class="n">ans</span><span class="p">);</span> 879 <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> 880<span class="p">}</span> 881</code></pre></div></div> 882 883<h2 id="string-문ìì´">String 문ìì´</h2> 884 885<h3 id="kmp-í¬ëì¤-모리ì¤-íë«">KMP í¬ëì¤ ëª¨ë¦¬ì¤ íë«</h3> 886 887<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include</span> <span class="cpf"><vector></span><span class="cp"> 888#include</span> <span class="cpf"><string></span><span class="cp"> 889</span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> 890 891<span class="n">vector</span><span class="o"><</span><span class="kt">int</span><span class="o">></span> <span class="n">search</span><span class="p">(</span><span class="n">string</span> <span class="n">str</span><span class="p">,</span> <span class="n">string</span> <span class="n">pattern</span><span class="p">)</span> <span class="p">{</span> 892 <span class="n">vector</span><span class="o"><</span><span class="kt">int</span><span class="o">></span> <span class="n">f</span><span class="p">;</span> 893 <span class="n">f</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="mi">0</span><span class="p">);</span> 894 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">,</span> <span class="n">k</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">pattern</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
895 <span class="k">while</span> <span class="p">(</span><span class="n">k</span> <span class="o">!=</span> <span class="mi">0</span> <span class="o">&&</span> <span class="n">pattern</span><span class="p">[</span><span class="n">k</span><span class="p">]</span> <span class="o">!=</span> <span class="n">pattern</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="p">{</span> 896 <span class="n">k</span> <span class="o">=</span> <span class="n">f</span><span class="p">[</span><span class="n">k</span> <span class="o">-</span> <span class="mi">1</span><span class="p">];</span> 897 <span class="p">}</span> 898 <span class="k">if</span> <span class="p">(</span><span class="n">pattern</span><span class="p">[</span><span class="n">k</span><span class="p">]</span> <span class="o">==</span> <span class="n">pattern</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="p">{</span> 899 <span class="n">f</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="o">++</span><span class="n">k</span><span class="p">);</span> 900 <span class="p">}</span> 901 <span class="k">else</span> <span class="p">{</span> 902 <span class="n">f</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="mi">0</span><span class="p">);</span> 903 <span class="p">}</span> 904 <span class="p">}</span> 905 <span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> 906 <span class="n">vector</span><span class="o"><</span><span class="kt">int</span><span class="o">></span> <span class="n">matches</span><span class="p">;</span> 907 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">str</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> 908 <span class="k">while</span> <span class="p">(</span><span class="n">j</span> <span class="o">!=</span> <span class="mi">0</span> <span class="o">&&</span> <span class="n">pattern</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">!=</span> <span class="n">str</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="p">{</span> 909 <span class="n">j</span> <span class="o">=</span> <span class="n">f</span><span class="p">[</span><span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="p">];</span> 910 <span class="p">}</span> 911 <span class="k">if</span> <span class="p">(</span><span class="n">pattern</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="n">str</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="p">{</span> 912 <span class="k">if</span> <span class="p">(</span><span class="n">j</span> <span class="o">+</span> <span class="mi">1</span> <span class="o">==</span> <span class="n">pattern</span><span class="p">.</span><span class="n">size</span><span class="p">())</span> <span class="p">{</span> 913 <span class="n">matches</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">i</span> <span class="o">-</span> <span class="p">(</span><span class="kt">int</span><span class="p">)</span> <span class="n">pattern</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">+</span> <span class="mi">2</span><span class="p">);</span> 914 <span class="n">j</span> <span class="o">=</span> <span class="n">f</span><span class="p">[</span><span class="n">j</span><span class="p">];
914</span> 915 <span class="p">}</span> 916 <span class="k">else</span> <span class="p">{</span> 917 <span class="n">j</span><span class="o">++</span><span class="p">;</span> 918 <span class="p">}</span> 919 <span class="p">}</span> 920 <span class="p">}</span> 921 <span class="k">return</span> <span class="n">matches</span><span class="p">;</span> 922<span class="p">}</span> 923</code></pre></div></div> 924 925<h3 id="suffix-array-ìí½ì¤-ì´ë ì´-ì 미ì¬-ë°°ì´">Suffix Array ìí½ì¤ ì´ë ì´ ì ë¯¸ì¬ ë°°ì´</h3> 926 927<ul> 928 <li><code class="language-plaintext highlighter-rouge">sa[n] = beginning index of N-th suffix (ordered, 1-indexed)</code>, <code class="language-plaintext highlighter-rouge">O(NlogN)</code></li> 929 <li><code class="language-plaintext highlighter-rouge">lcp[n] = length of common prefix between sa[n-1] and sa[n]</code>, <code class="language-plaintext highlighter-rouge">O(N)</code></li> 930</ul> 931 932<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include</span> <span class="cpf"><iostream></span><span class="cp"> 933#include</span> <span class="cpf"><string></span><span class="cp"> 934#include</span> <span class="cpf"><vector></span><span class="cp"> 935#include</span> <span class="cpf"><algorithm></span><span class="cp"> 936</span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> 937<span class="k">typedef</span> <span class="n">vector</span><span class="o"><</span><span class="kt">int</span><span class="o">></span> <span class="n">vi</span><span class="p">;</span> 938<span class="n">vi</span> <span class="nf">SuffixArray</span><span class="p">(</span><span class="n">string</span> <span class="o">&</span><span class="n">S</span><span class="p">)</span> <span class="p">{</span> 939 <span class="kt">int</span> <span class="n">i</span><span class="p">,</span><span class="n">j</span><span class="p">,</span><span class="n">k</span><span class="p">;</span> 940 <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="mi">26</span><span class="p">;</span> <span class="c1">// ì²ì ìíë²³ ê°ì</span> 941 <span class="kt">int</span> <span class="n">N</span> <span class="o">=</span> <span class="n">S</span><span class="p">.</span><span class="n">length</span><span class="p">();</span> 942 <span class="n">vi</span> <span class="n">SA</span><span class="p">(</span><span class="n">N</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),</span> <span class="n">cnt</span><span class="p">(</span><span class="n">max</span><span class="p">(</span><span class="n">N</span><span class="p">,</span><span class="n">m</span><span class="p">)</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),</span> <span class="n">x</span><span class="p">(</span><span class="n">N</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),</span> <span class="n">y</span><span class="p">(</span><span class="n">N</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">);</span> 943 <span class="k">for</span> <span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o"><=</span><span class="n">N</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cnt</span><span class="p">[</span><span class="n">x</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">S</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-</span><span class="sc">'a'</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span><span class="o">++</span><span class="p">;</span> 944 <span class="k">for</span> <span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o"><=</span><span class="n">m</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cnt</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+=</span> <span class="n">cnt</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">];
944</span> 945 <span class="k">for</span> <span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="n">N</span><span class="p">;</span><span class="n">i</span><span class="p">;</span><span class="n">i</span><span class="o">--</span><span class="p">)</span> <span class="n">SA</span><span class="p">[</span><span class="n">cnt</span><span class="p">[</span><span class="n">x</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span><span class="o">--</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span> 946 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">len</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span><span class="n">p</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">p</span><span class="o"><</span><span class="n">N</span><span class="p">;</span><span class="n">len</span><span class="o"><<=</span><span class="mi">1</span><span class="p">,</span><span class="n">m</span><span class="o">=</span><span class="n">p</span><span class="p">){</span> 947 <span class="k">for</span> <span class="p">(</span><span class="n">p</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">i</span><span class="o">=</span><span class="n">N</span><span class="o">-</span><span class="n">len</span><span class="p">;</span><span class="o">++</span><span class="n">i</span><span class="o"><=</span><span class="n">N</span><span class="p">;)</span> <span class="n">y</span><span class="p">[</span><span class="o">++</span><span class="n">p</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span> 948 <span class="k">for</span> <span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o"><=</span><span class="n">N</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span> <span class="p">(</span><span class="n">SA</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">></span> <span class="n">len</span><span class="p">)</span> <span class="n">y</span><span class="p">[</span><span class="o">++</span><span class="n">p</span><span class="p">]</span> <span class="o">=</span> <span class="n">SA</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-</span><span class="n">len</span><span class="p">;</span> 949 <span class="k">for</span> <span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o"><=</span><span class="n">m</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cnt</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> 950 <span class="k">for</span> <span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o"><=</span><span class="n">N</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cnt</span><span class="p">[</span><span class="n">x</span><span class="p">[</span><span class="n">y</span><span class="p">[</span><span class="n">i</span><span class="p">]]]</span><span class="o">++</span><span class="p">;</span> 951 <span class="k">for</span> <span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o"><=</span><span class="n">m</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cnt</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+=</span> <span class="n">cnt</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">];
951</span> 952 <span class="k">for</span> <span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="n">N</span><span class="p">;</span><span class="n">i</span><span class="p">;</span><span class="n">i</span><span class="o">--</span><span class="p">)</span> <span class="n">SA</span><span class="p">[</span><span class="n">cnt</span><span class="p">[</span><span class="n">x</span><span class="p">[</span><span class="n">y</span><span class="p">[</span><span class="n">i</span><span class="p">]]]</span><span class="o">--</span><span class="p">]</span> <span class="o">=</span> <span class="n">y</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> 953 <span class="n">swap</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="n">y</span><span class="p">);</span> <span class="n">p</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">x</span><span class="p">[</span><span class="n">SA</span><span class="p">[</span><span class="mi">1</span><span class="p">]]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> 954 <span class="k">for</span> <span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o"><</span><span class="n">N</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> 955 <span class="n">x</span><span class="p">[</span><span class="n">SA</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">]]</span> <span class="o">=</span> <span class="n">SA</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">+</span><span class="n">len</span> <span class="o"><=</span> <span class="n">N</span> <span class="o">&&</span> <span class="n">SA</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span><span class="o">+</span><span class="n">len</span> <span class="o"><=</span> <span class="n">N</span> <span class="o">&&</span> <span class="n">y</span><span class="p">[</span><span class="n">SA</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span> <span class="o">==</span> <span class="n">y</span><span class="p">[</span><span class="n">SA</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">]]</span> <span class="o">&&</span> <span class="n">y</span><span class="p">[</span><span class="n">SA</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">+</span><span class="n">len</span><span class="p">]</span> <span class="o">==</span> <span class="n">y</span><span class="p">[</span><span class="n">SA</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span><span class="o">+</span><span class="n">len</span><span class="p">]</span> <span class="o">?</span> <span class="n">p</span> <span class="o">:</span> <span class="o">++</span><span class="n">p</span><span class="p">;</span> 956 <span class="p">}</span> 957 <span class="k">return</span> <span class="n">SA</span><span class="p">;</span> 958<span class="p">}</span> 959<span class="n">vi</span> <span class="n">GetLcp</span><span class="p">(</span><span class="n">string</span> <span class="o">&</span><span class="n">S</span><span class="p">,</span> <span class="n">vi</span> <span class="o">&</span><span class="n">SA</span><span class="p">)</span> <span class="p">{</span> 960 <span class="kt">int</span> <span class="n">i</span><span class="p">,</span><span class="n">j</span><span class="p">,</span><span class="n">k</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> 961 <span class="kt">int</span> <span class="n">N</span> <span class="o">=</span> <span class="n">SA</span><span class="p">.</span><span class="n">size</span><span class="p">()</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span> 962 <span class="n">vi</span> <span class="n">rank</span><span class="p">(</span><span class="n">N</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),</span> <span class="n">lcp</span><span class="p">(</span><span class="n">N</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span> 963 <span class="k">for</span> <span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o"><=</span><span class="n">N</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">rank</span><span class="p">[</span><span class="n">SA</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span> 964 <span class="k">for</span> <span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o"><=</span><span class="n">N</span><span class="p">;</span><span class="n">lcp</span><span class="p">[</span><span class="n">rank</span><span class="p">[</span><span class="n">i</span><span class="o">++</span><span class="p">]]</span><span class="o">=</span><span class="n">k</span><span class="p">)</span>
965 <span class="k">for</span> <span class="p">(</span><span class="n">k</span><span class="o">?</span><span class="n">k</span><span class="o">--:</span><span class="mi">0</span><span class="p">,</span><span class="n">j</span><span class="o">=</span><span class="n">SA</span><span class="p">[</span><span class="n">rank</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-</span><span class="mi">1</span><span class="p">];</span><span class="n">S</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="n">k</span><span class="p">]</span><span class="o">==</span><span class="n">S</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="n">k</span><span class="p">];</span><span class="n">k</span><span class="o">++</span><span class="p">);</span> 966 <span class="k">return</span> <span class="n">lcp</span><span class="p">;</span> 967<span class="p">}</span> 968<span class="kt">int</span> <span class="n">main</span><span class="p">()</span> <span class="p">{</span> 969 <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">NULL</span><span class="p">);</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> 970 <span class="kt">int</span> <span class="n">n</span><span class="p">;</span> 971 <span class="n">string</span> <span class="n">str</span><span class="p">;</span> 972 <span class="n">cin</span> <span class="o">>></span> <span class="n">n</span> <span class="o">>></span> <span class="n">str</span><span class="p">;</span> 973 <span class="n">str</span> <span class="o">=</span> <span class="sc">'$'</span> <span class="o">+</span> <span class="n">str</span><span class="p">;</span> 974 <span class="n">vi</span> <span class="n">sa</span> <span class="o">=</span> <span class="n">SuffixArray</span><span class="p">(</span><span class="n">str</span><span class="p">);</span> 975 <span class="n">vi</span> <span class="n">lcp</span> <span class="o">=</span> <span class="n">GetLcp</span><span class="p">(</span><span class="n">str</span><span class="p">,</span> <span class="n">sa</span><span class="p">);</span> 976 <span class="n">cout</span> <span class="o"><<</span> <span class="o">*</span><span class="n">max_element</span><span class="p">(</span><span class="n">lcp</span><span class="p">.</span><span class="n">begin</span><span class="p">()</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">lcp</span><span class="p">.</span><span class="n">end</span><span class="p">());</span> 977 <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> 978<span class="p">}</span> 979</code></pre></div></div> 980 981<h3 id="manacher-매ë´ì³">Manacher 매ë´ì³</h3> 982 983<p><code class="language-plaintext highlighter-rouge">p[i] = i-k, ..., i, ..., i+kê¹ì§ í°ë¦°ëë¡¬ì¸ ê°ì¥ í° k</code><br /> 984<code class="language-plaintext highlighter-rouge">O(N)</code></p> 985 986<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="c1">// ëµì´ long long ë²ì를 ë²ì´ëì§ ìëì§ ì ìí ê²,</span> 987<span class="c1">// manacher를 ì¬ì©íë ê²½ì°, ëì²´ë¡ ì íì´ í¬ê¸° ë문ì int ë²ì를 ë²ì´ëë ê²½ì°ê° ë§ì</span> 988<span class="cp">#include</span> <span class="cpf"><cstring></span><span class="cp"> 989#include</span> <span class="cpf"><algorithm></span><span class="cp"> 990</span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> 991 992<span class="k">const</span> <span class="kt">int</span> <span class="n">MAXN</span> <span class="o">=</span> <span class="mi">2000000</span> <span class="o">+</span> <span class="mi">2</span><span class="p">;</span> 993<span class="kt">int</span> <span class="n">p</span><span class="p">[</span><span class="n">MAXN</span> <span class="o">*</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">1</span><span class="p">];
993</span> 994<span class="kt">char</span> <span class="n">t</span><span class="p">[</span><span class="n">MAXN</span> <span class="o">+</span> <span class="mi">1</span><span class="p">],</span> <span class="n">s</span><span class="p">[</span><span class="n">MAXN</span> <span class="o">*</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">1</span><span class="p">];</span> 995 996<span class="kt">void</span> <span class="nf">manacher</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="p">)</span> <span class="p">{</span> 997 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> 998 <span class="n">s</span><span class="p">[</span><span class="n">i</span> <span class="o">*</span> <span class="mi">2</span><span class="p">]</span> <span class="o">=</span> <span class="n">t</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> 999 <span class="k">if</span> <span class="p">(</span><span class="n">i</span> <span class="o">!=</span> <span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="n">s</span><span class="p">[</span><span class="n">i</span> <span class="o">*</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="sc">'$'</span><span class="p">;</span> 1000 <span class="p">}</span> 1001 <span class="n">n</span> <span class="o">=</span> <span class="n">n</span> <span class="o">*</span> <span class="mi">2</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span> 1002 <span class="kt">int</span> <span class="n">r</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="n">k</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span> 1003 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> 1004 <span class="k">if</span> <span class="p">(</span><span class="n">i</span> <span class="o"><=</span> <span class="n">r</span><span class="p">)</span> <span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">r</span> <span class="o">-</span> <span class="n">i</span><span class="p">,</span> <span class="n">p</span><span class="p">[</span><span class="mi">2</span> <span class="o">*</span> <span class="n">k</span> <span class="o">-</span> <span class="n">i</span><span class="p">]);</span> 1005 <span class="k">while</span> <span class="p">(</span><span class="n">i</span> <span class="o">-</span> <span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">-</span> <span class="mi">1</span> <span class="o">>=</span> <span class="mi">0</span> <span class="o">&&</span> <span class="n">i</span> <span class="o">+</span> <span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span> <span class="o"><</span> <span class="n">n</span> <span class="o">&&</span> <span class="n">s</span><span class="p">[</span><span class="n">i</span> <span class="o">-</span> <span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]</span> <span class="o">==</span> <span class="n">s</span><span class="p">[</span><span class="n">i</span> <span class="o">+</span> <span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span><span class="p">])</span>
1006 <span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">++</span><span class="p">;</span> 1007 <span class="k">if</span> <span class="p">(</span><span class="n">r</span> <span class="o"><</span> <span class="n">i</span> <span class="o">+</span> <span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">r</span> <span class="o">=</span> <span class="n">i</span> <span class="o">+</span> <span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">k</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span> 1008 <span class="p">}</span> 1009<span class="p">}</span> 1010 1011<span class="kt">int</span> <span class="n">main</span><span class="p">()</span> <span class="p">{</span> 1012 <span class="n">scanf</span><span class="p">(</span><span class="s">"%s"</span><span class="p">,</span> <span class="n">t</span><span class="p">);
1012</span> 1013 <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="n">strlen</span><span class="p">(</span><span class="n">t</span><span class="p">),</span> <span class="n">dap</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> 1014 <span class="n">manacher</span><span class="p">(</span><span class="n">n</span><span class="p">);</span> 1015 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">n</span> <span class="o">*</span> <span class="mi">2</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> 1016 <span class="k">if</span> <span class="p">(</span><span class="n">i</span> <span class="o">%</span> <span class="mi">2</span><span class="p">)</span> <span class="n">dap</span> <span class="o">+=</span> <span class="p">(</span><span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span> 1017 <span class="k">else</span> <span class="n">dap</span> <span class="o">+=</span> <span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span> 1018 <span class="p">}</span> 1019 <span class="n">printf</span><span class="p">(</span><span class="s">"%d</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="n">dap</span> <span class="o">+</span> <span class="n">n</span><span class="p">);</span> 1020 <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> 1021<span class="p">}</span> 1022</code></pre></div></div> 1023 1024<h2 id="geometry-기í">Geometry 기í</h2> 1025 1026<h3 id="convex-hull-컨벡ì¤í">Convex Hull 컨벡ì¤í</h3> 1027 1028<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include</span><span class="cpf"><cstdio></span><span class="cp"> 1029#include</span><span class="cpf"><algorithm></span><span class="cp"> 1030#include</span><span class="cpf"><tuple></span><span class="cp"> 1031#include</span><span class="cpf"><vector></span><span class="cp"> 1032#include</span><span class="cpf"><cmath></span><span class="cp"> 1033</span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> 1034<span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> 1035<span class="k">typedef</span> <span class="n">pair</span><span class="o"><</span><span class="kt">int</span><span class="p">,</span><span class="kt">int</span><span class="o">></span> <span class="n">pii</span><span class="p">;</span> 1036<span class="k">struct</span> <span class="nc">POINT</span><span class="p">{</span> 1037 <span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">;</span> 1038 <span class="kt">bool</span> <span class="k">operator</span> <span class="o"><</span><span class="p">(</span><span class="n">POINT</span> <span class="n">a</span><span class="p">)</span><span class="k">const</span> <span class="p">{</span> 1039 <span class="k">return</span> <span class="n">x</span> <span class="o">==</span> <span class="n">a</span><span class="p">.</span><span class="n">x</span> <span class="o">?</span> <span class="n">y</span> <span class="o"><</span> <span class="n">a</span><span class="p">.</span><span class="n">y</span> <span class="o">:</span> <span class="n">x</span> <span class="o"><</span> <span class="n">a</span><span class="p">.</span><span class="n">x</span><span class="p">;</span> 1040 <span class="p">}</span> 1041 <span class="n">POINT</span> <span class="k">operator</span> <span class="o">-</span><span class="p">(</span><span class="n">POINT</span> <span class="n">a</span><span class="p">)</span><span class="k">const</span> <span class="p">{</span>
1042 <span class="k">return</span> <span class="p">{</span> <span class="n">x</span><span class="o">-</span><span class="n">a</span><span class="p">.</span><span class="n">x</span><span class="p">,</span><span class="n">y</span><span class="o">-</span><span class="n">a</span><span class="p">.</span><span class="n">y</span> <span class="p">};</span> 1043 <span class="p">}</span> 1044<span class="p">};</span> 1045<span class="kt">int</span> <span class="n">N</span><span class="p">;</span> 1046<span class="n">ll</span> <span class="n">sq</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">){</span> 1047 <span class="k">return</span> <span class="p">(</span><span class="n">ll</span><span class="p">)</span><span class="n">x</span><span class="o">*</span><span class="n">x</span><span class="p">;</span> 1048<span class="p">}</span> 1049<span class="n">ll</span> <span class="n">dst</span><span class="p">(</span><span class="n">POINT</span> <span class="n">A</span><span class="p">,</span> <span class="n">POINT</span> <span class="n">B</span><span class="p">)</span> <span class="p">{</span> 1050 <span class="k">return</span> <span class="n">sq</span><span class="p">(</span><span class="n">A</span><span class="p">.</span><span class="n">x</span><span class="o">-</span><span class="n">B</span><span class="p">.</span><span class="n">x</span><span class="p">)</span><span class="o">+</span><span class="n">sq</span><span class="p">(</span><span class="n">A</span><span class="p">.</span><span class="n">y</span><span class="o">-</span><span class="n">B</span><span class="p">.</span><span class="n">y</span><span class="p">);</span> 1051<span class="p">}</span> 1052<span class="kt">int</span> <span class="n">ccw</span><span class="p">(</span><span class="n">POINT</span> <span class="n">A</span><span class="p">,</span> <span class="n">POINT</span> <span class="n">B</span><span class="p">,</span> <span class="n">POINT</span> <span class="n">C</span><span class="p">){</span> 1053 <span class="n">ll</span> <span class="n">r</span> <span class="o">=</span> <span class="n">A</span><span class="p">.</span><span class="n">x</span><span class="o">*</span><span class="n">B</span><span class="p">.</span><span class="n">y</span> <span class="o">+</span> <span class="n">B</span><span class="p">.</span><span class="n">x</span><span class="o">*</span><span class="n">C</span><span class="p">.</span><span class="n">y</span> <span class="o">+</span> <span class="n">C</span><span class="p">.</span><span class="n">x</span><span class="o">*</span><span class="n">A</span><span class="p">.</span><span class="n">y</span><span class="p">;</span> 1054 <span class="n">r</span> <span class="o">-=</span> <span class="n">A</span><span class="p">.</span><span class="n">y</span><span class="o">*</span><span class="n">B</span><span class="p">.</span><span class="n">x</span> <span class="o">+</span> <span class="n">B</span><span class="p">.</span><span class="n">y</span><span class="o">*</span><span class="n">C</span><span class="p">.</span><span class="n">x</span> <span class="o">+</span> <span class="n">C</span><span class="p">.</span><span class="n">y</span><span class="o">*</span><span class="n">A</span><span class="p">.</span><span class="n">x</span><span class="p">;</span> 1055 <span class="k">if</span> <span class="p">(</span><span class="n">r</span> <span class="o">></span> <span class="mi">0</span><span class="p">)</span> <span class="k">return</span> <span class="mi">1</span><span class="p">;</span> 1056 <span class="k">if</span> <span class="p">(</span><span class="n">r</span> <span class="o"><</span> <span class="mi">0</span><span class="p">)</span> <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span> 1057 <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> 1058<span class="p">}</span> 1059 1060<span class="n">vector</span><span class="o"><</span><span class="n">POINT</span><span class="o">></span> <span class="n">GetConvexHull</span><span class="p">(</span><span class="n">vector</span><span class="o"><</span><span class="n">POINT</span><span class="o">></span> <span class="o">&</span><span class="n">p</span><span class="p">)</span> <span class="p">{</span> 1061 <span class="n">swap</span><span class="p">(</span><span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span> <span class="o">*</span><span class="n">min_element</span><span class="p">(</span><span class="n">p</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span> <span class="n">p</span><span class="p">.</span><span class="n">end</span><span class="p">()));
1061</span> 1062 <span class="n">sort</span><span class="p">(</span><span class="n">p</span><span class="p">.</span><span class="n">begin</span><span class="p">()</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">p</span><span class="p">.</span><span class="n">end</span><span class="p">(),</span> <span class="p">[</span><span class="o">&</span><span class="p">](</span><span class="k">const</span> <span class="n">POINT</span> <span class="o">&</span><span class="n">A</span><span class="p">,</span> <span class="k">const</span> <span class="n">POINT</span> <span class="o">&</span><span class="n">B</span><span class="p">){</span> 1063 <span class="k">if</span><span class="p">(</span><span class="n">ccw</span><span class="p">(</span><span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span> <span class="n">A</span><span class="p">,</span> <span class="n">B</span><span class="p">)</span> <span class="o">!=</span> <span class="mi">0</span><span class="p">){</span> 1064 <span class="k">return</span> <span class="n">ccw</span><span class="p">(</span><span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span> <span class="n">A</span><span class="p">,</span> <span class="n">B</span><span class="p">)</span> <span class="o"><</span> <span class="mi">0</span><span class="p">;</span> 1065 <span class="p">}</span> 1066 <span class="k">return</span> <span class="n">dst</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">])</span> <span class="o"><</span> <span class="n">dst</span><span class="p">(</span><span class="n">B</span><span class="p">,</span> <span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">]);</span> 1067 <span class="p">});</span> 1068 <span class="n">vector</span><span class="o"><</span><span class="n">POINT</span><span class="o">></span> <span class="n">hull</span><span class="p">;</span> 1069 <span class="n">hull</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">]);</span> 1070 <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">N</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> 1071 <span class="k">while</span><span class="p">(</span><span class="n">hull</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">>=</span> <span class="mi">2</span> <span class="o">&&</span> <span class="n">ccw</span><span class="p">(</span><span class="n">hull</span><span class="p">[</span><span class="n">hull</span><span class="p">.</span><span class="n">size</span><span class="p">()</span><span class="o">-</span><span class="mi">2</span><span class="p">],</span> <span class="n">hull</span><span class="p">.</span><span class="n">back</span><span class="p">(),</span> <span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="o">>=</span> <span class="mi">0</span><span class="p">){</span> 1072 <span class="n">hull</span><span class="p">.</span><span class="n">pop_back</span><span class="p">();</span> 1073 <span class="p">}</span> 1074 <span class="n">hull</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> 1075 <span class="p">}</span> 1076 <span class="k">return</span> <span class="n">hull</span><span class="p">;</span> 1077<span class="p">}</span> 1078 1079<span class="n">pii</span> <span class="n">FarthestPair</span><span class="p">(</span><span class="n">vector</span><span class="o"><</span><span class="n">POINT</span><span class="o">></span> <span class="o">&</span><span class="n">hull</span><span class="p">)</span> <span class="p">{</span> 1080 <span class="n">pii</span> <span class="n">ret</span><span class="p">;</span> 1081 <span class="n">ll</span> <span class="n">mx</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span> 1082 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">hull</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
1083 <span class="k">while</span> <span class="p">(</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span> <span class="o"><</span> <span class="n">hull</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">&&</span> <span class="n">ccw</span><span class="p">({</span> <span class="mi">0</span><span class="p">,</span><span class="mi">0</span> <span class="p">},</span> <span class="n">hull</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span><span class="o">-</span><span class="n">hull</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">hull</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span><span class="o">-</span><span class="n">hull</span><span class="p">[</span><span class="n">j</span><span class="p">])</span> <span class="o"><=</span> <span class="mi">0</span><span class="p">)</span> <span class="p">{</span> 1084 <span class="k">if</span> <span class="p">(</span><span class="n">mx</span> <span class="o"><</span> <span class="n">dst</span><span class="p">(</span><span class="n">hull</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">hull</span><span class="p">[</span><span class="n">j</span><span class="p">]))</span> <span class="p">{</span> 1085 <span class="n">mx</span> <span class="o">=</span> <span class="n">dst</span><span class="p">(</span><span class="n">hull</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">hull</span><span class="p">[</span><span class="n">j</span><span class="p">]);</span> 1086 <span class="n">ret</span> <span class="o">=</span> <span class="p">{</span> <span class="n">i</span><span class="p">,</span><span class="n">j</span> <span class="p">};</span> 1087 <span class="p">}</span> 1088 <span class="n">j</span><span class="o">++</span><span class="p">;</span> 1089 <span class="p">}</span> 1090 <span class="k">if</span> <span class="p">(</span><span class="n">mx</span> <span class="o"><</span> <span class="n">dst</span><span class="p">(</span><span class="n">hull</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">hull</span><span class="p">[</span><span class="n">j</span><span class="p">]))</span> <span class="p">{</span> 1091 <span class="n">mx</span> <span class="o">=</span> <span class="n">dst</span><span class="p">(</span><span class="n">hull</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">hull</span><span class="p">[</span><span class="n">j</span><span class="p">]);</span> 1092 <span class="n">ret</span> <span class="o">=</span> <span class="p">{</span> <span class="n">i</span><span class="p">,</span><span class="n">j</span> <span class="p">};</span> 1093 <span class="p">}</span> 1094 <span class="p">}</span> 1095 <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> 1096<span class="p">}</span> 1097 1098<span class="kt">int</span> <span class="n">main</span><span class="p">(){</span> 1099 <span class="n">scanf</span><span class="p">(</span><span class="s">"%d"</span><span class="p">,</span> <span class="o">&</span><span class="n">N</span><span class="p">);</span> 1100 <span class="n">vector</span><span class="o"><</span><span class="n">POINT</span><span class="o">></span> <span class="n">p</span><span class="p">(</span><span class="n">N</span><span class="p">);</span> 1101 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">N</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
1102 <span class="n">scanf</span><span class="p">(</span><span class="s">"%d%d"</span><span class="p">,</span> <span class="o">&</span><span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">x</span><span class="p">,</span> <span class="o">&</span><span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">y</span><span class="p">);</span> 1103 <span class="p">}</span> 1104 1105 <span class="n">vector</span><span class="o"><</span><span class="n">POINT</span><span class="o">></span> <span class="n">hull</span> <span class="o">=</span> <span class="n">GetConvexHull</span><span class="p">(</span><span class="n">p</span><span class="p">);</span> 1106 <span class="kt">int</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">;</span> <span class="n">tie</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">)</span> <span class="o">=</span> <span class="n">FarthestPair</span><span class="p">(</span><span class="n">hull</span><span class="p">);</span> 1107 <span class="n">printf</span><span class="p">(</span><span class="s">"%.8lf"</span><span class="p">,</span> <span class="n">sqrt</span><span class="p">(</span><span class="n">dst</span><span class="p">(</span><span class="n">hull</span><span class="p">[</span><span class="n">a</span><span class="p">],</span> <span class="n">hull</span><span class="p">[</span><span class="n">b</span><span class="p">])));</span> 1108 1109 <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> 1110<span class="p">}</span> 1111</code></pre></div></div> 1112 1113<h3 id="point-in-polygon">Point in Polygon</h3> 1114 1115<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include</span> <span class="cpf"><vector></span><span class="cp"> 1116</span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> 1117<span class="k">struct</span> <span class="nc">point</span> <span class="p">{</span> <span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">;</span> <span class="p">};</span> 1118<span class="k">typedef</span> <span class="n">vector</span><span class="o"><</span><span class="n">point</span><span class="o">></span> <span class="n">polygon</span><span class="p">;</span> 1119<span class="kt">bool</span> <span class="n">isInside</span><span class="p">(</span><span class="n">point</span> <span class="n">B</span><span class="p">,</span> <span class="n">vector</span><span class="o"><</span><span class="n">point</span><span class="o">></span> <span class="o">&</span><span class="n">p</span><span class="p">)</span> <span class="p">{</span> 1120 <span class="kt">int</span> <span class="n">cross</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> 1121 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">p</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> 1122 <span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="p">(</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span> <span class="o">%</span> <span class="n">p</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> 1123 <span class="k">if</span> <span class="p">((</span><span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">y</span> <span class="o">></span> <span class="n">B</span><span class="p">.</span><span class="n">y</span><span class="p">)</span> <span class="o">!=</span> <span class="p">(</span><span class="n">p</span><span class="p">[</span><span class="n">j</span><span class="p">].</span><span class="n">y</span> <span class="o">></span> <span class="n">B</span><span class="p">.</span><span class="n">y</span><span class="p">))</span> <span class="p">{</span>
1124 <span class="kt">double</span> <span class="n">atX</span> <span class="o">=</span> <span class="p">(</span><span class="n">p</span><span class="p">[</span><span class="n">j</span><span class="p">].</span><span class="n">x</span><span class="o">-</span><span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">x</span><span class="p">)</span><span class="o">*</span><span class="p">(</span><span class="n">B</span><span class="p">.</span><span class="n">y</span><span class="o">-</span><span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">y</span><span class="p">)</span><span class="o">/</span><span class="p">(</span><span class="n">p</span><span class="p">[</span><span class="n">j</span><span class="p">].</span><span class="n">y</span><span class="o">-</span><span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">y</span><span class="p">)</span><span class="o">+</span><span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">x</span><span class="p">;</span> 1125 <span class="k">if</span> <span class="p">(</span><span class="n">B</span><span class="p">.</span><span class="n">x</span> <span class="o"><</span> <span class="n">atX</span><span class="p">)</span> <span class="n">cross</span><span class="o">++</span><span class="p">;</span> 1126 <span class="p">}</span> 1127 <span class="p">}</span> 1128 <span class="k">return</span> <span class="n">cross</span> <span class="o">%</span> <span class="mi">2</span> <span class="o">></span> <span class="mi">0</span><span class="p">;</span> 1129<span class="p">}</span> 1130</code></pre></div></div> 1131 1132<h3 id="line-intersect-cross-ì ë¶-êµì°¨">line intersect cross ì ë¶ êµì°¨</h3> 1133 1134<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="kt">int</span> <span class="nf">ccw</span><span class="p">(</span><span class="n">point</span> <span class="n">a</span><span class="p">,</span> <span class="n">point</span> <span class="n">b</span><span class="p">,</span> <span class="n">point</span> <span class="n">c</span><span class="p">)</span> <span class="p">{</span> 1135 <span class="c1">// r ì¤ë²íë¡ì° 주ì</span> 1136 <span class="n">ll</span> <span class="n">r</span> <span class="o">=</span> <span class="n">a</span><span class="p">.</span><span class="n">x</span> <span class="o">*</span> <span class="n">b</span><span class="p">.</span><span class="n">y</span> <span class="o">+</span> <span class="n">b</span><span class="p">.</span><span class="n">x</span> <span class="o">*</span> <span class="n">c</span><span class="p">.</span><span class="n">y</span> <span class="o">+</span> <span class="n">c</span><span class="p">.</span><span class="n">x</span> <span class="o">*</span> <span class="n">a</span><span class="p">.</span><span class="n">y</span><span class="p">;</span> 1137 <span class="n">r</span> <span class="o">-=</span> <span class="n">a</span><span class="p">.</span><span class="n">y</span> <span class="o">*</span> <span class="n">b</span><span class="p">.</span><span class="n">x</span> <span class="o">+</span> <span class="n">b</span><span class="p">.</span><span class="n">y</span> <span class="o">*</span> <span class="n">c</span><span class="p">.</span><span class="n">x</span> <span class="o">+</span> <span class="n">c</span><span class="p">.</span><span class="n">y</span> <span class="o">*</span> <span class="n">a</span><span class="p">.</span><span class="n">x</span><span class="p">;</span> 1138 <span class="k">if</span> <span class="p">(</span><span class="n">r</span> <span class="o">></span> <span class="mi">0</span><span class="p">)</span> <span class="k">return</span> <span class="mi">1</span><span class="p">;</span> 1139 <span class="k">if</span> <span class="p">(</span><span class="n">r</span> <span class="o"><</span> <span class="mi">0</span><span class="p">)</span> <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span> 1140 <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> 1141<span class="p">}</span> 1142 1143<span class="kt">int</span> <span class="n">isCross</span><span class="p">(</span><span class="n">point</span> <span class="n">a</span><span class="p">,</span> <span class="n">point</span> <span class="n">b</span><span class="p">,</span> <span class="n">point</span> <span class="n">c</span><span class="p">,</span> <span class="n">point</span> <span class="n">d</span><span class="p">)</span> <span class="p">{</span> 1144 <span class="kt">int</span> <span class="n">ab</span> <span class="o">=</span> <span class="n">ccw</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">c</span><span class="p">)</span><span class="o">*</span><span class="n">ccw</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">d</span><span class="p">);</span> 1145 <span class="kt">int</span> <span class="n">cd</span> <span class="o">=</span> <span class="n">ccw</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">d</span><span class="p">,</span> <span class="n">a</span><span class="p">)</span><span class="o">*</span><span class="n">ccw</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">d</span><span class="p">,</span> <span class="n">b</span><span class="p">);</span> 1146 <span class="k">if</span> <span class="p">(</span><span class="n">ab</span> <span class="o">==</span> <span class="mi">0</span> <span class="o">&&</span> <span class="n">cd</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="p">{</span>
1147 <span class="k">if</span> <span class="p">(</span><span class="n">a</span> <span class="o">></span> <span class="n">b</span><span class="p">)</span> <span class="n">swap</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">);</span> 1148 <span class="k">if</span> <span class="p">(</span><span class="n">c</span> <span class="o">></span> <span class="n">d</span><span class="p">)</span> <span class="n">swap</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">d</span><span class="p">);</span> 1149 <span class="k">return</span> <span class="n">c</span> <span class="o"><=</span> <span class="n">b</span> <span class="o">&&</span> <span class="n">a</span> <span class="o"><=</span> <span class="n">d</span><span class="p">;</span> 1150 <span class="p">}</span> 1151 <span class="k">return</span> <span class="n">ab</span> <span class="o"><=</span> <span class="mi">0</span> <span class="o">&&</span> <span class="n">cd</span> <span class="o"><=</span> <span class="mi">0</span><span class="p">;</span> 1152<span class="p">}</span> 1153</code></pre></div></div> 1154 1155<h2 id="magic-íë§ë²">Magic íë§ë²</h2> 1156 1157<h3 id="pbds-bst">pbds BST</h3> 1158 1159<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include</span> <span class="cpf"><ext/pb_ds/assoc_container.hpp></span><span class="cp"> 1160#include</span> <span class="cpf"><ext/pb_ds/tree_policy.hpp></span><span class="cp"> 1161</span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> 1162<span class="k">using</span> <span class="k">namespace</span> <span class="n">__gnu_pbds</span><span class="p">;</span> 1163<span class="k">typedef</span> <span class="n">tree</span><span class="o"><</span><span class="kt">int</span><span class="p">,</span> <span class="n">null_type</span><span class="p">,</span> <span class="n">less</span><span class="o"><</span><span class="kt">int</span><span class="o">></span><span class="p">,</span> <span class="n">rb_tree_tag</span><span class="p">,</span> <span class="n">tree_order_statistics_node_update</span><span class="o">></span> <span class="n">ordered_set</span><span class="p">;</span> 1164<span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> 1165 <span class="n">ordered_set</span> <span class="n">X</span><span class="p">;</span> 1166 <span class="n">X</span><span class="p">.</span><span class="n">insert</span><span class="p">(</span><span class="mi">4</span><span class="p">);</span> 1167 <span class="n">cout</span> <span class="o"><<</span> <span class="o">*</span><span class="n">X</span><span class="p">.</span><span class="n">find_by_order</span><span class="p">(</span><span class="mi">4</span><span class="p">)</span> <span class="o"><<</span> <span class="n">endl</span><span class="p">;</span> 1168 <span class="n">cout</span> <span class="o"><<</span> <span class="n">X</span><span class="p">.</span><span class="n">order_of_key</span><span class="p">(</span><span class="mi">3</span><span class="p">)</span> <span class="o"><<</span> <span class="n">endl</span><span class="p">;</span> 1169<span class="p">}</span> 1170</code></pre></div></div> 1171 1172<h3 id="2d-arrary-rotation-ë°°ì´-ë리기">2D arrary rotation ë°°ì´ ë리기</h3> 1173 1174<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="c1">// Rotate n * m array A by clockwise and save in B (A: n * m, B: m * n)</span> 1175<span class="kt">void</span> <span class="nf">rotate90</span><span class="p">(</span><span class="kt">int</span> <span class="o">**</span><span class="n">A</span><span class="p">,</span> <span class="kt">int</span> <span class="o">**</span><span class="n">B</span><span class="p">,</span> <span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="kt">int</span> <span class="n">m</span><span class="p">)</span> <span class="p">{</span> 1176 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
1177 <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">j</span> <span class="o"><</span> <span class="n">n</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> 1178 <span class="n">B</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">A</span><span class="p">[</span><span class="n">n</span> <span class="o">-</span> <span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="p">][</span><span class="n">i</span><span class="p">];</span> 1179<span class="p">}</span> 1180</code></pre></div></div> 1181 1182 </div> 1183</div> 1184 1185 1186 <div class="clearfix"></div> 1187 1188 <a href="#" id="back-to-top"></a> 1189</div> 1190 1191<div id="footer" class="container-fluid"> 1192 <ul id="links"> 1193 1194 <li> 1195 <a id="link-github" href="http://github.com/wookje" target="_blank"> 1196 <span class="sr-only">github</span> 1197 </a> 1198 </li> 1199 1200 1201 <li> 1202 <a id="link-facebook" href="http://facebook.com/wookje" target="_blank"> 1203 <span class="sr-only">facebook</span> 1204 </a> 1205 </li> 1206 1207 1208 1209 <li> 1210 <a id="link-rss" href="/rss" target="_blank"> 1211 <span class="sr-only">rss</span> 1212 </a> 1213 </li> 1214 </ul> 1215 <!--<ul id="footer-menu"> 1216 <li><a href="//www.kakaocorp.com">Kakao</a></li> 1217 <li><a href="//www.kakaocorp.com/recruit/currentOpportunities">Jobs</a></li> 1218 <li><a href="//privacy.kakaocorp.com">Privacy</a></li> 1219 </ul>--> 1220 <p id="copyright"> 1221 <a>Copyright © Wookje Kwon.</a> 1222 All rights reserved. 1223 </p> 1224</div><!--#footer--> 1225 1226
1227<script src="/assets/lib/jquery-1.12.0.min.js"></script>
vendor: 1 bytes, line 1227
1227
1228<script src="/assets/lib/jquery.magnific-popup.min.js"></script>
vendor: 1 bytes, line 1228
1228
1229<script src="/assets/js/index.js"></script>
vendor: 1 bytes, line 1229
1229
1230<script src="//developers.kakao.com/sdk/js/kakao.min.js"></script>
1230 1231 1232 1233<!--
1233<script>
vendor: 485 bytes, lines 1233-1245
1233 1234 (function (i, s, o, g, r, a, m) { 1235 i['GoogleAnalyticsObject'] = r; 1236 i[r] = i[r] || function () { 1237 (i[r].q = i[r].q || []).push(arguments) 1238 }, i[r].l = 1 * new Date(); 1239 a = s.createElement(o), 1240 m = s.getElementsByTagName(o)[0]; 1241 a.async = 1; 1242 a.src = g; 1243 m.parentNode.insertBefore(a, m) 1244 })(window, document, 'script', '//www.google-analytics.com/analytics.js', 'ga'); 1245 ga('create', '
1245UA-91755632-1
vendor: 40 bytes, lines 1245-1246
1245', 'auto'); 1246 ga('send', 'pageview');
1247</script>
1247 --> 1248<!-- Google tag (gtag.js) -->
vendor: 64 bytes, lines 1248-1249
1248 1249<script async src="https://www.googletagmanager.com/gtag/js?id=
1249G-8MPYXFJ7VV
vendor: 12 bytes, line 1249
1249"></script>
1250<script> 1251
vendor: 134 bytes, lines 1251-1255
1251window.dataLayer = window.dataLayer || []; 1252 function gtag(){dataLayer.push(arguments);} 1253 gtag('js', new Date()); 1254 1255 gtag('config', '
1255G-8MPYXFJ7VV
vendor: 4 bytes, line 1255
1255');
1256</script>
1256 1257 1258 1259 1260 <!--
1261<script type='text/javascript'> 1262 //<![CDATA[ 1263 // // ì¬ì©í ì±ì JavaScript í¤ë¥¼ ì¤ì í´ ì£¼ì¸ì. 1264 Kakao.init('65d48e116d8b9409e08960c4800c3017'); 1265 // // ì¹´ì¹´ì¤ë§í¬ ë²í¼ì ìì±í©ëë¤. ì²ì íë²ë§ í¸ì¶íë©´ ë©ëë¤. 1266 var ogImg = $('meta[property="og:image"]').attr('content').replace("tech.kakao.com", "kakao.github.io"); 1267 var ogTitle = $('meta[property="og:title"]').attr('content'); 1268 var ogUrl = $('meta[property="og:url"]').attr('content'); 1269 Kakao.Link.createTalkLinkButton({ 1270 container: '#kakao-link-btn', 1271 label: ogTitle, 1272 image: { 1273 src: ogImg, 1274 width: '300', 1275 height: '200' 1276 }, 1277 webButton: { 1278 text: 'ì¹´ì¹´ì¤ ê¸°ì ë¸ë¡ê·¸', 1279 url: ogUrl // ì± ì¤ì ì ì¹ íë«í¼ì ë±ë¡í ëë©ì¸ì URLì´ì´ì¼ í©ëë¤. 1280 }, 1281 forwardable: true 1282 }); 1283 //]]> 1284</script>
vendor: 1 bytes, line 1284
1284
1285<script> 1286 var _ua = navigator.userAgent.toLowerCase().match(/iphone|ipod|ipad|android/); 1287 var sb = document.getElementById("shares").getElementsByTagName("li"); 1288 if (_ua) { 1289 sb[0].style.display = "inline"; 1290 } 1291</script>
1291 1292--> 1293
1293<script type='text/javascript'> 1294 //<![CDATA[ 1295 // ì¬ì©í ì±ì JavaScript í¤ë¥¼ ì¤ì í´ ì£¼ì¸ì. 1296 //Kakao.init('65d48e116d8b9409e08960c4800c3017'); 1297 function shareStory(abs_page_url) { 1298 Kakao.Story.share({ 1299 url: abs_page_url, 1300 text: 'ì¹´ì¹´ì¤ ê¸°ì ë¸ë¡ê·¸ #ê°ë°ì #ì¹´ì¹´ì¤' 1301 }); 1302 } 1303 //]]> 1304</script>
1304 1305 1306 1307
1307<script> 1308window.fbAsyncInit = function() { 1309 FB.init({ 1310 appId : '956026527861303', 1311 xfbml : true, 1312 version : 'v2.7' 1313 }); 1314}; 1315 1316(function(d, s, id){ 1317 var js, fjs = d.getElementsByTagName(s)[0]; 1318 if (d.getElementById(id)) {return;} 1319 js = d.createElement(s); js.id = id; 1320 js.src = "//connect.facebook.net/en_US/sdk.js"; 1321 fjs.parentNode.insertBefore(js, fjs); 1322}(document, 'script', 'facebook-jssdk')); 1323</script>
1323 1324 1325 1326 1327 1328 1329 1330 1331</body> 1332</html>
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.