PageSourceSearch

https://wookje.dance/library/

html wookje.dance collected 2026-10-03 23:20:17 UTC 209,520 bytes, 1,332 lines download raw bytes

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">&lt;cstdio&gt;</span><span class="cp">
126#include</span><span class="cpf">&lt;iostream&gt;</span><span class="cp">
127#include</span><span class="cpf">&lt;algorithm&gt;</span><span class="cp">
128#include</span><span class="cpf">&lt;vector&gt;</span><span class="cp">
129#include</span><span class="cpf">&lt;queue&gt;</span><span class="cp">
130#include</span><span class="cpf">&lt;deque&gt;</span><span class="cp">
131#include</span><span class="cpf">&lt;stack&gt;</span><span class="cp">
132#include</span><span class="cpf">&lt;string&gt;</span><span class="cp">
133#include</span><span class="cpf">&lt;list&gt;</span><span class="cp">
134#include</span><span class="cpf">&lt;map&gt;</span><span class="cp">
135#include</span><span class="cpf">&lt;set&gt;</span><span class="cp">
136#include</span><span class="cpf">&lt;unordered_map&gt;</span><span class="cp">
137#include</span><span class="cpf">&lt;unordered_set&gt;</span><span class="cp">
138#include</span><span class="cpf">&lt;bitset&gt;</span><span class="cp">
139#include</span><span class="cpf">&lt;tuple&gt;</span><span class="cp">
140#include</span><span class="cpf">&lt;functional&gt;</span><span class="cp">
141#include</span><span class="cpf">&lt;utility&gt;</span><span class="cp">
142#include</span><span class="cpf">&lt;cmath&gt;</span><span class="cp">
143#include</span><span class="cpf">&lt;cstdlib&gt;</span><span class="cp">
144#include</span><span class="cpf">&lt;cstring&gt;</span><span class="cp">
145#include</span><span class="cpf">&lt;complex&gt;</span><span class="cp">
146#include</span><span class="cpf">&lt;cassert&gt;</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">&lt;</span><span class="kt">int</span><span class="p">,</span><span class="kt">int</span><span class="o">&gt;</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">&lt;</span><span class="n">ll</span><span class="p">,</span><span class="n">ll</span><span class="o">&gt;</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">&lt;</span><span class="kt">int</span><span class="o">&gt;</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">&lt;</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">&lt;</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">&lt;</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">&amp;</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">&gt;&gt;=</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">&lt;=</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">&amp;-</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">&amp;-</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">&lt;=</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">&lt;=</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">&amp;-</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">&lt;=</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">&amp;-</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">&lt;=</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">&amp;-</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">&lt;=</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">&amp;-</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">&lt;=</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">&amp;-</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">&amp;-</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">&lt;&lt;</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">&lt;=</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">&lt;&lt;</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">&lt;</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">&gt;&gt;</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">&lt;</span> <span class="n">s</span> <span class="o">||</span> <span class="n">e</span> <span class="o">&lt;</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">&gt;&gt;</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">&lt;=</span> <span class="n">s</span> <span class="o">&amp;&amp;</span> <span class="n">e</span> <span class="o">&lt;=</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">&lt;</span> <span class="n">x</span> <span class="o">||</span> <span class="n">y</span> <span class="o">&lt;</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">&gt;&gt;</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">&lt;vector&gt;</span><span class="cp">
357#include</span> <span class="cpf">&lt;algorithm&gt;</span><span class="cp">
358#include</span> <span class="cpf">&lt;queue&gt;</span><span class="cp">
359#include</span> <span class="cpf">&lt;cstring&gt;</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">&lt;</span><span class="n">edg</span><span class="o">&gt;</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">&lt;</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">&lt;</span><span class="kt">int</span><span class="o">&gt;</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">&gt;</span> <span class="mi">0</span> <span class="o">&amp;&amp;</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">&amp;</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">&lt;</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">&amp;</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">&gt;</span> <span class="mi">0</span> <span class="o">&amp;&amp;</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">&gt;</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">&lt;vector&gt;</span><span class="cp">
470#include</span> <span class="cpf">&lt;algorithm&gt;</span><span class="cp">
471#include</span> <span class="cpf">&lt;queue&gt;</span><span class="cp">
472#include</span> <span class="cpf">&lt;cstring&gt;</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">&lt;</span><span class="n">edg</span><span class="o">&gt;</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">&lt;</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">&lt;</span><span class="kt">int</span><span class="o">&gt;</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">&lt;</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">&amp;</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">&gt;</span> <span class="mi">0</span> <span class="o">&amp;&amp;</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">&gt;</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">&lt;</span><span class="kt">int</span><span class="p">,</span> <span class="kt">int</span><span class="o">&gt;</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">&lt;algorithm&gt;</span><span class="cp">
545#include</span> <span class="cpf">&lt;vector&gt;</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 &gt; 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">&lt;</span><span class="kt">int</span><span class="o">&gt;</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">&lt;=</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">&lt;</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">&gt;=</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">&lt;=</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">&gt;=</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">&lt;&lt;</span> <span class="n">d</span><span class="p">)</span> <span class="o">&lt;=</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">&lt;algorithm&gt;</span><span class="cp">
577#include</span> <span class="cpf">&lt;vector&gt;</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 &gt; 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">&lt;</span><span class="kt">int</span><span class="o">&gt;</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">&lt;=</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">&lt;</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">&gt;=</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">&lt;=</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">&lt;&lt;</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">&gt;=</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">&lt;&lt;</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">&lt;&lt;</span> <span class="n">d</span><span class="p">)</span> <span class="o">&lt;=</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">&lt;algorithm&gt;</span><span class="cp">
614#include</span> <span class="cpf">&lt;vector&gt;</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">&lt;</span><span class="kt">int</span><span class="o">&gt;</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">&gt;=</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">&lt;=</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">&lt;vector&gt;</span><span class="cp">
645#include</span> <span class="cpf">&lt;algorithm&gt;</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">&lt;</span><span class="kt">int</span><span class="o">&gt;</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">&lt;</span><span class="n">pair</span><span class="o">&lt;</span><span class="kt">int</span><span class="p">,</span> <span class="kt">int</span><span class="o">&gt;</span> <span class="o">&gt;</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">&gt;</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">&lt;</span><span class="n">ll</span><span class="o">&gt;</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">&lt;</span><span class="n">ll</span><span class="o">&gt;</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">&lt;=</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">&lt;=</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">&lt;=</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">&amp;&amp;</span> <span class="n">s</span> <span class="o">&lt;=</span> <span class="n">i</span> <span class="o">&amp;&amp;</span> <span class="n">i</span> <span class="o">&lt;=</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">&lt;</span><span class="n">ll</span><span class="o">&gt;</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">&lt;</span><span class="n">ll</span><span class="o">&gt;</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">&lt;=</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">&lt;</span><span class="n">pair</span><span class="o">&lt;</span><span class="n">ll</span><span class="p">,</span> <span class="kt">int</span><span class="o">&gt;</span> <span class="o">&gt;</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">&lt;</span><span class="n">pair</span><span class="o">&lt;</span><span class="n">ll</span><span class="p">,</span> <span class="kt">int</span><span class="o">&gt;</span> <span class="o">&gt;</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">&lt;=</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">&lt;</span><span class="kt">int</span><span class="p">,</span><span class="kt">int</span><span class="o">&gt;</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">&lt;</span><span class="kt">int</span><span class="o">&gt;</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">&gt;&gt;</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) -&gt; c(2n)</span>
782        <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</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">&lt;=</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">&lt;=</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">&gt;</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">&lt;=</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) -&gt; c(n+1)</span>
788        <span class="k">if</span> <span class="p">((</span><span class="n">n</span><span class="o">&gt;&gt;</span><span class="n">b</span><span class="p">)</span><span class="o">&amp;</span><span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
789            <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</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">&lt;=</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">&lt;=</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">&gt;&gt;</span> <span class="n">n</span> <span class="o">&gt;&gt;</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">&lt;=</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">&gt;&gt;</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">&lt;=</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">&gt;&gt;</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">&lt;&lt;</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">&lt;cstdio&gt;</span><span class="cp">
817#include</span> <span class="cpf">&lt;cmath&gt;</span><span class="cp">
818#include</span> <span class="cpf">&lt;complex&gt;</span><span class="cp">
819#include</span> <span class="cpf">&lt;vector&gt;</span><span class="cp">
820#include</span> <span class="cpf">&lt;algorithm&gt;</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">&lt;</span><span class="kt">double</span><span class="o">&gt;</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">&lt;</span><span class="n">base</span><span class="o">&gt;</span> <span class="o">&amp;</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">&lt;</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">&gt;&gt;</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">&gt;=</span><span class="n">bit</span><span class="p">;</span><span class="n">bit</span><span class="o">&gt;&gt;=</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">&lt;</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">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">len</span><span class="o">&lt;&lt;=</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">&lt;</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">&lt;</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">&lt;</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">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">multiply</span><span class="p">(</span><span class="k">const</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="o">&amp;</span><span class="n">a</span><span class="p">,</span><span class="k">const</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="o">&amp;</span><span class="n">b</span><span class="p">)</span> <span class="p">{</span>
849    <span class="n">vector</span> <span class="o">&lt;</span><span class="n">base</span><span class="o">&gt;</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">&lt;</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">&lt;&lt;=</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">&lt;</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">&lt;</span><span class="kt">int</span><span class="o">&gt;</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">&lt;</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">&gt;</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">&lt;</span><span class="kt">int</span><span class="o">&gt;</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">&amp;</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">&lt;</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">&amp;</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">&lt;</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">&amp;</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">&lt;</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">&lt;vector&gt;</span><span class="cp">
888#include</span> <span class="cpf">&lt;string&gt;</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">&lt;</span><span class="kt">int</span><span class="o">&gt;</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">&lt;</span><span class="kt">int</span><span class="o">&gt;</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">&lt;</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">&amp;&amp;</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">&lt;</span><span class="kt">int</span><span class="o">&gt;</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">&lt;</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">&amp;&amp;</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">&lt;iostream&gt;</span><span class="cp">
933#include</span> <span class="cpf">&lt;string&gt;</span><span class="cp">
934#include</span> <span class="cpf">&lt;vector&gt;</span><span class="cp">
935#include</span> <span class="cpf">&lt;algorithm&gt;</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">&lt;</span><span class="kt">int</span><span class="o">&gt;</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">&amp;</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">&lt;=</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">&lt;=</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">&lt;</span><span class="n">N</span><span class="p">;</span><span class="n">len</span><span class="o">&lt;&lt;=</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">&lt;=</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">&lt;=</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">&gt;</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">&lt;=</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">&lt;=</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">&lt;=</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">&lt;</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">&lt;=</span> <span class="n">N</span> <span class="o">&amp;&amp;</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">&lt;=</span> <span class="n">N</span> <span class="o">&amp;&amp;</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">&amp;&amp;</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">&amp;</span><span class="n">S</span><span class="p">,</span> <span class="n">vi</span> <span class="o">&amp;</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">&lt;=</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">&lt;=</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">&gt;&gt;</span> <span class="n">n</span> <span class="o">&gt;&gt;</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">&lt;&lt;</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">&lt;cstring&gt;</span><span class="cp">
989#include</span> <span class="cpf">&lt;algorithm&gt;</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">&lt;</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">&lt;</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">&lt;=</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">&gt;=</span> <span class="mi">0</span> <span class="o">&amp;&amp;</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">&lt;</span> <span class="n">n</span> <span class="o">&amp;&amp;</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">&lt;</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">&lt;</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">&lt;cstdio&gt;</span><span class="cp">
1029#include</span><span class="cpf">&lt;algorithm&gt;</span><span class="cp">
1030#include</span><span class="cpf">&lt;tuple&gt;</span><span class="cp">
1031#include</span><span class="cpf">&lt;vector&gt;</span><span class="cp">
1032#include</span><span class="cpf">&lt;cmath&gt;</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">&lt;</span><span class="kt">int</span><span class="p">,</span><span class="kt">int</span><span class="o">&gt;</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">&lt;</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">&lt;</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">&lt;</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">&gt;</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">&lt;</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">&lt;</span><span class="n">POINT</span><span class="o">&gt;</span> <span class="n">GetConvexHull</span><span class="p">(</span><span class="n">vector</span><span class="o">&lt;</span><span class="n">POINT</span><span class="o">&gt;</span> <span class="o">&amp;</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">&amp;</span><span class="p">](</span><span class="k">const</span> <span class="n">POINT</span> <span class="o">&amp;</span><span class="n">A</span><span class="p">,</span> <span class="k">const</span> <span class="n">POINT</span> <span class="o">&amp;</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">&lt;</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">&lt;</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">&lt;</span><span class="n">POINT</span><span class="o">&gt;</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">&lt;</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">&gt;=</span> <span class="mi">2</span> <span class="o">&amp;&amp;</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">&gt;=</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">&lt;</span><span class="n">POINT</span><span class="o">&gt;</span> <span class="o">&amp;</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">&lt;</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">&lt;</span> <span class="n">hull</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">&amp;&amp;</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">&lt;=</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">&lt;</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">&lt;</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">&amp;</span><span class="n">N</span><span class="p">);</span>
1100    <span class="n">vector</span><span class="o">&lt;</span><span class="n">POINT</span><span class="o">&gt;</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">&lt;</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">&amp;</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">&amp;</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">&lt;</span><span class="n">POINT</span><span class="o">&gt;</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">&lt;vector&gt;</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">&lt;</span><span class="n">point</span><span class="o">&gt;</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">&lt;</span><span class="n">point</span><span class="o">&gt;</span> <span class="o">&amp;</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">&lt;</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">&gt;</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">&gt;</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">&lt;</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">&gt;</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">&gt;</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">&lt;</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">&amp;&amp;</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">&gt;</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">&gt;</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">&lt;=</span> <span class="n">b</span> <span class="o">&amp;&amp;</span> <span class="n">a</span> <span class="o">&lt;=</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">&lt;=</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">cd</span> <span class="o">&lt;=</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">&lt;ext/pb_ds/assoc_container.hpp&gt;</span><span class="cp">
1160#include</span> <span class="cpf">&lt;ext/pb_ds/tree_policy.hpp&gt;</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">&lt;</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">&lt;</span><span class="kt">int</span><span class="o">&gt;</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">&gt;</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">&lt;&lt;</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">&lt;&lt;</span> <span class="n">endl</span><span class="p">;</span>
1168    <span class="n">cout</span> <span class="o">&lt;&lt;</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">&lt;&lt;</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">&lt;</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">&lt;</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 &copy; 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.