diff options
Diffstat (limited to 'README.html')
| -rw-r--r-- | README.html | 538 |
1 files changed, 529 insertions, 9 deletions
diff --git a/README.html b/README.html index 664dc3d..e0b000a 100644 --- a/README.html +++ b/README.html @@ -2122,14 +2122,6 @@ width:100%; </tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
-<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>keyOffset</strong></p></td>
-<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">delta</span>)</p></td>
-<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
-<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
-<td class="tableblock halign-left valign-top" ><p class="tableblock">將所有Element的Key同加上 <span class="monospaced">delta</span></p></td>
-</tr>
-<tr>
-<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>insert</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">key</span>,<br>
Value const& <span class="monospaced">value</span>)</p></td>
@@ -2150,6 +2142,14 @@ Value const& <span class="monospaced">value</span>)</p></td> </tr>
<tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>keyOffset</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">delta</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">將所有Element的Key同加上 <span class="monospaced">delta</span></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>operator[]</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">key</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Value&</p></td>
@@ -2397,6 +2397,508 @@ Value const& <span class="monospaced">delta</span>)</p></td> <hr>
</div>
</div>
+<div class="sect2">
+<h3 id="_meow_strong_splaytree_range_lt_key_value_gt_strong_c_class">meow:: <strong>SplayTree_Range<Key, Value></strong> (C++ class)</h3>
+<div class="sect3">
+<h4 id="_description_10">Description</h4>
+<div class="paragraph"><p><span class="monospaced">SplayTree_Range</span> 是一種神乎其技的資料結構, 維護一堆 Key→Value. 並且支援
+一些 <span class="monospaced">std::map</span> 難以快速實踐的操作, 如 <span class="monospaced">split</span> , <span class="monospaced">merge</span> , <span class="monospaced">keyOffset</span></p></div>
+</div>
+<div class="sect3">
+<h4 id="_template_class_operators_request_6">Template Class Operators Request</h4>
+<table class="tableblock frame-all grid-rows"
+style="
+width:70%;
+">
+<col style="width:3%;">
+<col style="width:3%;">
+<col style="width:10%;">
+<col style="width:17%;">
+<col style="width:10%;">
+<col style="width:53%;">
+<thead>
+<tr>
+<th class="tableblock halign-right valign-top" >Const?</th>
+<th class="tableblock halign-left valign-top" >Typename</th>
+<th class="tableblock halign-left valign-top" > Operator</th>
+<th class="tableblock halign-left valign-top" > Parameters </th>
+<th class="tableblock halign-left valign-top" > Return_Type</th>
+<th class="tableblock halign-left valign-top" > Description</th>
+</tr>
+</thead>
+<tbody>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Key</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator+</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key <span class="monospaced">k</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Key</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">相加</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Key</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator<</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key <span class="monospaced">k</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">大小比較</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Key</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong><em>Key</em></strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(int <span class="monospaced">n</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">建構子, <span class="monospaced">n</span> 永遠是0</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Value</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong><em>Value</em></strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">( )</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">建構子</p></td>
+</tr>
+</tbody>
+</table>
+</div>
+<div class="sect3">
+<h4 id="_custom_type_definitions_4">Custom Type Definitions</h4>
+<div class="ulist"><ul>
+<li>
+<p>
+<span class="monospaced">Element</span> → 用來當作回傳資料的媒介
+</p>
+<div class="ulist"><ul>
+<li>
+<p>
+重定義 <span class="monospaced">operator->()</span> 到 <span class="monospaced">std::pair<Key const&, Value&>*</span>
+</p>
+</li>
+<li>
+<p>
+重定義 <span class="monospaced">operator*()</span> 到 <span class="monospaced">std::pair<Key const&, Value&>&</span>
+</p>
+</li>
+<li>
+<p>
+有 <span class="monospaced">operator==</span> , <span class="monospaced">operator!=</span>, <span class="monospaced">operator=</span> 可用
+</p>
+</li>
+<li>
+<p>
+可以直接用 <span class="monospaced">(*e).second = some_value</span> 來改變SplayTree_Range中的資料
+</p>
+</li>
+</ul></div>
+</li>
+</ul></div>
+</div>
+<div class="sect3">
+<h4 id="_support_methods_7">Support Methods</h4>
+<div class="ulist"><ul>
+<li>
+<p>
+N ← <span class="monospaced">this</span> 中擁有的資料數
+</p>
+</li>
+<li>
+<p>
+M ← <span class="monospaced">tree2</span> 中擁有的資料數
+</p>
+</li>
+</ul></div>
+<table class="tableblock frame-all grid-rows"
+style="
+width:100%;
+">
+<col style="width:2%;">
+<col style="width:8%;">
+<col style="width:18%;">
+<col style="width:8%;">
+<col style="width:8%;">
+<col style="width:54%;">
+<thead>
+<tr>
+<th class="tableblock halign-right valign-top" >Const?</th>
+<th class="tableblock halign-right valign-top" >Name </th>
+<th class="tableblock halign-left valign-top" > Parameters </th>
+<th class="tableblock halign-left valign-top" > Return_Type</th>
+<th class="tableblock halign-center valign-top" > Time_Complexity</th>
+<th class="tableblock halign-left valign-top" > Description</th>
+</tr>
+</thead>
+<tbody>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>moveTo</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(SplayTree_Range* <span class="monospaced">tree2</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(M)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">將 <span class="monospaced">this</span> 的資料複寫到 <span class="monospaced">tree2</span> 上面, 同時清空自己,
+時間複雜度中的M是 <span class="monospaced">tree2</span> 所擁有的資料數</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>lowerBound</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">k</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">找出第一個(最小的) Element且 <span class="monospaced">k</span> ⇐ 它的 Key, 並且回傳之.
+找不到的話回傳 <span class="monospaced">this->end()</span></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>lowerBound</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">k</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">找出第一個(最小的) Element且 <span class="monospaced">k</span> < 它的 Key, 並且回傳之.
+找不到的話回傳 <span class="monospaced">this->end()</span></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>lowerBound</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">k</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">找出第一個(最小的) Element且 <span class="monospaced">k</span> >= 它的 Key, 並且回傳之.
+找不到的話回傳 <span class="monospaced">this->end()</span></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>lowerBound</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">k</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">找出第一個(最小的) Element且 <span class="monospaced">k</span> > 它的 Key, 並且回傳之.
+找不到的話回傳 <span class="monospaced">this->end()</span></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>find</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">k</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">找出 Key= <span class="monospaced">k</span> 的Elemenet 並回傳. 找不到的話回傳 <span class="monospaced">this->end()</span></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>query</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Value</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳整棵樹的區間Value</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>query</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">first</span> ,<br>
+Key const& <span class="monospaced">last</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Value</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">找出key介於 <span class="monospaced">first</span> <br>
+~ <span class="monospaced">last</span> 的區間Value</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>order</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">ord</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">將Elements依照Key由小到大排序, 回傳第 <span class="monospaced">ord</span> 個Element (由0算起).
+其中如果 <span class="monospaced">ord</span> > N - 1, 則會回傳 <span class="monospaced">this->last()</span></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>first</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">ord</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳Key最小的Element, 如果SplayTree_Range為空, 則回傳 <span class="monospaced">this->end()</span></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>last</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">ord</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳Key最大的Element, 如果SplayTree_Range為空, 則回傳 <span class="monospaced">this->end()</span></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>end</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Element</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳一個指向NULL的Element, 以供 <span class="monospaced">find</span> , <span class="monospaced">order</span> , <span class="monospaced">first</span>
+, <span class="monospaced">last</span> 等判斷是否有找到相對應的Element</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>size</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">size_t</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳資料數</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>size</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">回傳是否為空</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>clear</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(N)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">清空資料</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>insert</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">key</span>,<br>
+Value const& <span class="monospaced">value</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">檢查是否已有Element的Key 為 <span class="monospaced">key</span>, 若有則回傳 <span class="monospaced">false</span> , 否則將
+一個 (Key → Value) = (<span class="monospaced">key</span> → <span class="monospaced">value</span>)的Element加入, 並回傳 <span class="monospaced">true</span>
+將所有Element的Key同加上 <span class="monospaced">delta</span></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>erase</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">key</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">檢查是否已有Element的Key 為 <span class="monospaced">key</span>, 若有則刪除之, 並回傳 <span class="monospaced">true</span>,
+否則則回傳 <span class="monospaced">false</span></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>keyOffset</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">delta</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">將所有Element的Key同加上 <span class="monospaced">delta</span></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>valueOffset</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Value const& <span class="monospaced">delta</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">將所有Element的value同加上 <span class="monospaced">delta</span></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>valueOverride</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Value const& <span class="monospaced">vaule</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">將所有Element的value同變成 <span class="monospaced">value</span></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>operator[]</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">key</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Value&</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">檢查是否已有Element的Key 為 <span class="monospaced">key</span>, 若有則回傳相對應的Value的Reference
+否則先執行 <span class="monospaced">insert(key, Value())</span> 再回傳相對應的Reference</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>splitOut</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Key const& <span class="monospaced">upper_bound</span>,<br>
+SplayTree_Range* <span class="monospaced">tree2</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN) + O(M)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">將 <span class="monospaced">tree2</span> 清空, 再將所有Key > <span class="monospaced">upper_bound</span> 的Element都丟到 <span class="monospaced">tree2</span></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>mergeAfter</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(SplayTree_Range* <span class="monospaced">tree2</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN) + O(logM)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">檢查是否 <span class="monospaced">this</span> 中的 Key 都小於 <span class="monospaced">tree2</span> 中的Key, 是的話把 <span class="monospaced">tree2</span>
+中的 Element 都搬到 <span class="monospaced">this</span> , 同時清空 <span class="monospaced">tree2</span> , 回傳 <span class="monospaced">true</span>. 否則
+回傳 <span class="monospaced">false</span></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>merge</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(SplayTree_Range* <span class="monospaced">tree2</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN) + O(logM)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">檢查是否 <span class="monospaced">this</span> 中的 Key 都小於 <span class="monospaced">tree2</span> 中的Key 或者
+是否 <span class="monospaced">this</span> 中的 Key 都大於 <span class="monospaced">tree2</span> 中的Key, 是的話把 <span class="monospaced">tree2</span>
+中的 Element 都搬到 <span class="monospaced">this</span> , 同時清空 <span class="monospaced">tree2</span> , 回傳 <span class="monospaced">true</span>. 否則
+回傳 <span class="monospaced">false</span></p></td>
+</tr>
+</tbody>
+</table>
+<div class="admonitionblock">
+<table><tr>
+<td class="icon">
+<div class="title">Note</div>
+</td>
+<td class="content">
+<div class="ulist"><ul>
+<li>
+<p>
+假設現在有兩個SplayTree_Range <span class="monospaced">A</span> 和 <span class="monospaced">B</span>, 則:
+</p>
+<div class="ulist"><ul>
+<li>
+<p>
+執行 <span class="monospaced">B.moveTo(&A)</span> 後 <span class="monospaced">B</span> 會變成空的, <span class="monospaced">A</span> 原本擁有的資料也會覆蓋掉
+</p>
+</li>
+<li>
+<p>
+執行 <span class="monospaced">A.merge(&B)</span> 或 <span class="monospaced">A.mergeAfter(&B)</span> 後
+如果檢查發現確實可以merge, 則之後 <span class="monospaced">B</span> 會變成空的
+</p>
+</li>
+</ul></div>
+</li>
+</ul></div>
+</td>
+</tr></table>
+</div>
+<hr>
+</div>
+</div>
+<div class="sect2">
+<h3 id="_meow_strong_binaryindextree_lt_value_gt_strong_c_class">meow:: <strong>BinaryIndexTree<Value></strong> (C++ class)</h3>
+<div class="sect3">
+<h4 id="_description_11">Description</h4>
+<div class="paragraph"><p>極度簡化版的 <span class="monospaced">SegmentTree</span> 已無法區間操作, 區間詢問的區間開頭也一定要
+在 <span class="monospaced">index=0</span> 的地方</p></div>
+</div>
+<div class="sect3">
+<h4 id="_template_class_operators_request_7">Template Class Operators Request</h4>
+<table class="tableblock frame-all grid-rows"
+style="
+width:70%;
+">
+<col style="width:3%;">
+<col style="width:3%;">
+<col style="width:10%;">
+<col style="width:17%;">
+<col style="width:10%;">
+<col style="width:53%;">
+<thead>
+<tr>
+<th class="tableblock halign-right valign-top" >Const?</th>
+<th class="tableblock halign-left valign-top" >Typename</th>
+<th class="tableblock halign-left valign-top" > Operator </th>
+<th class="tableblock halign-left valign-top" > Parameters </th>
+<th class="tableblock halign-left valign-top" > Return_Type</th>
+<th class="tableblock halign-left valign-top" > Description</th>
+</tr>
+</thead>
+<tbody>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Value</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator+</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Value <span class="monospaced">n</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Value</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">合併用(類似
+<span class="monospaced">SegmentTree</span> 的
+operator| )</p></td>
+</tr>
+</tbody>
+</table>
+</div>
+<div class="sect3">
+<h4 id="_support_methods_8">Support Methods</h4>
+<div class="ulist"><ul>
+<li>
+<p>
+N ← <span class="monospaced">this</span> 中擁有的資料數
+</p>
+</li>
+</ul></div>
+<table class="tableblock frame-all grid-rows"
+style="
+width:100%;
+">
+<col style="width:2%;">
+<col style="width:8%;">
+<col style="width:18%;">
+<col style="width:8%;">
+<col style="width:8%;">
+<col style="width:54%;">
+<thead>
+<tr>
+<th class="tableblock halign-right valign-top" >Const?</th>
+<th class="tableblock halign-right valign-top" >Name </th>
+<th class="tableblock halign-left valign-top" > Parameters </th>
+<th class="tableblock halign-left valign-top" > Return_Type</th>
+<th class="tableblock halign-center valign-top" > Time_Complexity</th>
+<th class="tableblock halign-left valign-top" > Description</th>
+</tr>
+</thead>
+<tbody>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>reset</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">size</span>, Value const& <span class="monospaced">value</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(<span class="monospaced">size</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">將資料長度刷成 <span class="monospaced">N = size</span> 且每一個元素都是 <span class="monospaced">value</span></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>update</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">index</span>, Value const& <span class="monospaced">value</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">將第 <span class="monospaced">index</span> (從零開始算) 多加上 <span class="monospaced">value</span></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>query</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">index</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">詢問 <span class="monospaced">0~index</span> 的區間值</p></td>
+</tr>
+</tbody>
+</table>
+<div class="admonitionblock">
+<table><tr>
+<td class="icon">
+<div class="title">Note</div>
+</td>
+<td class="content">
+<div class="ulist"><ul>
+<li>
+<p>
+一般來說只能用在維護區間總和, 維護區間最大值只有在特殊情況才可以, 即
+<em>針對每個元素, 每次 update() 的值一定會大於等於原本的值</em>
+</p>
+</li>
+<li>
+<p>
+若要用區間最大值 , 則 <span class="monospaced">Value</span> 的 <span class="monospaced">operator+</span> 要寫成 <span class="monospaced">std::max(...)</span>
+</p>
+</li>
+</ul></div>
+</td>
+</tr></table>
+</div>
+<hr>
+</div>
+</div>
</div>
</div>
<div class="sect1">
@@ -2443,6 +2945,24 @@ width:70%; <td class="tableblock halign-left valign-top" ><p class="tableblock">0.516</p></td>
<td class="tableblock halign-center valign-top" ><p class="tableblock monospaced"><a href="http://codepad.org/03dW6ZHV">codepad</a></p></td>
</tr>
+<tr>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>SplayTree + SegmentTree</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><em>Shuffling_cards</em></p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock"><a href="http://acm.csie.org/ntujudge/problem.php?id=1353">NTU-OJ</a>
+<a href="http://www.spoj.com/problems/SHUFFLEK/">SPOJ</a></p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">Accept/TLE</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">6.910/---</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock monospaced"><a href="http://codepad.org/yUeiVZc0">codepad</a></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>SplayTree + BinaryIndexTree</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><em>Shuffling_cards</em></p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock"><a href="http://acm.csie.org/ntujudge/problem.php?id=1353">NTU-OJ</a>
+<a href="http://www.spoj.com/problems/SHUFFLEK/">SPOJ</a></p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">Accept/Accept</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">5.480/44.35</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock monospaced"><a href="http://codepad.org/GAWjEtmq">codepad</a></p></td>
+</tr>
</tbody>
</table>
</div>
@@ -2464,7 +2984,7 @@ E-Mail: cat.hook31894 ~在~ gmail.com <div id="footnotes"><hr></div>
<div id="footer">
<div id="footer-text">
-Last updated 2014-04-24 01:34:02 CST
+Last updated 2014-04-25 01:51:40 CST
</div>
</div>
</body>
|