aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorcathook <b01902109@csie.ntu.edu.tw>2014-04-25 01:53:47 +0800
committercathook <b01902109@csie.ntu.edu.tw>2014-04-25 01:53:47 +0800
commit04e55aa4560f597373ca58c29f57fe6c98d11a50 (patch)
treed9782d703266e0962d6c34de0c1faf043474be1b
parent77038a76911ecbb32931a51e2ac8eb9d32cc13da (diff)
downloadmeow-04e55aa4560f597373ca58c29f57fe6c98d11a50.tar
meow-04e55aa4560f597373ca58c29f57fe6c98d11a50.tar.gz
meow-04e55aa4560f597373ca58c29f57fe6c98d11a50.tar.bz2
meow-04e55aa4560f597373ca58c29f57fe6c98d11a50.tar.lz
meow-04e55aa4560f597373ca58c29f57fe6c98d11a50.tar.xz
meow-04e55aa4560f597373ca58c29f57fe6c98d11a50.tar.zst
meow-04e55aa4560f597373ca58c29f57fe6c98d11a50.zip
add BIT
Diffstat
-rw-r--r--Makefile2
-rw-r--r--README.asciidoc164
-rw-r--r--README.html538
-rw-r--r--_test/meowpp.cpp92
-rw-r--r--_test/meowpp.h64
-rw-r--r--_test/meowpp_BinaryIndexTree.cpp54
-rw-r--r--_test/meowpp_Colors.cpp124
-rw-r--r--_test/meowpp_DisjointSet.cpp79
-rw-r--r--_test/meowpp_KD_Tree.cpp186
-rw-r--r--_test/meowpp_MergeableHeap.cpp71
-rw-r--r--_test/meowpp_SegmentTree.cpp154
-rw-r--r--_test/meowpp_SplayTree.cpp503
-rw-r--r--footer.asciidoc12
-rw-r--r--meowpp/dsa/BinaryIndexTree.h69
-rw-r--r--meowpp/dsa/BinaryIndexTree.hpp44
-rw-r--r--meowpp/dsa/SplayTree.h52
-rw-r--r--meowpp/dsa/SplayTree.hpp467
17 files changed, 2357 insertions, 318 deletions
diff --git a/Makefile b/Makefile
index 1bb75c5..ffb91b5 100644
--- a/Makefile
+++ b/Makefile
@@ -25,8 +25,10 @@ $(TEST)/meowpp: $(TEST)/meowpp.o \
$(TEST)/meowpp_DisjointSet.o \
$(TEST)/meowpp_KD_Tree.o \
$(TEST)/meowpp_SegmentTree.o \
+ $(TEST)/meowpp_BinaryIndexTree.o \
$(TEST)/meowpp_MergeableHeap.o \
$(TEST)/meowpp_SplayTree.o \
+ $(TEST)/meowpp_SplayTree_Range.o \
$(TEST)/meowpp_VP_Tree.o \
$(CXX) -o $@ $(CXXFLAGS) $^
diff --git a/README.asciidoc b/README.asciidoc
index 1d25b02..3617440 100644
--- a/README.asciidoc
+++ b/README.asciidoc
@@ -456,8 +456,6 @@ bool `cmp`)|Vectors
|const|size|()|size_t|O(1)| 回傳資料數
|const|size|()|bool|O(1)| 回傳是否為空
||clear|()|void|O(N)| 清空資料
-||keyOffset|(Key const& `delta`)|void|O(1)
-|將所有Element的Key同加上 `delta`
||insert|(Key const& `key`, +
Value const& `value`)|bool|O(logN)
|檢查是否已有Element的Key 為 `key`, 若有則回傳 `false` , 否則將
@@ -466,6 +464,8 @@ Value const& `value`)|bool|O(logN)
||erase|(Key const& `key`)|bool|O(logN)
|檢查是否已有Element的Key 為 `key`, 若有則刪除之, 並回傳 `true`,
否則則回傳 `false`
+||keyOffset|(Key const& `delta`)|void|O(1)
+|將所有Element的Key同加上 `delta`
||operator[]|(Key const& `key`)|Value&|O(logN)
|檢查是否已有Element的Key 為 `key`, 若有則回傳相對應的Value的Reference
否則先執行 `insert(key, Value())` 再回傳相對應的Reference
@@ -546,6 +546,154 @@ Value const& `delta`)
'''
+=== meow:: *SplayTree_Range<Key, Value>* (C++ class)
+==== Description
+`SplayTree_Range` 是一種神乎其技的資料結構, 維護一堆 Key->Value. 並且支援
+一些 `std::map` 難以快速實踐的操作, 如 `split` , `merge` , `keyOffset`
+
+==== Template Class Operators Request
+[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"]
+|=====================================================================
+|Const?|Typename| Operator| Parameters | Return_Type| Description
+|const |Key |operator+|(Key `k`) | Key | 相加
+|const |Key |operator<|(Key `k`) | bool | 大小比較
+| |Key |'Key' |(int `n`) | | 建構子, `n` 永遠是0
+| |Value | 'Value' |( ) | | 建構子
+|=====================================================================
+
+==== Custom Type Definitions
+
+* `Element` -> 用來當作回傳資料的媒介
+** 重定義 `operator->()` 到 `std::pair<Key const&, Value&>*`
+** 重定義 `operator*()` 到 `std::pair<Key const&, Value&>&`
+** 有 `operator==` , `operator!=`, `operator=` 可用
+** 可以直接用 `(*e).second = some_value` 來改變SplayTree_Range中的資料
+
+==== Support Methods
+
+* N <- `this` 中擁有的資料數
+* M <- `tree2` 中擁有的資料數
+
+[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"]
+|=====================================================================
+|Const?|Name | Parameters | Return_Type| Time_Complexity| Description
+||moveTo|(SplayTree_Range* `tree2`)|void|O(M)
+|將 `this` 的資料複寫到 `tree2` 上面, 同時清空自己,
+時間複雜度中的M是 `tree2` 所擁有的資料數
+|const|lowerBound|(Key const& `k`)|Element|O(logN)
+|找出第一個(最小的) Element且 `k` <= 它的 Key, 並且回傳之.
+找不到的話回傳 `this->end()`
+|const|lowerBound|(Key const& `k`)|Element|O(logN)
+|找出第一個(最小的) Element且 `k` < 它的 Key, 並且回傳之.
+找不到的話回傳 `this->end()`
+|const|lowerBound|(Key const& `k`)|Element|O(logN)
+|找出第一個(最小的) Element且 `k` >= 它的 Key, 並且回傳之.
+找不到的話回傳 `this->end()`
+|const|lowerBound|(Key const& `k`)|Element|O(logN)
+|找出第一個(最小的) Element且 `k` > 它的 Key, 並且回傳之.
+找不到的話回傳 `this->end()`
+|const|find|(Key const& `k`)|Element|O(logN)
+|找出 Key= `k` 的Elemenet 並回傳. 找不到的話回傳 `this->end()`
+|const|query|()|Value|O(1)
+|回傳整棵樹的區間Value
+|const|query|(Key const& `first` , +
+Key const& `last`)|Value|O(logN)
+|找出key介於 `first` +
+~ `last` 的區間Value
+|const|order|(size_t `ord`)|Element|O(logN)
+|將Elements依照Key由小到大排序, 回傳第 `ord` 個Element (由0算起).
+其中如果 `ord` > N - 1, 則會回傳 `this->last()`
+|const|first|(size_t `ord`)|Element|O(logN)
+|回傳Key最小的Element, 如果SplayTree_Range為空, 則回傳 `this->end()`
+|const|last|(size_t `ord`)|Element|O(logN)
+|回傳Key最大的Element, 如果SplayTree_Range為空, 則回傳 `this->end()`
+|const|end|()|Element|O(1)
+|回傳一個指向NULL的Element, 以供 `find` , `order` , `first`
+, `last` 等判斷是否有找到相對應的Element
+|const|size|()|size_t|O(1)| 回傳資料數
+|const|size|()|bool|O(1)| 回傳是否為空
+||clear|()|void|O(N)| 清空資料
+||insert|(Key const& `key`, +
+Value const& `value`)|bool|O(logN)
+|檢查是否已有Element的Key 為 `key`, 若有則回傳 `false` , 否則將
+一個 (Key -> Value) = (`key` -> `value`)的Element加入, 並回傳 `true`
+將所有Element的Key同加上 `delta`
+||erase|(Key const& `key`)|bool|O(logN)
+|檢查是否已有Element的Key 為 `key`, 若有則刪除之, 並回傳 `true`,
+否則則回傳 `false`
+||keyOffset|(Key const& `delta`)|void|O(1)
+|將所有Element的Key同加上 `delta`
+||valueOffset|(Value const& `delta`)|void|O(1)
+|將所有Element的value同加上 `delta`
+||valueOverride|(Value const& `vaule`)|void|O(1)
+|將所有Element的value同變成 `value`
+||operator[]|(Key const& `key`)|Value&|O(logN)
+|檢查是否已有Element的Key 為 `key`, 若有則回傳相對應的Value的Reference
+否則先執行 `insert(key, Value())` 再回傳相對應的Reference
+||splitOut|(Key const& `upper_bound`, +
+SplayTree_Range* `tree2`)|void
+|O(logN) + O(M)
+|將 `tree2` 清空, 再將所有Key > `upper_bound` 的Element都丟到 `tree2`
+||mergeAfter|(SplayTree_Range* `tree2`)|void|O(logN) + O(logM)
+|檢查是否 `this` 中的 Key 都小於 `tree2` 中的Key, 是的話把 `tree2`
+中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則
+回傳 `false`
+||merge|(SplayTree_Range* `tree2`)|void|O(logN) + O(logM)
+|檢查是否 `this` 中的 Key 都小於 `tree2` 中的Key 或者
+是否 `this` 中的 Key 都大於 `tree2` 中的Key, 是的話把 `tree2`
+中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則
+回傳 `false`
+|=====================================================================
+
+[NOTE]
+========================================
+* 假設現在有兩個SplayTree_Range `A` 和 `B`, 則:
+** 執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉
+** 執行 `A.merge(&B)` 或 `A.mergeAfter(&B)` 後
+如果檢查發現確實可以merge, 則之後 `B` 會變成空的
+========================================
+
+'''
+
+
+=== meow:: *BinaryIndexTree<Value>* (C++ class)
+==== Description
+極度簡化版的 `SegmentTree` 已無法區間操作, 區間詢問的區間開頭也一定要
+在 `index=0` 的地方
+
+==== Template Class Operators Request
+[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"]
+|=====================================================================
+|Const?|Typename| Operator | Parameters | Return_Type| Description
+|const | Value | operator+ |(Value `n`) | Value | 合併用(類似
+`SegmentTree` 的
+operator{b} )
+|=====================================================================
+
+==== Support Methods
+
+* N <- `this` 中擁有的資料數
+
+[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"]
+|=====================================================================
+|Const?|Name | Parameters | Return_Type| Time_Complexity| Description
+||reset|(size_t `size`, Value const& `value`)|void|O(`size`)
+|將資料長度刷成 `N = size` 且每一個元素都是 `value`
+||update|(size_t `index`, Value const& `value`)|void|O(logN)
+|將第 `index` (從零開始算) 多加上 `value`
+|const|query|(size_t `index`)|void|O(logN)
+|詢問 `0~index` 的區間值
+|=====================================================================
+
+[NOTE]
+========================================
+* 一般來說只能用在維護區間總和, 維護區間最大值只有在特殊情況才可以, 即
+'針對每個元素, 每次 update() 的值一定會大於等於原本的值'
+* 若要用區間最大值 , 則 `Value` 的 `operator+` 要寫成 `std::max(...)`
+========================================
+
+'''
+
== Test
=== ACM 相關題目
[options="header",width="70%",cols="3<s,3<,4^,1^,1<,2^m",grid="rows"]
@@ -563,6 +711,18 @@ https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&pag
| Accept | 0.516 | http://codepad.org/03dW6ZHV[codepad]
+| SplayTree + SegmentTree | 'Shuffling_cards' |
+http://acm.csie.org/ntujudge/problem.php?id=1353[NTU-OJ]
+http://www.spoj.com/problems/SHUFFLEK/[SPOJ]
+| Accept/TLE | 6.910/--- | http://codepad.org/yUeiVZc0[codepad]
+
+| SplayTree + BinaryIndexTree | 'Shuffling_cards' |
+http://acm.csie.org/ntujudge/problem.php?id=1353[NTU-OJ]
+http://www.spoj.com/problems/SHUFFLEK/[SPOJ]
+|Accept/Accept|5.480/44.35| http://codepad.org/GAWjEtmq[codepad]
+
+
+
|=======================================================================
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&amp; <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&amp; <span class="monospaced">key</span>,<br>
Value const&amp; <span class="monospaced">value</span>)</p></td>
@@ -2150,6 +2142,14 @@ Value const&amp; <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&amp; <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&amp; <span class="monospaced">key</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Value&amp;</p></td>
@@ -2397,6 +2397,508 @@ Value const&amp; <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&lt;Key, Value&gt;</strong> (C++ class)</h3>
+<div class="sect3">
+<h4 id="_description_10">Description</h4>
+<div class="paragraph"><p><span class="monospaced">SplayTree_Range</span> 是一種神乎其技的資料結構, 維護一堆 Key&#8594;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&lt;</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> &#8594; 用來當作回傳資料的媒介
+</p>
+<div class="ulist"><ul>
+<li>
+<p>
+重定義 <span class="monospaced">operator-&gt;()</span> 到 <span class="monospaced">std::pair&lt;Key const&amp;, Value&amp;&gt;*</span>
+</p>
+</li>
+<li>
+<p>
+重定義 <span class="monospaced">operator*()</span> 到 <span class="monospaced">std::pair&lt;Key const&amp;, Value&amp;&gt;&amp;</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 &#8592; <span class="monospaced">this</span> 中擁有的資料數
+</p>
+</li>
+<li>
+<p>
+M &#8592; <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&amp; <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> &#8656; 它的 Key, 並且回傳之.
+找不到的話回傳 <span class="monospaced">this-&gt;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&amp; <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> &lt; 它的 Key, 並且回傳之.
+找不到的話回傳 <span class="monospaced">this-&gt;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&amp; <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> &gt;= 它的 Key, 並且回傳之.
+找不到的話回傳 <span class="monospaced">this-&gt;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&amp; <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> &gt; 它的 Key, 並且回傳之.
+找不到的話回傳 <span class="monospaced">this-&gt;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&amp; <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-&gt;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&amp; <span class="monospaced">first</span> ,<br>
+Key const&amp; <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> &gt; N - 1, 則會回傳 <span class="monospaced">this-&gt;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-&gt;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-&gt;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&amp; <span class="monospaced">key</span>,<br>
+Value const&amp; <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 &#8594; Value) = (<span class="monospaced">key</span> &#8594; <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&amp; <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&amp; <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&amp; <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&amp; <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&amp; <span class="monospaced">key</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Value&amp;</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&amp; <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 &gt; <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(&amp;A)</span> 後 <span class="monospaced">B</span> 會變成空的, <span class="monospaced">A</span> 原本擁有的資料也會覆蓋掉
+</p>
+</li>
+<li>
+<p>
+執行 <span class="monospaced">A.merge(&amp;B)</span> 或 <span class="monospaced">A.mergeAfter(&amp;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&lt;Value&gt;</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 &#8592; <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&amp; <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&amp; <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>
diff --git a/_test/meowpp.cpp b/_test/meowpp.cpp
index e03edaa..805f459 100644
--- a/_test/meowpp.cpp
+++ b/_test/meowpp.cpp
@@ -1,32 +1,72 @@
-#include "dsa/KD_Tree.h"
-#include "Usage.h"
+#include "meowpp.h"
-bool testColors(){
-}
-bool testDisjointSet(){
-}
-bool testMergeableHeap(){
-}
+#include <string>
+#include <cstdlib>
+#include <ctime>
+
+////////////////////////////
+meow::Usage usg("meowpp"), usg2;
+int count = 0;
+TestFunctions tests;
+////////////////////////
int main(int argc, char** argv){
- Usage usg("meowpp"), usg2;
- usg .addOption('h', "Display this help document");
- usg2.addOption('t',
- "Test the i-th part of the meowpp and then quit",
- "<number>", "",
- false);
+ //srand(time(NULL));
+ usg.addOption('h', "Display this help document");
+ usg.addUsageBegin("<name> is a little test program to check whether"
+ "the data structures in the template is correct by"
+ "random generate lots of data to test");
+ usg.addUsageEnd ("zzzzzzzzzzzzzzz....");
+ usg.import(usg2);
- KD_Tree();
- KD_Tree(size_t _dimension);
- ~KD_Tree();
- //
- void insert(Keys const& key, Value value);
- void build();
- //
- Value query (Keys const& point, int k) const;
- Values rangeQuery(Keys const& point, int k) const;
- //
- void clear();
- void reset(size_t _dimension);
+ std::string err;
+ if(usg.setArguments(argc, argv, &err) == false){
+ printf("%s\n\n%s\n", err.c_str(), usg.getUsage().c_str());
+ return 1;
+ }else if(usg.hasOptionSetup('h')){
+ printf("%s", usg.getUsage().c_str());
+ return 0;
+ }else{
+ usg2.update(usg);
+ if(usg2.getOptionValuesCount('t') > 0){
+ for(int i = 0, I = usg2.getOptionValuesCount('t'); i < I; i++){
+ int id = atoi(usg2.getOptionValue('t', i).c_str());
+ TestFunction* f = (TestFunction*)tests.getImplement(id);
+ if(f->run() == false){
+ printf("error occure on %s\n", f->name().c_str());
+ return 1;
+ }else{
+ printf("%s success\n", f->name().c_str());
+ }
+ }
+ }else{
+ std::vector<int> ids = tests.getIdentifys();
+ while(true){
+ for(int i = 0, I = ids.size(); i < I; i++){
+ TestFunction* f = (TestFunction*)tests.getImplement(i);
+ printf(" %d) %s\n", ids[i], f->name().c_str());
+ }
+ printf("please select(EOF to quit): ");
+ int id;
+ if(!~scanf("%d", &id)){
+ break;
+ }
+ printf("\n");
+ TestFunction* f = (TestFunction*)tests.getImplement(id);
+ if(f == NULL){
+ printf("Bad value!\n\n");
+ continue;
+ }
+ if(f->run() == false){
+ printf("error occure on %s\n\n", f->name().c_str());
+ return 1;
+ }else{
+ printf("%s success\n\n", f->name().c_str());
+ }
+ }
+ printf("\n");
+ }
+ return 0;
+ }
return 0;
}
diff --git a/_test/meowpp.h b/_test/meowpp.h
new file mode 100644
index 0000000..ca6c224
--- /dev/null
+++ b/_test/meowpp.h
@@ -0,0 +1,64 @@
+#ifndef __meowpp_h__
+#define __meowpp_h__
+
+#include "Usage.h"
+#include "utility.h"
+#include "colors/RGB.h"
+#include "colors/YUV.h"
+#include "colors/HSL.h"
+#include "colors/HSV.h"
+#include "dsa/DisjointSet.h"
+#include "dsa/KD_Tree.h"
+#include "dsa/VP_Tree.h"
+#include "dsa/SegmentTree.h"
+#include "dsa/BinaryIndexTree.h"
+#include "dsa/MergeableHeap.h"
+#include "dsa/SplayTree.h"
+#include "dsa/SplayTree_Range.h"
+#include "oo/Register_Implement.h"
+
+extern meow::Usage usg, usg2;
+extern int count;
+//////////////////////////////////
+class TestFunctions: public meow::RegisterInterface<int>{
+ public:
+ TestFunctions(): RegisterInterface(){
+ usg2.addOption('t',
+ "Specify which part of the template to test",
+ "name", "",
+ false);
+ }
+ bool regImplement(meow::ImplementInterface<int>* imp,
+ std::string const& str){
+ usg2.addOptionValueAccept('t',
+ meow::stringPrintf("%d", imp->identify()),
+ str);
+ return RegisterInterface::regImplement(imp);
+ }
+};
+extern TestFunctions tests;
+////////////////////////
+class TestFunction: public meow::ImplementInterface<int>{
+ private:
+ std::string _name;
+ public:
+ TestFunction(std::string const& __name):
+ ImplementInterface(count++), _name("testing code about " + __name){
+ tests.regImplement(this, _name);
+ }
+ virtual ~TestFunction(){ }
+ virtual bool run() = 0;
+ std::string name() const{ return _name; }
+};
+////////////////////////
+
+#define concat(a,b) a##b
+#define TEST(a) \
+class Test_##a: public TestFunction{ \
+ public: \
+ Test_##a(): TestFunction(#a){ } \
+ bool run();\
+} __test_##a; bool Test_##a::run()
+
+
+#endif // meowpp_h__
diff --git a/_test/meowpp_BinaryIndexTree.cpp b/_test/meowpp_BinaryIndexTree.cpp
new file mode 100644
index 0000000..3841a84
--- /dev/null
+++ b/_test/meowpp_BinaryIndexTree.cpp
@@ -0,0 +1,54 @@
+#include "meowpp.h"
+
+#include <vector>
+
+static int N = 100000;
+
+static std::vector<int> array;
+
+inline int sum(int k){
+ int x = 0;
+ for(int i = 0; i <= k; i++){
+ x += array[i];
+ }
+ return x;
+}
+
+static meow::BinaryIndexTree<int> bit;
+
+TEST(BinaryIndexTree){
+ size_t tMe = 0, tBi = 0, t0;
+ for(int z = 0; z < 10; z++){
+ meow::messagePrintf(1, "test %d", z);
+ bit.reset(N, 0);
+ array.clear();
+ array.resize(N, 0);
+
+ int NN = rand() % 10000;
+ for(int i = 0; i < NN; i++){
+ int index = rand() % N;
+ if(rand() & 1){
+ int val = rand() % 1000;
+ t0 = clock(); array[i] += val; tMe += clock() - t0;
+ t0 = clock(); bit.update(i, val); tBi += clock() - t0;
+ }else{
+ if(sum(index) != bit.query(index)){
+ meow::messagePrintf(-1, "range-sum query fail");
+ return false;
+ }
+ }
+ }
+ int s = 0;
+ for(int i = 0; i < N; i++){
+ s += array[i];
+ if(s != bit.query(i)){
+ meow::messagePrintf(-1, "range-sum query fail");
+ return false;
+ }
+ }
+ meow::messagePrintf(-1, "ok %.3f/%.3f",
+ tBi * 1.0 / CLOCKS_PER_SEC,
+ tMe * 1.0 / CLOCKS_PER_SEC);
+ }
+ return true;
+};
diff --git a/_test/meowpp_Colors.cpp b/_test/meowpp_Colors.cpp
new file mode 100644
index 0000000..847f838
--- /dev/null
+++ b/_test/meowpp_Colors.cpp
@@ -0,0 +1,124 @@
+#include "meowpp.h"
+
+TEST(Colors){
+ meow::RGBf rgb, rgb2;
+ meow::YUVf yuv, yuv2;
+ meow::HSLf hsl, hsl2;
+ meow::HSVf hsv, hsv2;
+ bool ok = true;
+ double eps;
+ eps = 1e-8;
+ meow::messagePrintf(1, "rgb ---> hsl ---> rgb ---> hsl (eps = %e)", eps);
+ for(int i = 0; ok && i < 100000; i++){
+ rgb.r(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.rMin(), rgb.rMax()));
+ rgb.g(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.gMin(), rgb.gMax()));
+ rgb.b(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.bMin(), rgb.bMax()));
+ meow::RGB_to_HSL(rgb , &hsl );
+ meow::HSL_to_RGB(hsl , &rgb2);
+ meow::RGB_to_HSL(rgb2, &hsl2);
+ if(meow::noEPS(rgb.r() - rgb2.r(), eps) != 0 ||
+ meow::noEPS(rgb.g() - rgb2.g(), eps) != 0 ||
+ meow::noEPS(rgb.b() - rgb2.b(), eps) != 0) ok = false;
+ if(meow::noEPS(hsl.h() - hsl2.h(), eps) != 0 ||
+ meow::noEPS(hsl.s() - hsl2.s(), eps) != 0 ||
+ meow::noEPS(hsl.l() - hsl2.l(), eps) != 0) ok = false;
+ }
+ if(ok) meow::messagePrintf(-1, "ok!");
+ else{ meow::messagePrintf(-1, "fail"); return false; }
+ //
+ eps = 1e-8;
+ meow::messagePrintf(1, "rgb ---> hsv ---> rgb ---> hsv (eps = %e)", eps);
+ for(int i = 0; ok && i < 100000; i++){
+ rgb.r(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.rMin(), rgb.rMax()));
+ rgb.g(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.gMin(), rgb.gMax()));
+ rgb.b(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.bMin(), rgb.bMax()));
+ meow::RGB_to_HSV(rgb , &hsv );
+ meow::HSV_to_RGB(hsv , &rgb2);
+ meow::RGB_to_HSV(rgb2, &hsv2);
+ if(meow::noEPS(rgb.r() - rgb2.r(), eps) != 0 ||
+ meow::noEPS(rgb.g() - rgb2.g(), eps) != 0 ||
+ meow::noEPS(rgb.b() - rgb2.b(), eps) != 0) ok = false;
+ if(meow::noEPS(hsv.h() - hsv2.h(), eps) != 0 ||
+ meow::noEPS(hsv.s() - hsv2.s(), eps) != 0 ||
+ meow::noEPS(hsv.v() - hsv2.v(), eps) != 0) ok = false;
+ }
+ if(ok) meow::messagePrintf(-1, "ok!");
+ else{ meow::messagePrintf(-1, "fail"); return false; }
+ //
+ /*
+ eps = 1e-3;
+ meow::messagePrintf(1, "yuv ---> hsl ---> yuv ---> hsl");
+ for(int i = 0; ok && i < 100000; i++){
+ yuv.y(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.yMin(), yuv.yMax()));
+ yuv.u(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.uMin(), yuv.uMax()));
+ yuv.v(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.vMin(), yuv.vMax()));
+ meow::YUV_to_HSL(yuv , &hsl );
+ meow::HSL_to_YUV(hsl , &yuv2);
+ meow::YUV_to_HSL(yuv2, &hsl2);
+ if(meow::noEPS(yuv.y() - yuv2.y(), eps) != 0 ||
+ meow::noEPS(yuv.u() - yuv2.u(), eps) != 0 ||
+ meow::noEPS(yuv.v() - yuv2.v(), eps) != 0) ok = false;
+ if(meow::noEPS(hsl.h() - hsl2.h(), eps) != 0 ||
+ meow::noEPS(hsl.s() - hsl2.s(), eps) != 0 ||
+ meow::noEPS(hsl.l() - hsl2.l(), eps) != 0) ok = false;
+ }
+ if(ok) meow::messagePrintf(-1, "ok!");
+ else{ meow::messagePrintf(-1, "fail"); return false; }
+ // */
+ /*
+ meow::messagePrintf(1, "yuv ---> hsv ---> yuv ---> hsv");
+ for(int i = 0; ok && i < 100000; i++){
+ yuv.y(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.yMin(), yuv.yMax()));
+ yuv.u(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.uMin(), yuv.uMax()));
+ yuv.v(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.vMin(), yuv.vMax()));
+ meow::YUV_to_HSV(yuv , &hsv );
+ meow::HSV_to_YUV(hsv , &yuv2);
+ meow::YUV_to_HSV(yuv2, &hsv2);
+ if(meow::noEPS(yuv.y() - yuv2.y(), eps) != 0 ||
+ meow::noEPS(yuv.u() - yuv2.u(), eps) != 0 ||
+ meow::noEPS(yuv.v() - yuv2.v(), eps) != 0) ok = false;
+ if(meow::noEPS(hsv.h() - hsv2.h(), eps) != 0 ||
+ meow::noEPS(hsv.s() - hsv2.s(), eps) != 0 ||
+ meow::noEPS(hsv.v() - hsv2.v(), eps) != 0) ok = false;
+ }
+ if(ok) meow::messagePrintf(-1, "ok!");
+ else{ meow::messagePrintf(-1, "fail"); return false; }
+ // */
+ eps = 1e-3;
+ meow::messagePrintf(1, "rgb ---> yuv ---> rgb ---> yuv (eps = %e)", eps);
+ for(int i = 0; ok && i < 100000; i++){
+ rgb.r(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.rMin(), rgb.rMax()));
+ rgb.g(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.gMin(), rgb.gMax()));
+ rgb.b(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.bMin(), rgb.bMax()));
+ meow::RGB_to_YUV(rgb , &yuv );
+ meow::YUV_to_RGB(yuv , &rgb2);
+ meow::RGB_to_YUV(rgb2, &yuv2);
+ if(meow::noEPS(rgb.r() - rgb2.r(), eps) != 0 ||
+ meow::noEPS(rgb.g() - rgb2.g(), eps) != 0 ||
+ meow::noEPS(rgb.b() - rgb2.b(), eps) != 0) ok = false;
+ if(meow::noEPS(yuv.y() - yuv2.y(), eps) != 0 ||
+ meow::noEPS(yuv.u() - yuv2.u(), eps) != 0 ||
+ meow::noEPS(yuv.v() - yuv2.v(), eps) != 0) ok = false;
+ }
+ if(ok) meow::messagePrintf(-1, "ok!");
+ else{ meow::messagePrintf(-1, "fail"); return false; }
+ eps = 1e-8;
+ meow::messagePrintf(1, "hsl ---> hsv ---> hsl ---> hsv (eps = %e)", eps);
+ for(int i = 0; ok && i < 100000; i++){
+ hsl.h(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, hsl.hMin(), hsl.hMax()));
+ hsl.s(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, hsl.sMin(), hsl.sMax()));
+ hsl.l(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, hsl.lMin(), hsl.lMax()));
+ meow::HSL_to_HSV(hsl , &hsv );
+ meow::HSV_to_HSL(hsv , &hsl2);
+ meow::HSL_to_HSV(hsl2, &hsv2);
+ if(meow::noEPS(hsl.h() - hsl2.h(), eps) != 0 ||
+ meow::noEPS(hsl.s() - hsl2.s(), eps) != 0 ||
+ meow::noEPS(hsl.l() - hsl2.l(), eps) != 0) ok = false;
+ if(meow::noEPS(hsv.h() - hsv2.h(), eps) != 0 ||
+ meow::noEPS(hsv.s() - hsv2.s(), eps) != 0 ||
+ meow::noEPS(hsv.v() - hsv2.v(), eps) != 0) ok = false;
+ }
+ if(ok) meow::messagePrintf(-1, "ok!");
+ else{ meow::messagePrintf(-1, "fail"); return false; }
+ return true;
+};
diff --git a/_test/meowpp_DisjointSet.cpp b/_test/meowpp_DisjointSet.cpp
new file mode 100644
index 0000000..b871c4d
--- /dev/null
+++ b/_test/meowpp_DisjointSet.cpp
@@ -0,0 +1,79 @@
+#include "meowpp.h"
+
+#include <vector>
+
+TEST(DisjointSet){
+ int N = 10000000;
+ meow::DisjointSet dsj(N);
+
+ meow::messagePrintf(1, "merge(0, 1) merge(0, 2) merge(0, 3) ... (N = %d)", N);
+ for(int i = 1; i < N; i++){
+ dsj.merge(0, i);
+ }
+ int root = dsj.root(0);
+ for(int i = 1; i < N; i++){
+ if(root != dsj.root(i)){
+ meow::messagePrintf(-1, "fail");
+ return false;
+ }
+ }
+ meow::messagePrintf(-1, "ok");
+ //
+
+ dsj.reset(N);
+ meow::messagePrintf(1, "merge(0, 1) merge(1, 2) merge(2, 3) ... (N = %d)", N);
+ for(int i = 1; i < N; i++){
+ dsj.merge(i - 1, i);
+ }
+ root = dsj.root(0);
+ for(int i = 1; i < N; i++){
+ if(root != dsj.root(i)){
+ meow::messagePrintf(-1, "fail");
+ return false;
+ }
+ }
+ meow::messagePrintf(-1, "ok");
+ //
+
+ int M = 1000;
+ N = 1000000;
+ dsj.reset(N);
+ std::vector<int> used(N, -1);
+ std::vector<int> nums[M];
+
+ meow::messagePrintf(1, "random test (N = %d)", N);
+ for(int i = 0; i < N / 10; i++){
+ int grp = rand() % M;
+ int who;
+ while(used[who = rand() % N] != -1);
+ nums[grp].push_back(who);
+ used[who] = grp;
+ }
+ meow::messagePrintf(0, "data created");
+ for(int i = 0; i < M; i++){
+ for(int k = 0; k < 100; k++){
+ int j1 = rand() % nums[i].size();
+ int j2 = rand() % nums[i].size();
+ dsj.merge(nums[i][j1], nums[i][j2]);
+ }
+ for(size_t j = 1; j < nums[i].size(); j++){
+ dsj.merge(nums[i][0], nums[i][j]);
+ }
+ }
+ for(int i = 0; i < N; i++){
+ bool ok = false;
+ if(used[i] == -1 && dsj.root(i) == i){
+ ok = true;
+ }else{
+ if(dsj.root(i) == dsj.root(nums[used[i]][0])){
+ ok = true;
+ }
+ }
+ if(!ok){
+ meow::messagePrintf(-1, "fail");
+ return false;
+ }
+ }
+ meow::messagePrintf(-1, "ok");
+ return true;
+};
diff --git a/_test/meowpp_KD_Tree.cpp b/_test/meowpp_KD_Tree.cpp
new file mode 100644
index 0000000..dcbda5f
--- /dev/null
+++ b/_test/meowpp_KD_Tree.cpp
@@ -0,0 +1,186 @@
+#include "meowpp.h"
+
+#include <vector>
+
+#include <cmath>
+#include <cstdlib>
+#include <algorithm>
+#include <ctime>
+#include <queue>
+
+static int N = 10000;
+static int D = 5;
+
+static double dist2(std::vector<double> const& v1, std::vector<double> const& v2){
+ double ret = 0;
+ for(int i = 0; i < D; i++){
+ ret += meow::squ(v1[i] - v2[i]);
+ }
+ return ret;
+}
+
+static std::vector< std::vector<double> > data;
+static std::vector< double > dist;
+static std::vector< int > order;
+
+
+struct Answer{
+ double dist;
+ int id;
+ Answer(double _dist, int _id): dist(_dist), id(_id){ }
+ bool operator<(Answer const& b) const{
+ if(dist != b.dist) return (dist < b.dist);
+ return (id < b.id);
+ }
+};
+
+
+static void find(std::vector<double> const& v, int k){
+ std::priority_queue<Answer> qu;
+ for(int i = 0; i < k; i++){
+ qu.push(Answer(dist2(v, data[i]), i));
+ }
+ for(int i = k; i < N; i++){
+ qu.push(Answer(dist2(v, data[i]), i));
+ qu.pop();
+ }
+ order.resize(k);
+ for(int i = qu.size() - 1; i >= 0; i--){
+ order[i] = qu.top().id;
+ qu.pop();
+ }
+}
+
+static std::vector<double> v;
+
+static bool sf(const int& a, const int& b){
+ if(dist[a] != dist[b])
+ return (dist[a] < dist[b]);
+ return (a < b);
+}
+
+static void show(std::vector<double> const& ask, std::vector<int> kd, std::vector<int> me, int k){
+ if(N <= 30 && D <= 3){
+ printf("\nData:\n");
+ for(int i = 0; i < N; i++){
+ printf(" %2d) <", i);
+ for(int j = 0; j < D; j++){
+ printf("%.7f", data[i][j]);
+ if(j < D - 1) printf(", ");
+ else printf(">");
+ }
+ printf("\n");
+ }
+ printf("Ask <");
+ for(int j = 0; j < D; j++){
+ printf("%.7f", ask[j]);
+ if(j < D - 1) printf(", ");
+ else printf(">");
+ }
+ printf("\n");
+ printf("MyAnswer: ");
+ for(int i = 0; i < k; i++) printf("%d ", me[i]);
+ printf("\n");
+ printf("KdAnswer: ");
+ for(int i = 0; i < k; i++) printf("%d ", kd[i]);
+ printf("\n");
+ order.resize(N);
+ dist .resize(N);
+ for(int i = 0; i < N; i++){
+ dist [i] = dist2(ask, data[i]);
+ order[i] = i;
+ }
+ std::sort(order.begin(), order.end(), sf);
+ printf("Sorted:\n");
+ for(int i = 0; i < N; i++){
+ printf(" %2d) <", order[i]);
+ for(int j = 0; j < D; j++){
+ printf("%.7f", data[order[i]][j]);
+ if(j < D - 1) printf(", ");
+ else printf(">");
+ }
+ printf(" ((%.7f))", dist[order[i]]);
+ printf("\n");
+ }
+ }
+}
+
+struct Node{
+ std::vector<double> v;
+ int id;
+ double& operator[](size_t d) { return v[d]; }
+ double operator[](size_t d) const { return v[d]; }
+ bool operator<(Node const& n) const{ return (id < n.id); }
+};
+
+TEST(KD_Tree){
+
+ int t0, t1, t2;
+
+ meow::KD_Tree<Node, double> tree(D);
+
+ meow::messagePrintf(1, "Create data (N = %d, D = %d)", N, D);
+ data.resize(N);
+ for(int i = 0; i < N; i++){
+ data[i].resize(D);
+ Node nd;
+ nd.v.resize(D);
+ nd.id = i;
+ for(int j = 0; j < D; j++){
+ data[i][j] = 12345.0 * (1.0 * rand() / RAND_MAX - 0.3);
+ nd[j] = data[i][j];
+ }
+ tree.insert(nd);
+ }
+ meow::messagePrintf(-1, "ok");
+ meow::messagePrintf(1, "build");
+ t0 = clock();
+ tree.build();
+ meow::messagePrintf(-1, "ok, %.3f seconds", (clock() - t0) * 1.0 / CLOCKS_PER_SEC);
+
+ meow::messagePrintf(1, "query...");
+ v.resize(D);
+ meow::KD_Tree<Node, double>::Vectors ret;
+ int id;
+ for(int k = 1; k <= std::min(100, N); k++){
+ meow::messagePrintf(1, "range k = %d", k);
+ t1 = t2 = 0;
+ for(int i = 0; i < 10; i++){
+ Node nd;
+ nd.v.resize(D);
+ for(int d = 0; d < D; d++){
+ v[d] = 12345.0 * (1.0 * rand() / RAND_MAX - 0.3);
+ nd[d] = v[d];
+ }
+ t0 = clock();
+ tree.build();
+ ret = tree.query(nd, k, true);
+ t1 += clock() - t0;
+
+ t0 = clock();
+ find(v, k);
+ t2 += clock() - t0;
+ if(ret.size() != std::min(k, N)){
+ meow::messagePrintf(-1, "(%d)query fail, size error", i);
+ meow::messagePrintf(-1, "fail");
+ return false;
+ }
+ for(int kk = 1; kk <= k; kk++){
+ if(order[kk - 1] != ret[kk - 1].id){
+ //show(v, ret, order, k);
+ meow::messagePrintf(-1, "(%d)query fail", i);
+ meow::messagePrintf(-1, "fail");
+ return false;
+ }
+ }
+ }
+ meow::messagePrintf(-1, "ok %.3f/%.3f",
+ t1 * 1.0 / CLOCKS_PER_SEC,
+ t2 * 1.0 / CLOCKS_PER_SEC
+ );
+ }
+ meow::messagePrintf(-1, "ok");
+
+
+ return true;
+};
diff --git a/_test/meowpp_MergeableHeap.cpp b/_test/meowpp_MergeableHeap.cpp
new file mode 100644
index 0000000..c4814da
--- /dev/null
+++ b/_test/meowpp_MergeableHeap.cpp
@@ -0,0 +1,71 @@
+#include "meowpp.h"
+
+#include <vector>
+#include <queue>
+#include <cstdlib>
+
+
+TEST(MergeableHeap){
+ int N = 10;
+ std::vector<std::priority_queue<int> > nhp;
+ std::vector<meow::MergeableHeap<int> > mhp;
+ for(int i = 0; i < 10; i++){
+ int MM = 5000 + rand() % 10000;
+ meow::messagePrintf(1, "%d-th test (M = %5d)", i, MM);
+ nhp.clear(); nhp.resize(N);
+ mhp.clear(); mhp.resize(N);
+ int tn = 0, tm = 0, t0;
+ for(int j = 0; j < MM; j++){
+ if((rand() & 3) == 0){
+ int a = rand() % N;
+ int num = rand();
+ t0 = clock(); nhp[a].push(num); tn += clock() - t0;
+ t0 = clock(); mhp[a].push(num); tm += clock() - t0;
+ }else if(rand() & 1){
+ int a = rand() % N;
+ t0 = clock();
+ if(!nhp[a].empty()) nhp[a].pop();
+ tn += clock() - t0;
+ t0 = clock();
+ if(!mhp[a].empty()) mhp[a].pop();
+ tm += clock() - t0;
+ }else{
+ int a = rand() % N, b = rand() % N;
+ if(b == a) b = (b + 1) % N;
+ t0 = clock();
+ for( ; !nhp[b].empty(); nhp[b].pop()){
+ nhp[a].push(nhp[b].top());
+ }
+ tn += clock() - t0;
+ t0 = clock();
+ mhp[a].merge(&mhp[b]);
+ tm += clock() - t0;
+ }
+ }
+ bool ok = true;
+ for(int j = 0; j < N; j++){
+ while(!nhp[j].empty() && !mhp[j].empty()){
+ if(nhp[j].top() != mhp[j].top()){
+ ok = false;
+ break;
+ }
+ nhp[j].pop();
+ mhp[j].pop();
+ }
+ if(mhp[j].empty() != nhp[j].empty()){
+ ok = false;
+ }
+ if(ok == false) break;
+ }
+ ok = true;
+ if(!ok){
+ meow::messagePrintf(-1, "fail");
+ return false;
+ }else{
+ meow::messagePrintf(-1, "ok %.3f/%.3f",
+ tm * 1.0 / CLOCKS_PER_SEC,
+ tn * 1.0 / CLOCKS_PER_SEC );
+ }
+ }
+ return true;
+};
diff --git a/_test/meowpp_SegmentTree.cpp b/_test/meowpp_SegmentTree.cpp
new file mode 100644
index 0000000..777ca9d
--- /dev/null
+++ b/_test/meowpp_SegmentTree.cpp
@@ -0,0 +1,154 @@
+#include "meowpp.h"
+
+#include <ctime>
+#include <algorithm>
+
+struct RangeMax{
+ int value;
+ //
+ RangeMax(){}
+ RangeMax(int _value): value(_value){ }
+ RangeMax(RangeMax const& b): value(b.value){ }
+ //
+ RangeMax operator*(size_t n) const{ return RangeMax(value); }
+ RangeMax operator|(RangeMax const& b) const{ return RangeMax(std::max(value, b.value)); }
+ RangeMax operator+(RangeMax const& b) const{ return RangeMax(b.value + value); }
+ bool operator==(RangeMax const& b) const{ return (value == b.value); }
+};
+struct RangeSum{
+ int value;
+ //
+ RangeSum(){}
+ RangeSum(int _value): value(_value){ }
+ RangeSum(RangeSum const& b): value(b.value){ }
+ //
+ RangeSum operator*(size_t n) const{ return RangeSum(n * value); }
+ RangeSum operator|(RangeSum const& b) const{ return RangeSum(value + b.value); }
+ RangeSum operator+(RangeSum const& b) const{ return RangeSum(b.value + value); }
+ bool operator==(RangeSum const& b) const{ return (value == b.value); }
+};
+
+meow::SegmentTree<RangeMax> s_max;
+meow::SegmentTree<RangeSum> s_sum;
+
+static int N = 1000000;
+
+std::vector<int> array;
+
+void override(int a, int b, int c){
+ for(int i = a; i <= b; i++)
+ array[i] = c;
+}
+void offset(int a, int b, int c){
+ for(int i = a; i <= b; i++)
+ array[i] += c;
+}
+int bmax(int a, int b){
+ int ret = array[a];
+ for(int i = a + 1; i <= b; i++)
+ ret = std::max(ret, array[i]);
+ return ret;
+}
+int bsum(int a, int b){
+ int sum = 0;
+ for(int i = a; i <= b; i++)
+ sum += array[i];
+ return sum;
+}
+
+void show(){
+ if(N <= 20){
+ printf("\n");
+ printf("Me : ");
+ for(int i = 0; i < N; i++){
+ printf("%4d ", array[i]);
+ }
+ printf("\n");
+ printf("Sum: ");
+ for(int i = 0; i < N; i++){
+ printf("%4d ", s_sum.query(i, i).value);
+ }
+ printf("\n");
+ printf("Max: ");
+ for(int i = 0; i < N; i++){
+ printf("%4d ", s_max.query(i, i).value);
+ }
+ printf("\n");
+ }
+}
+
+TEST(SegmentTree){
+ s_max.reset(N);
+ s_sum.reset(N);
+ s_max.override(0, N - 1, RangeMax(0));
+ s_sum.override(0, N - 1, RangeSum(0));
+ array.resize(N, 0);
+
+ for(int z = 0; z < 10; z++){
+ meow::messagePrintf(1, "test %d", z);
+ int tMe = 0, tSeg = 0, t0;
+ int NN = 1 + rand() % 100;
+ for(int i = 0; i < NN; i++){
+ int a = rand() % N;
+ int b = rand() % (N - a) + a;
+ int k = rand() % 20000 - 10000;
+ bool over = (rand() % 2 == 1);
+ if(over){
+ t0 = clock();
+ s_max.override(a, b, RangeMax(k));
+ s_sum.override(a, b, RangeSum(k));
+ tSeg += clock() - t0;
+ t0 = clock();
+ override(a, b, k);
+ tMe += clock() - t0;
+ }else{
+ t0 = clock();
+ s_max.offset(a, b, RangeMax(k));
+ s_sum.offset(a, b, RangeSum(k));
+ tSeg = clock() - t0;
+ t0 = clock();
+ offset(a, b, k);
+ tMe += clock() - t0;
+ }
+ /*
+ printf("\n");
+ printf("%s %d~%d with %d", over ? "override" : "offset", a, b, k);
+ show();
+ printf("max:"); s_max.print();
+ printf("sum:"); s_sum.print();
+ // */
+ }
+ NN = 1 + rand() % 100;
+ for(int i = 0; i < NN; i++){
+ int a = rand() % N;
+ int b = rand() % (N - a) + a;
+
+ t0 = clock();
+ RangeMax m(s_max.query(a, b));
+ RangeSum s(s_sum.query(a, b));
+ tSeg += clock() - t0;
+ t0 = clock();
+ int mm = bmax(a, b);
+ int ss = bsum(a, b);
+ tMe += clock() - t0;
+ if(m.value != mm){
+ printf("ask %d~%d, me %d/%d seg %d/%d\n", a, b, mm, ss, m.value, s.value);
+ meow::messagePrintf(-1, "range-max query fail");
+ return false;
+ }
+ if(s.value != ss){
+ printf("ask %d~%d, max/sum = me %d/%d seg %d/%d\n", a, b, mm, ss, m.value, s.value);
+ meow::messagePrintf(-1, "range-sum query fail");
+ return false;
+ }
+ }
+ meow::messagePrintf(-1, "ok, %.3f/%.3f",
+ 1.0 * tSeg / CLOCKS_PER_SEC,
+ 1.0 * tMe / CLOCKS_PER_SEC);
+ s_max.reset(N);
+ s_sum.reset(N);
+ array.clear();
+ array.resize(N, 0);
+ }
+ return true;
+};
diff --git a/_test/meowpp_SplayTree.cpp b/_test/meowpp_SplayTree.cpp
new file mode 100644
index 0000000..0d1e2f2
--- /dev/null
+++ b/_test/meowpp_SplayTree.cpp
@@ -0,0 +1,503 @@
+#include "meowpp.h"
+
+#include <algorithm>
+#include <utility>
+#include <map>
+#include <cstdlib>
+
+static int N;
+
+static bool detail_fg;
+
+typedef typename std::map <int, double>:: iterator IterN;
+typedef typename std::map <int, double>::reverse_iterator IterR;
+typedef typename meow::SplayTree<int, double>::Element IterS;
+
+static std::vector< std::map <int, double> > normal;
+static std::vector<meow::SplayTree<int, double> > splay;
+
+static void show(bool fg = false){
+ if(fg){
+ for(int i = 0; i < N; i++){
+ printf("normal %d-%lu: ", i, normal[i].size());
+ for(IterN it = normal[i].begin(); it != normal[i].end(); it++){
+ printf("%d/%.2f ", it->first, it->second);
+ }
+ printf("\n");
+ printf("splay %d-%lu: ", i, splay[i].size());
+ bool bye = false;
+ for(int j = 0; j < splay[i].size(); j++){
+ IterS it = splay[i].order(j);
+ printf("%d/%.2f ", it->first, it->second);
+ }
+ printf("\n");
+ }
+ printf("\n");
+ }
+}
+
+static bool lowerBound(int i, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= lowerBound(%d, %d)\n", i, key);
+ t0 = clock(); IterS b = splay [i].lowerBound (key); (*tS) += clock() - t0;
+ t0 = clock(); IterN a = normal[i].lower_bound(key); (*tN) += clock() - t0;
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (a == normal[i].end()) ? 0 : a->first,
+ (b == splay[i].end()) ? 0 : b->first,
+ (a == normal[i].end()) ? 0 : a->second,
+ (b == splay[i].end()) ? 0 : b->second);
+ show(detail_fg);
+ if((a == normal[i].end()) != (b == splay[i].end())) return false;
+ if( a == normal[i].end()) return true;
+ return (a->first == b->first && a->second == b->second);
+}
+static bool upperBound(int i, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= upperBound(%d, %d)\n", i, key);
+ t0 = clock(); IterS b = splay [i].upperBound (key); (*tS) += clock() - t0;
+ t0 = clock(); IterN a = normal[i].upper_bound(key); (*tN) += clock() - t0;
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (a == normal[i].end()) ? 0 : a->first,
+ (b == splay [i].end()) ? 0 : b->first,
+ (a == normal[i].end()) ? 0 : a->second,
+ (b == splay [i].end()) ? 0 : b->second);
+ show(detail_fg);
+ if((a == normal[i].end()) != (b == splay[i].end())) return false;
+ if( a == normal[i].end()) return true;
+ return (a->first == b->first && a->second == b->second);
+}
+static bool rLowerBound(int i, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= rLowerBound(%d, %d)\n", i, key);
+ t0 = clock(); IterS b = splay [i].rLowerBound(key); (*tS) += clock() - t0;
+ t0 = clock();
+ IterN a, z;
+ if(normal[i].size() == 0 || normal[i].begin()->first > key){
+ a = normal[i].end();
+ }else{
+ for(a = normal[i].begin(), z = a, z++; z != normal[i].end(); z++, a++){
+ if(z->first > key){
+ break;
+ }
+ }
+ }
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (a == normal[i].end()) ? 0 : a->first,
+ (b == splay[i].end()) ? 0 : b->first,
+ (a == normal[i].end()) ? 0 : a->second,
+ (b == splay[i].end()) ? 0 : b->second);
+ show(detail_fg);
+ if((a == normal[i].end()) != (b == splay[i].end())) return false;
+ if( a == normal[i].end()) return true;
+ return (a->first == b->first && a->second == b->second);
+}
+static bool rUpperBound(int i, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= rUpperBound(%d, %d)\n", i, key);
+ t0 = clock(); IterS b = splay [i].rUpperBound(key); (*tS) += clock() - t0;
+ t0 = clock();
+ IterN a, z;
+ if(normal[i].begin() == normal[i].end()){
+ a = normal[i].end();
+ }else{
+ if(normal[i].begin()->first >= key) a = normal[i].end();
+ else{
+ for(a = normal[i].begin(), z = a, z++; z != normal[i].end(); a++, z++){
+ if(z->first >= key)
+ break;
+ }
+ }
+ }
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (a == normal[i].end()) ? 0 : a->first,
+ (b == splay[i].end()) ? 0 : b->first,
+ (a == normal[i].end()) ? 0 : a->second,
+ (b == splay[i].end()) ? 0 : b->second);
+ show(detail_fg);
+ if((a == normal[i].end()) != (b == splay[i].end())) return false;
+ if( a == normal[i].end()) return true;
+ return (a->first == b->first && a->second == b->second);
+}
+static bool find(int i, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= find(%d, %d)\n", i, key);
+ t0 = clock(); IterS b = splay [i].find(key); (*tS) += clock() - t0;
+ t0 = clock(); IterN a = normal[i].find(key); (*tN) += clock() - t0;
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (a == normal[i].end()) ? 0 : a->first,
+ (b == splay[i].end()) ? 0 : b->first,
+ (a == normal[i].end()) ? 0 : a->second,
+ (b == splay[i].end()) ? 0 : b->second);
+ show(detail_fg);
+ if((a == normal[i].end()) != (b == splay[i].end())) return false;
+ if( a == normal[i].end()) return true;
+ return (a->first == b->first && a->second == b->second);
+}
+static bool order(int i, int order, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= order(%d, %d)\n", i, order);
+ t0 = clock(); IterS b = splay[i].order(order); (*tS) += clock() - t0;
+ t0 = clock();
+ IterN a = normal[i].begin();
+ for(int k = 0; k < order; k++) a++;
+ (*tN) += clock() - t0;
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (a == normal[i].end()) ? 0 : a->first,
+ (b == splay[i].end()) ? 0 : b->first,
+ (a == normal[i].end()) ? 0 : a->second,
+ (b == splay[i].end()) ? 0 : b->second);
+ show(detail_fg);
+ if((a == normal[i].end()) != (b == splay[i].end())) return false;
+ if( a == normal[i].end()) return true;
+ return (a->first == b->first && a->second == b->second);
+}
+static bool first_last(int i, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= first_last(%d)\n", i);
+ IterN a;
+ t0 = clock(); IterS b = splay[i].first (); (*tS) += clock() - t0;
+ t0 = clock(); a = normal[i].begin(); (*tN) += clock() - t0;
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (a == normal[i].end()) ? 0 : a->first,
+ (b == splay[i].end()) ? 0 : b->first,
+ (a == normal[i].end()) ? 0 : a->second,
+ (b == splay[i].end()) ? 0 : b->second);
+ if((a == normal[i].end()) != (b == splay[i].end())) return false;
+ if( a == normal[i].end());
+ else{
+ if((a->first == b->first && a->second == b->second) == false){
+ return false;
+ }
+ }
+ t0 = clock(); b = splay[i].last (); (*tS) += clock() - t0;
+ t0 = clock(); IterR r = normal[i].rbegin(); (*tN) += clock() - t0;
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (r == normal[i].rend()) ? 0 : r->first,
+ (b == splay[i].end()) ? 0 : b->first,
+ (r == normal[i].rend()) ? 0 : r->second,
+ (b == splay[i].end()) ? 0 : b->second);
+ if((r == normal[i].rend()) != (b == splay[i].end())) return false;
+ if(r == normal[i].rend());
+ else{
+ if((r->first == b->first && r->second == b->second) == false){
+ return false;
+ }
+ }
+ return true;
+}
+static bool insert(int i, int key, double val, size_t* tN, size_t* tS){
+ size_t t0;
+ if(rand() & 1){
+ t0 = clock(); splay [i].insert(key, val); (*tS) += clock() - t0;
+ t0 = clock(); normal[i].insert(std::pair<int, double>(key, val)); (*tN) += clock() - t0;
+ }else{
+ t0 = clock(); splay [i][key] = val; (*tS) += clock() - t0;
+ t0 = clock(); normal[i][key] = val; (*tN) += clock() - t0;
+ }
+ detail_fg && printf("============= insert(%d, %d)\n", i, key);
+ show(detail_fg);
+ return true;
+}
+static bool split(int i, int j, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ if(i == j){
+ return true;
+ }
+ detail_fg && printf("============= split(%d, %d, %d)\n", i, j, key);
+ t0 = clock(); splay[i].splitOut(key, &splay[j]); *tS += clock() - t0;
+ t0 = clock();
+ normal[j].clear();
+ for(IterN it; (it = normal[i].upper_bound(key)) != normal[i].end(); ){
+ normal[j].insert(*it);
+ normal[i].erase(it);
+ }
+ *tN += clock() - t0;
+ show(detail_fg);
+ return true;
+}
+static bool merge(int i, int j, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ if(i == j){
+ return true;
+ }
+ if(rand() & 1){
+ t0 = clock();
+ if(splay[i].size() > 0)
+ while(splay[j].size() > 0 &&
+ splay[j].first()->first <= splay[i].last()->first){
+ splay[j].erase(splay[j].first()->first);
+ }
+ *tS += clock() - t0;
+ t0 = clock();
+ if(normal[i].size() > 0)
+ while(normal[j].size() > 0 &&
+ normal[j].begin()->first <= normal[i].rbegin()->first)
+ normal[j].erase(normal[j].begin());
+ *tN += clock() - t0;
+ }
+ t0 = clock(); splay[i].merge(&splay[j]); *tS += clock() - t0;
+ t0 = clock();
+ if(normal[i].size() == 0 || normal[j].size() == 0 ||
+ normal[i].rbegin()->first < normal[j].begin()->first ||
+ normal[j].rbegin()->first < normal[i].begin()->first
+ ){
+ for(IterN it = normal[j].begin(); it != normal[j].end(); it++){
+ normal[i].insert(*it);
+ }
+ normal[j].clear();
+ }
+ *tN += clock() - t0;
+ detail_fg && printf("============= merge(%d, %d)\n", i, j, key);
+ show(detail_fg);
+ return true;
+}
+static bool erase(int i, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= erase(%d, %d)\n", i, key);
+ t0 = clock(); splay[i].erase(key); (*tS) += clock() - t0;
+ t0 = clock(); normal[i].erase(key); (*tN) += clock() - t0;
+ show(detail_fg);
+ return true;
+}
+static bool keyOffset(int i, int delta, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= keyOffset(%d, %d)\n", i, delta);
+ t0 = clock(); splay[i].keyOffset(delta); (*tS) += clock() - t0;
+ t0 = clock();
+ std::map<int, double> tmp = normal[i];
+ normal[i].clear();
+ for(IterN it = tmp.begin(); it != tmp.end(); it++){
+ normal[i].insert(std::pair<int, double>(it->first + delta, it->second));
+ }
+ (*tN) += clock() - t0;
+ show(detail_fg);
+ return true;
+}
+/*
+static bool valueOffset(int i, double delta, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= valueOffset(%d, %f)\n", i, delta);
+ t0 = clock(); splay[i].valueOffset(delta); (*tS) += clock() - t0;
+ t0 = clock();
+ for(IterN it = normal[i].begin(); it != normal[i].end(); it++){
+ it->second += delta;
+ }
+ (*tN) += clock() - t0;
+ show(detail_fg);
+ return true;
+}
+// */
+static bool copy(int i, int j, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("copy(%d, %d)\n", i, j);
+ t0 = clock(); splay[i] = splay[j]; (*tS) += clock() - t0;
+ t0 = clock(); normal[i] = normal[j]; (*tN) += clock() - t0;
+ show(detail_fg);
+ return true;
+}
+
+static bool check(){
+ for(int i = 0; i < N; i++){
+ if(normal[i].size() != splay[i].size()) return false;
+ int j = 0;
+ for(IterN it = normal[i].begin(); it != normal[i].end(); it++, j++){
+ if(it->first != splay[i].order(j)->first ||
+ it->second != splay[i].order(j)->second)
+ return false;
+ }
+ }
+ return true;
+}
+
+TEST(SplayTree){
+ detail_fg = false;
+ N = 5;
+ for(int i = 0; i < 10; i++){
+ normal.clear();
+ splay .clear();
+ normal.resize(N);
+ splay .resize(N);
+ size_t tn = 0, tm = 0;
+ int op = 1 + rand() % 2000000;
+ meow::messagePrintf(1, "%d-th test, N = %d, op = %7d", i, N, op);
+ while(op--){
+ int wh = rand() % 60;
+ int i1 = rand() % N, i2, k = rand() % 60;
+ while((i2 = rand() % N) == i1);
+ switch(wh){
+ case 0:
+ if(lowerBound(i1, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "lowerBound");
+ //for(int z = 0; z < N; z++){ splay[z].print(); }
+ show(true);
+ return false;
+ }
+ break;
+ case 1:
+ if(rUpperBound(i1, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "rUpperBound");
+ //for(int z = 0; z < N; z++){ splay[z].print(); }
+ show(true);
+ return false;
+ }
+ break;
+ case 2:
+ if(rLowerBound(i1, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "rLowerBound");
+ //for(int z = 0; z < N; z++){ splay[z].print(); }
+ show(true);
+ return false;
+ }
+ break;
+ case 3:
+ if(upperBound(i1, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "upperBound");
+ //for(int z = 0; z < N; z++){ splay[z].print(); }
+ show(true);
+ return false;
+ }
+ break;
+ case 4:
+ case 5:
+ case 6:
+ if(find(i1, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "find");
+ //for(int z = 0; z < N; z++){ splay[z].print(); }
+ show(true);
+ return false;
+ }
+ break;
+ case 7:
+ case 8:
+ case 9:
+ if(normal[i1].size() > 0){
+ if(order(i1, rand() % normal[i1].size(), &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "order");
+ //for(int z = 0; z < N; z++){ splay[z].print(); }
+ show(true);
+ return false;
+ }
+ break;
+ }
+ case 10:
+ if(first_last(i1, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "first_last");
+ //for(int z = 0; z < N; z++){ splay[z].print(); }
+ show(true);
+ return false;
+ }
+ break;
+ case 11:
+ case 12:
+ case 13:
+ case 14:
+ case 15:
+ case 16:
+ case 17:
+ case 18:
+ case 19:
+ case 20:
+ if(insert(i1, k, rand() * 1.0 / RAND_MAX * 50, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "insert");
+ //for(int z = 0; z < N; z++){ splay[z].print(); }
+ show(true);
+ return false;
+ }
+ break;
+ case 21:
+ case 22:
+ case 23:
+ case 24:
+ case 25:
+ case 26:
+ if(split(i1, i2, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "split");
+ //for(int z = 0; z < N; z++){ splay[z].print(); }
+ show(true);
+ return false;
+ }
+ break;
+ case 27:
+ case 28:
+ case 29:
+ case 30:
+ case 31:
+ case 32:
+ case 33:
+ case 34:
+ case 35:
+ case 36:
+ if(merge(i1, i2, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "merge");
+ //for(int z = 0; z < N; z++){ splay[z].print(); }
+ show(true);
+ return false;
+ }
+ break;
+ case 37:
+ case 38:
+ case 39:
+ case 40:
+ if(erase(i1, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "erase");
+ //for(int z = 0; z < N; z++){ splay[z].print(); }
+ show(true);
+ return false;
+ }
+ break;
+ case 41:
+ case 42:
+ case 43:
+ case 44:
+ case 45:
+ case 46:
+ case 47:
+ case 48:
+ case 49:
+ if(keyOffset(i1, ((rand() & 2) - 1) * k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "keyOffset");
+ //for(int z = 0; z < N; z++){ splay[z].print(); }
+ show(true);
+ return false;
+ }
+ break;
+ case 50:
+ case 51:
+ case 52:
+ if(copy(i1, i2, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "copy");
+ //for(int z = 0; z < N; z++){ splay[z].print(); }
+ show(true);
+ return false;
+ }
+ break;
+ case 53:
+ case 54:
+ case 55:
+ case 56:
+ case 57:
+ case 58:
+ case 59:
+ op++;
+ /*
+ if(valueOffset(i1, 1.0 * rand() / RAND_MAX * 100, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "valueOffset");
+ //for(int z = 0; z < N; z++){ splay[z].print(); }
+ show(true);
+ return false;
+ }
+ break;
+ // */
+ }
+ }
+ if(!check()){
+ meow::messagePrintf(-1, "fail");
+ show(true);
+ return false;
+ }
+ meow::messagePrintf(-1, "ok %.3f/%.3f",
+ tm * 1.0 / CLOCKS_PER_SEC,
+ tn * 1.0 / CLOCKS_PER_SEC);
+ }
+ return true;
+};
diff --git a/footer.asciidoc b/footer.asciidoc
index a6301ee..18c6751 100644
--- a/footer.asciidoc
+++ b/footer.asciidoc
@@ -16,6 +16,18 @@ https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&pag
| Accept | 0.516 | http://codepad.org/03dW6ZHV[codepad]
+| SplayTree + SegmentTree | 'Shuffling_cards' |
+http://acm.csie.org/ntujudge/problem.php?id=1353[NTU-OJ]
+http://www.spoj.com/problems/SHUFFLEK/[SPOJ]
+| Accept/TLE | 6.910/--- | http://codepad.org/yUeiVZc0[codepad]
+
+| SplayTree + BinaryIndexTree | 'Shuffling_cards' |
+http://acm.csie.org/ntujudge/problem.php?id=1353[NTU-OJ]
+http://www.spoj.com/problems/SHUFFLEK/[SPOJ]
+|Accept/Accept|5.480/44.35| http://codepad.org/GAWjEtmq[codepad]
+
+
+
|=======================================================================
diff --git a/meowpp/dsa/BinaryIndexTree.h b/meowpp/dsa/BinaryIndexTree.h
new file mode 100644
index 0000000..4b1b23a
--- /dev/null
+++ b/meowpp/dsa/BinaryIndexTree.h
@@ -0,0 +1,69 @@
+#ifndef __BinaryIndexTree_H__
+#define __BinaryIndexTree_H__
+
+namespace meow{
+ //#
+ //#=== meow:: *BinaryIndexTree<Value>* (C++ class)
+ //#==== Description
+ //# 極度簡化版的 `SegmentTree` 已無法區間操作, 區間詢問的區間開頭也一定要
+ //# 在 `index=0` 的地方
+ //#
+ //#==== Template Class Operators Request
+ //#[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"]
+ //#|=====================================================================
+ //#|Const?|Typename| Operator | Parameters | Return_Type| Description
+ //#|const | Value | operator+ |(Value `n`) | Value | 合併用(類似
+ //# `SegmentTree` 的
+ //# operator{b} )
+ //#|=====================================================================
+ //#
+ template<class Value>
+ class BinaryIndexTree{
+ private:
+ std::vector<Value> _array;
+ public:
+ BinaryIndexTree();
+ BinaryIndexTree(size_t __size, Value const& __value);
+ BinaryIndexTree(BinaryIndexTree const& __tree2);
+
+ //#==== Support Methods
+ //#
+ //# * N <- `this` 中擁有的資料數
+ //#
+ //#[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"]
+ //#|=====================================================================
+ //#|Const?|Name | Parameters | Return_Type| Time_Complexity| Description
+
+
+ //#||reset|(size_t `size`, Value const& `value`)|void|O(`size`)
+ //#|將資料長度刷成 `N = size` 且每一個元素都是 `value`
+ void reset(size_t __size, Value const& __value);
+
+
+ //#||update|(size_t `index`, Value const& `value`)|void|O(logN)
+ //#|將第 `index` (從零開始算) 多加上 `value`
+ void update( size_t __index, Value const& __value);
+
+
+ //#|const|query|(size_t `index`)|void|O(logN)
+ //#|詢問 `0~index` 的區間值
+ Value query (ssize_t __index) const;
+
+
+ //#|=====================================================================
+ };
+ //#
+ //#[NOTE]
+ //#========================================
+ //# * 一般來說只能用在維護區間總和, 維護區間最大值只有在特殊情況才可以, 即
+ //# '針對每個元素, 每次 update() 的值一定會大於等於原本的值'
+ //# * 若要用區間最大值 , 則 `Value` 的 `operator+` 要寫成 `std::max(...)`
+ //#========================================
+ //#
+ //# '''
+}
+
+#include "BinaryIndexTree.hpp"
+
+#endif // BinaryIndexTree_H__
+
diff --git a/meowpp/dsa/BinaryIndexTree.hpp b/meowpp/dsa/BinaryIndexTree.hpp
new file mode 100644
index 0000000..e7e146a
--- /dev/null
+++ b/meowpp/dsa/BinaryIndexTree.hpp
@@ -0,0 +1,44 @@
+
+namespace meow{
+ template<class Value>
+ inline
+ BinaryIndexTree<Value>::BinaryIndexTree():
+ _array(0){
+ }
+ template<class Value>
+ inline
+ BinaryIndexTree<Value>::BinaryIndexTree(size_t __size, Value const& __value):
+ _array(__size, __value){
+ }
+ template<class Value>
+ inline
+ BinaryIndexTree<Value>::BinaryIndexTree(BinaryIndexTree const& __tree2):
+ _array(__tree2._array){
+ }
+ //
+ template<class Value>
+ inline void
+ BinaryIndexTree<Value>::reset(size_t __size, Value const& __init){
+ _array.clear();
+ _array.resize(__size, __init);
+ }
+ //
+ template<class Value>
+ inline void
+ BinaryIndexTree<Value>::update(size_t __index, Value const& __value){
+ __index++;
+ for( ; __index <= _array.size(); __index += (__index & -__index)){
+ _array[__index - 1] = _array[__index - 1] + __value;
+ }
+ }
+ template<class Value>
+ inline Value
+ BinaryIndexTree<Value>::query(ssize_t __index) const{
+ __index = std::min(__index + 1, (ssize_t)_array.size());
+ Value ret(0);
+ for( ; 0 < __index; __index -= (__index & -__index)){
+ ret = ret + _array[__index - 1];
+ }
+ return ret;
+ }
+}
diff --git a/meowpp/dsa/SplayTree.h b/meowpp/dsa/SplayTree.h
index 69b204e..38cbe7f 100644
--- a/meowpp/dsa/SplayTree.h
+++ b/meowpp/dsa/SplayTree.h
@@ -29,31 +29,27 @@ namespace meow{
Value _value;
size_t _size;
Node* _parent;
- Node* _lChild;
- Node* _rChild;
+ Node* _child[2];
//
Node(Key const& __key, Value const& __value);
+ //
+ void keyOffset(Key const& __delta);
+ void syncDown() const;
+ void syncUp () const;
};
//
Node* _root;
//
- void offsetAdd (Node* __node, Key const& __delta) const;
- void offsetDown (Node* __node ) const;
- void sizeUpdate (Node* __node ) const;
- void connectLChild(Node* __parent, Node* __child ) const;
- void connectRChild(Node* __parent, Node* __child ) const;
- Node const* setRoot(Node* __node) const;
- //
- Node* clear (Node* __node);
- Node* dup (Node* __node);
+ void connect(Node const* __parent, size_t __left_right,
+ Node const* __child) const;
+ Node const* splay (Node const* __node) const;
//
- void rotate( Node* __parent, Node* __child) const;
- void rotate(Node* __grand, Node* __parent, Node* __child) const;
- Node* splay(Node* __node) const;
+ void clear(Node* __node);
+ Node* dup(Node* __node);
//
- Node* findKey (Node* __node, Key const& __key) const;
- Node* findMinMax(Node* __node, bool minimum ) const;
- Node* findOrder (Node* __node, size_t __order ) const;
+ Node const* findKey (Node const* __node, Key const& __key ) const;
+ Node const* findMinMax(Node const* __node, bool __minimum) const;
+ Node const* findOrder (Node const* __node, size_t __order ) const;
//
void split(Node* __root, Node** __left, Node** __right);
Node* merge( Node* __left, Node* __right);
@@ -114,13 +110,13 @@ namespace meow{
//#|const|lowerBound|(Key const& `k`)|Element|O(logN)
//#|找出第一個(最小的) Element且 `k` <= 它的 Key, 並且回傳之.
//# 找不到的話回傳 `this->end()`
- Element lowerBound(Key const& __key) const;
+ Element lowerBound(Key const& __key) const;
//#|const|lowerBound|(Key const& `k`)|Element|O(logN)
//#|找出第一個(最小的) Element且 `k` < 它的 Key, 並且回傳之.
//# 找不到的話回傳 `this->end()`
- Element upperBound(Key const& __key) const;
+ Element upperBound(Key const& __key) const;
//#|const|lowerBound|(Key const& `k`)|Element|O(logN)
@@ -163,22 +159,17 @@ namespace meow{
//#|const|size|()|size_t|O(1)| 回傳資料數
- size_t size() const;
+ size_t size() const;
//#|const|size|()|bool|O(1)| 回傳是否為空
- bool empty() const;
+ bool empty() const;
//#||clear|()|void|O(N)| 清空資料
void clear();
- //#||keyOffset|(Key const& `delta`)|void|O(1)
- //#|將所有Element的Key同加上 `delta`
- void keyOffset(Key const& __delta);
-
-
//#||insert|(Key const& `key`,\Value const& `value`)|bool|O(logN)
//#|檢查是否已有Element的Key 為 `key`, 若有則回傳 `false` , 否則將
//# 一個 (Key -> Value) = (`key` -> `value`)的Element加入, 並回傳 `true`
@@ -192,6 +183,11 @@ namespace meow{
bool erase(Key const& __key);
+ //#||keyOffset|(Key const& `delta`)|void|O(1)
+ //#|將所有Element的Key同加上 `delta`
+ void keyOffset(Key const& __delta);
+
+
//#||operator[]|(Key const& `key`)|Value&|O(logN)
//#|檢查是否已有Element的Key 為 `key`, 若有則回傳相對應的Value的Reference
//# 否則先執行 `insert(key, Value())` 再回傳相對應的Reference
@@ -217,8 +213,8 @@ namespace meow{
//# 中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則
//# 回傳 `false`
bool merge(SplayTree* __tree2);
- //
- //
+
+
void print() const;
//#|=====================================================================
};
diff --git a/meowpp/dsa/SplayTree.hpp b/meowpp/dsa/SplayTree.hpp
index 77331ef..de08f63 100644
--- a/meowpp/dsa/SplayTree.hpp
+++ b/meowpp/dsa/SplayTree.hpp
@@ -1,200 +1,154 @@
namespace meow{
+ ///////////////////////////// **# Node #** /////////////////////////
+ //////////////////// **# Node -- Constructure #** //////////////////
template<class Key, class Value>
- inline SplayTree<Key, Value>::Node::Node(Key const& __key,
- Value const& __value):
- _key(__key),
- _keyOffset(0),
- _value(__value),
- _size(1),
- _parent(NULL),
- _lChild(NULL),
- _rChild(NULL){ }
- //
+ inline
+ SplayTree<Key, Value>::Node::Node(Key const& __key, Value const& __value):
+ _key(__key), _keyOffset(0), _value(__value){
+ _size = 1;
+ _parent = NULL;
+ _child[0] = NULL;
+ _child[1] = NULL;
+ }
+ //////////////////////// **# Node -- Offset #** ////////////////////
template<class Key, class Value>
inline void
- SplayTree<Key, Value>::offsetAdd(Node* __node, Key const& __delta) const{
- __node->_key = __node->_key + __delta;
- __node->_keyOffset = __node->_keyOffset + __delta;
+ SplayTree<Key, Value>::Node::keyOffset(Key const& __delta){
+ _key = _key + __delta;
+ _keyOffset = _keyOffset + __delta;
}
+ //////////////////////// **# Node -- sync #** //////////////////////
template<class Key, class Value>
inline void
- SplayTree<Key, Value>::sizeUpdate(Node* __node) const{
- if(__node != NULL){
- __node->_size = 1;
- if(__node->_lChild != NULL) __node->_size += __node->_lChild->_size;
- if(__node->_rChild != NULL) __node->_size += __node->_rChild->_size;
+ SplayTree<Key, Value>::Node::syncDown() const{
+ for(size_t i = 0; i < 2; i++){
+ if(_child[i] == NULL) continue;
+ _child[i]->keyOffset(_keyOffset);
}
+ ((Node*)this)->_keyOffset = Key(0);
}
template<class Key, class Value>
inline void
- SplayTree<Key, Value>::offsetDown(Node* __node) const{
- if(__node->_lChild != NULL) offsetAdd(__node->_lChild, __node->_keyOffset);
- if(__node->_rChild != NULL) offsetAdd(__node->_rChild, __node->_keyOffset);
- __node->_keyOffset = Key(0);
+ SplayTree<Key, Value>::Node::syncUp() const{
+ ((Node*)this)->_size = 1;
+ for(size_t i = 0; i < 2; i++){
+ if(_child[i] == NULL) continue;
+ ((Node*)this)->_size += _child[i]->_size;
+ }
}
- //
+ ////////////////////////// **# SplayTree #** ///////////////////////
+ ///////////////////// **# connection, splay #** ////////////////////
template<class Key, class Value>
inline void
- SplayTree<Key, Value>::connectLChild(Node* __parent, Node* __child) const{
- if(__parent != NULL) __parent->_lChild = __child;
- if(__child != NULL) __child ->_parent = __parent;
+ SplayTree<Key, Value>::connect(Node const* __parent, size_t __left_right,
+ Node const* __child) const{
+ Node* parent = (Node*)__parent;
+ Node* child = (Node*)__child;
+ if(parent != NULL) parent->_child[__left_right] = child;
+ if(child != NULL) child ->_parent = parent;
}
template<class Key, class Value>
- inline void
- SplayTree<Key, Value>::connectRChild(Node* __parent, Node* __child) const{
- if(__parent != NULL) __parent->_rChild = __child;
- if(__child != NULL) __child ->_parent = __parent;
+ inline typename SplayTree<Key, Value>::Node const*
+ SplayTree<Key, Value>::splay(Node const* __node) const{
+ if(__node != NULL && __node->_parent != NULL){
+ for(const Node *g_grand, *grand, *parent, *child = __node; ; ){
+ g_grand = (grand = parent = child->_parent)->_parent;
+ size_t pc = (parent->_child[0] == child ? 0 : 1);
+ connect(parent, pc, child->_child[!pc]);
+ connect(child , !pc, parent);
+ if(g_grand != NULL){
+ g_grand = (grand = g_grand)->_parent;
+ size_t gp = (grand->_child[0] == parent ? 0 : 1);
+ Node const* who = (pc == gp ? parent : child);
+ connect(grand, gp, who->_child[!gp]);
+ connect(who , !gp, grand);
+ grand->syncUp();
+ }
+ parent->syncUp();
+ child ->syncUp();
+ if(g_grand == NULL){
+ connect(NULL, 0, child);
+ break;
+ }
+ connect(g_grand, (g_grand->_child[0] == grand ? 0 : 1), child);
+ }
+ }
+ return (((SplayTree*)this)->_root = (Node*)__node);
}
- //
+ ///////////////////////// **# clear, dup #** ///////////////////////
template<class Key, class Value>
- inline typename SplayTree<Key, Value>::Node*
+ inline void
SplayTree<Key, Value>::clear(Node* __node){
- if(__node != NULL){
- clear(__node->_lChild);
- clear(__node->_rChild);
- delete __node;
- }
- return NULL;
+ if(__node == NULL) return ;
+ clear(__node->_child[0]);
+ clear(__node->_child[1]);
+ delete __node;
}
template<class Key, class Value>
inline typename SplayTree<Key, Value>::Node*
SplayTree<Key, Value>::dup(Node* __node){
if(__node == NULL) return NULL;
- offsetDown(__node);
+ __node->syncDown();
Node* node = new Node(__node->_key, __node->_value);
- connectLChild(node, dup(__node->_lChild));
- connectRChild(node, dup(__node->_rChild));
- sizeUpdate(node);
+ connect(node, 0, dup(__node->_child[0]));
+ connect(node, 1, dup(__node->_child[1]));
+ node->syncUp();
return node;
}
+ /////////////////////////// **# find #** ///////////////////////////
template<class Key, class Value>
inline typename SplayTree<Key, Value>::Node const*
- SplayTree<Key, Value>::setRoot(Node* __node) const{
- connectLChild(NULL, (((SplayTree*)this)->_root = __node));
- return _root;
- }
- //
- template<class Key, class Value>
- inline void
- SplayTree<Key, Value>::rotate(Node* __parent, Node* __child) const{
- if(__parent->_lChild == __child){
- connectLChild(__parent, __child->_rChild);
- connectRChild(__child , __parent);
- }else{
- connectRChild(__parent, __child->_lChild);
- connectLChild(__child , __parent);
- }
- sizeUpdate(__parent);
- sizeUpdate(__child );
- }
- template<class Key, class Value>
- inline void
- SplayTree<Key, Value>::rotate(Node* __grand,
- Node* __parent,
- Node* __child) const{
- if(__grand->_lChild == __parent){
- if(__parent->_lChild == __child){
- connectLChild(__grand , __parent->_rChild);
- connectLChild(__parent, __child ->_rChild);
- connectRChild(__child , __parent);
- connectRChild(__parent, __grand );
- }else{
- connectRChild(__parent, __child->_lChild);
- connectLChild(__grand , __child->_rChild);
- connectLChild(__child, __parent);
- connectRChild(__child, __grand );
- }
- }else if(__grand->_rChild == __parent){
- if(__parent->_rChild == __child){
- connectRChild(__grand , __parent->_lChild);
- connectRChild(__parent, __child ->_lChild);
- connectLChild(__child , __parent);
- connectLChild(__parent, __grand );
- }else{
- connectRChild(__grand , __child->_lChild);
- connectLChild(__parent, __child->_rChild);
- connectLChild(__child, __grand );
- connectRChild(__child, __parent);
- }
- }
- sizeUpdate(__grand );
- sizeUpdate(__parent);
- sizeUpdate(__child );
- }
- template<class Key, class Value>
- inline typename SplayTree<Key, Value>::Node*
- SplayTree<Key, Value>::splay(Node* __node) const{
- if(__node == NULL) return NULL;
- for(Node *parent, *grand, *child = __node; child->_parent != NULL; ){
- parent = child ->_parent;
- grand = parent->_parent;
- if(grand == NULL){
- rotate(parent, child);
- break;
- }else{
- Node* g_grand = grand->_parent;
- rotate(grand, parent, child);
- if(g_grand == NULL) break;
- if(g_grand->_lChild == grand) connectLChild(g_grand, child);
- else connectRChild(g_grand, child);
- }
- }
- sizeUpdate(__node);
- return __node;
- }
- template<class Key, class Value>
- inline typename SplayTree<Key, Value>::Node*
- SplayTree<Key, Value>::findKey(Node* __node, Key const& __key) const{
- Node* ret = __node;
+ SplayTree<Key, Value>::findKey(Node const* __node, Key const& __key) const{
+ Node const* ret = __node;
while(__node != NULL){
- offsetDown(__node);
+ __node->syncDown();
ret = __node;
if(!(__key < __node->_key)){
if(!(__node->_key< __key)) break;
- __node = __node->_rChild;
+ __node = __node->_child[1];
}else{
- __node = __node->_lChild;
+ __node = __node->_child[0];
}
}
return ret;
}
template<class Key, class Value>
- inline typename SplayTree<Key, Value>::Node*
- SplayTree<Key, Value>::findMinMax(Node* __node, bool minimum) const{
- Node* ret = __node;
- while(__node != NULL){
- offsetDown(__node);
+ inline typename SplayTree<Key, Value>::Node const*
+ SplayTree<Key, Value>::findMinMax(Node const* __node, bool __minimum) const{
+ Node const* ret = __node;
+ for(int i = __minimum ? 0 : 1; __node != NULL; __node = __node->_child[i]){
+ __node->syncDown();
ret = __node;
- __node = (minimum ? __node->_lChild : __node->_rChild);
}
return ret;
}
template<class Key, class Value>
- inline typename SplayTree<Key, Value>::Node*
- SplayTree<Key, Value>::findOrder(Node* __node, size_t __order) const{
- Node* ret = __node;
+ inline typename SplayTree<Key, Value>::Node const*
+ SplayTree<Key, Value>::findOrder(Node const* __node, size_t __order) const{
+ Node const* ret = __node;
while(__node != NULL){
- offsetDown(__node);
+ __node->syncDown();
ret = __node;
- size_t ord = 1 + (__node->_lChild == NULL ? 0 : __node->_lChild->_size);
+ size_t ord = 1 + (__node->_child[0]==NULL ? 0:__node->_child[0]->_size);
if (ord == __order) return ret;
- else if(ord < __order){ __node = __node->_rChild; __order -= ord; }
- else { __node = __node->_lChild; }
+ else if(ord < __order){ __node = __node->_child[1]; __order -= ord; }
+ else { __node = __node->_child[0]; }
}
return ret;
}
+ /////////////////////// **# split, merge #** ///////////////////////
template<class Key, class Value>
inline void
SplayTree<Key, Value>::split(Node* __root, Node** __left, Node** __right){
if(__root == NULL){ *__left = NULL; *__right = NULL; return ; }
- offsetDown(__root);
+ __root->syncDown();
*__left = __root;
- *__right = __root->_rChild;
+ *__right = __root->_child[1];
if(*__right != NULL){
- (*__left )->_rChild = NULL;
- (*__right)->_parent = NULL;
- sizeUpdate(*__left);
+ (*__left )->_child[1] = NULL;
+ (*__right)->_parent = NULL;
+ (*__left )->syncUp();
}
}
template<class Key, class Value>
@@ -202,11 +156,12 @@ namespace meow{
SplayTree<Key, Value>::merge(Node* __left, Node* __right){
if(__left == NULL) return __right;
if(__right == NULL) return __left ;
- offsetDown(__left);
- connectRChild(__left, __right);
- sizeUpdate(__left);
+ __left->syncDown();
+ connect(__left, 1, __right);
+ __left->syncUp();
return __left;
}
+ //
template<class Key, class Value>
inline void SplayTree<Key, Value>::print(Node* __now, int __depth) const{
if(__now == NULL) return ;
@@ -215,12 +170,12 @@ namespace meow{
(long long unsigned)__now,
__now->_size,
(long long unsigned)__now->_parent,
- (long long unsigned)__now->_lChild,
- (long long unsigned)__now->_rChild);
- print(__now->_lChild, __depth + 1);
- print(__now->_rChild, __depth + 1);
+ (long long unsigned)__now->_child[0],
+ (long long unsigned)__now->_child[1]);
+ print(__now->_child[0], __depth + 1);
+ print(__now->_child[1], __depth + 1);
}
- //
+ ///////////////////////// **# Element ##* //////////////////////////
template<class Key, class Value>
inline void SplayTree<Key, Value>::Element::reset(Node* __node){
_node = __node;
@@ -228,25 +183,36 @@ namespace meow{
if(__node == NULL) _entry = NULL;
else _entry = new Entry(__node->_key, __node->_value);
}
+ //
template<class Key, class Value>
- inline SplayTree<Key, Value>::Element::Element():
- _entry(NULL), _node(NULL){ }
+ inline
+ SplayTree<Key, Value>::Element::Element():
+ _entry(NULL), _node(NULL){
+ }
template<class Key, class Value>
- inline SplayTree<Key, Value>::Element::Element(Node* __node):
- _entry(NULL), _node(NULL){ reset(__node); }
+ inline
+ SplayTree<Key, Value>::Element::Element(Node* __node):
+ _entry(NULL), _node(NULL){
+ reset(__node);
+ }
template<class Key, class Value>
- inline SplayTree<Key, Value>::Element::Element(Element const& __element2):
- _entry(NULL), _node(NULL){ reset(__element2._node); }
+ inline
+ SplayTree<Key, Value>::Element::Element(Element const& __element2):
+ _entry(NULL), _node(NULL){
+ reset(__element2._node);
+ }
template<class Key, class Value>
- inline SplayTree<Key, Value>::Element::~Element(){ delete _entry; }
- //
+ inline
+ SplayTree<Key, Value>::Element::~Element(){
+ delete _entry;
+ }
template<class Key, class Value>
inline typename SplayTree<Key, Value>::Element&
SplayTree<Key, Value>::Element::operator=(Element const& __e2){
reset(__e2._node);
return *this;
}
- //
+ //////////////////// **# Element operations #** ////////////////////
template<class Key, class Value>
inline typename SplayTree<Key, Value>::Element::Entry*
SplayTree<Key, Value>::Element::operator->(){ return _entry; }
@@ -264,181 +230,186 @@ namespace meow{
SplayTree<Key, Value>::Element::operator!=(Element const& __e2) const{
return (_node != __e2._node);
}
- //
+ /////// **# Splay tree constructure/destructure/copy oper #** //////
template<class Key, class Value>
- inline SplayTree<Key, Value>::SplayTree(): _root(NULL){ }
+ inline
+ SplayTree<Key, Value>::SplayTree(): _root(NULL){
+ }
template<class Key, class Value>
- inline SplayTree<Key, Value>::SplayTree(SplayTree const& __tree2):
- _root(NULL){ setRoot(dup(__tree2._root)); }
+ inline
+ SplayTree<Key, Value>::SplayTree(SplayTree const& __tree2): _root(NULL){
+ _root = dup((Node*)(__tree2._root));
+ }
template<class Key, class Value>
- inline SplayTree<Key, Value>::~SplayTree(){ clear(_root); }
+ inline
+ SplayTree<Key, Value>::~SplayTree(){
+ clear(_root);
+ }
template<class Key, class Value>
inline SplayTree<Key, Value>&
SplayTree<Key, Value>::operator=(SplayTree const& __tree2){
clear(_root);
- setRoot(dup(__tree2._root));
+ _root = dup((Node*)(__tree2._root));
return *this;
}
- //
+ template<class Key, class Value>
+ inline void
+ SplayTree<Key, Value>::moveTo(SplayTree* __tree2){
+ __tree2->clear();
+ __tree2->_root = _root;
+ _root = NULL;
+ }
+ //////////////////////// **# Bounding #** //////////////////////////
template<class Key, class Value>
inline typename SplayTree<Key, Value>::Element
SplayTree<Key, Value>::lowerBound(Key const& __key) const{
- SplayTree* me = (SplayTree*)this;
- setRoot(splay(findKey(me->_root, __key)));
+ splay(findKey(_root, __key));
if(_root == NULL || !(_root->_key < __key)) return Element(_root);
- if(_root->_rChild == NULL) return Element(NULL);
- setRoot(splay(findMinMax(me->_root->_rChild, true)));
+ if(_root->_child[1] == NULL) return Element(NULL);
+ splay(findMinMax(_root->_child[1], true));
return Element(_root);
}
template<class Key, class Value>
inline typename SplayTree<Key, Value>::Element
SplayTree<Key, Value>::upperBound(Key const& __key) const{
- SplayTree* me = (SplayTree*)this;
- setRoot(splay(findKey(me->_root, __key)));
+ splay(findKey(_root, __key));
if(_root == NULL || __key < _root->_key) return Element(_root);
- if(_root->_rChild == NULL) return Element(NULL);
- setRoot(splay(findMinMax(me->_root->_rChild, true)));
+ if(_root->_child[1] == NULL) return Element(NULL);
+ splay(findMinMax(_root->_child[1], true));
return Element(_root);
}
template<class Key, class Value>
inline typename SplayTree<Key, Value>::Element
SplayTree<Key, Value>::rLowerBound(Key const& __key) const{
- SplayTree* me = (SplayTree*)this;
- setRoot(splay(findKey(me->_root, __key)));
+ splay(findKey(_root, __key));
if(_root == NULL || !(__key < _root->_key)) return Element(_root);
- if(_root->_lChild == NULL){
- return NULL;
- }
- setRoot(splay(findMinMax(me->_root->_lChild, false)));
+ if(_root->_child[0] == NULL) return Element(NULL);
+ splay(findMinMax(_root->_child[0], false));
return Element(_root);
}
template<class Key, class Value>
inline typename SplayTree<Key, Value>::Element
SplayTree<Key, Value>::rUpperBound(Key const& __key) const{
- SplayTree* me = (SplayTree*)this;
- setRoot(splay(findKey(me->_root, __key)));
+ splay(findKey(_root, __key));
if(_root == NULL || _root->_key < __key) return Element(_root);
- if(_root->_lChild == NULL) return Element(NULL);
- setRoot(splay(findMinMax(me->_root->_lChild, false)));
+ if(_root->_child[0] == NULL) return Element(NULL);
+ splay(findMinMax(_root->_child[0], false));
return Element(_root);
}
+ ////////////// **# find / order / first / last / end #** ////////////
template<class Key, class Value>
inline typename SplayTree<Key, Value>::Element
SplayTree<Key, Value>::find(Key const& __key) const{
- SplayTree* me = (SplayTree*)this;
- setRoot(splay(findKey(me->_root, __key)));
- if(_root != NULL && _root->_key == __key) return Element(_root);
+ splay(findKey(_root, __key));
+ if(_root != NULL && !(__key < _root->_key) && !(_root->_key < __key)){
+ return Element(_root);
+ }
return Element(NULL);
}
template<class Key, class Value>
inline typename SplayTree<Key, Value>::Element
SplayTree<Key, Value>::order(size_t __order) const{
- SplayTree* me = (SplayTree*)this;
- setRoot(splay(findOrder(me->_root, __order + 1)));
+ if(_root == NULL || __order >= _root->_size) return Element(NULL);
+ splay(findOrder(_root, __order + 1));
return Element(_root);
}
template<class Key, class Value>
inline typename SplayTree<Key, Value>::Element
SplayTree<Key, Value>::first() const{
- SplayTree* me = (SplayTree*)this;
- setRoot(splay(findMinMax(me->_root, true)));
+ splay(findMinMax(_root, true));
return Element(_root);
}
template<class Key, class Value>
inline typename SplayTree<Key, Value>::Element
SplayTree<Key, Value>::last() const{
- SplayTree* me = (SplayTree*)this;
- setRoot(splay(findMinMax(me->_root, false)));
+ splay(findMinMax(_root, false));
return Element(_root);
}
template<class Key, class Value>
inline typename SplayTree<Key, Value>::Element
SplayTree<Key, Value>::end() const{ return Element(NULL); }
+ //////////////////// **# size, empty, clear #** ////////////////////
template<class Key, class Value>
inline size_t SplayTree<Key, Value>::size() const{
return (_root == NULL ? 0 : _root->_size);
}
template<class Key, class Value>
- inline bool SplayTree<Key, Value>::empty() const{ return (size() == 0); }
+ inline bool SplayTree<Key, Value>::empty() const{
+ return (size() == 0);
+ }
//
template<class Key, class Value>
inline void SplayTree<Key, Value>::clear(){
clear(_root);
_root = NULL;
}
- template<class Key, class Value>
- inline void SplayTree<Key, Value>::keyOffset(Key const& __delta){
- if(_root != NULL){
- offsetAdd(_root, __delta);
- }
- }
+ ////////////// **# insert, erase, keyOffset, oper[] #** ////////////
template<class Key, class Value>
inline bool SplayTree<Key, Value>::insert(Key const& __key,
Value const& __value){
if(_root == NULL){
- setRoot(new Node(__key, __value));
- return true;
- }
- Node* parent = findKey(_root, __key);
- Node* new_node;
- if(parent->_key < __key){
- connectRChild(parent, new_node = new Node(__key, __value));
- sizeUpdate(parent);
- }else if(__key < parent->_key){
- connectLChild(parent, new_node = new Node(__key, __value));
- sizeUpdate(parent);
+ _root = new Node(__key, __value);
}else{
- setRoot(splay(parent));
- return false;
+ Node* parent = (Node*)findKey(_root, __key);
+ if(!(parent->_key < __key) && !(__key < parent->_key)){
+ splay(parent);
+ return false;
+ }
+ Node* new_node = new Node(__key, __value);
+ connect(parent, (parent->_key < __key ? 1 : 0), new_node);
+ parent->syncUp();
+ splay(new_node);
}
- setRoot(splay(new_node));
return true;
}
template<class Key, class Value>
inline bool SplayTree<Key, Value>::erase(Key const& __key){
if(_root == NULL) return false;
- Node* body = findKey(_root, __key);
+ Node* body = (Node*)findKey(_root, __key);
if(body->_key < __key || __key < body->_key){
- setRoot(splay(body));
+ splay(body);
return false;
}
Node* ghost;
- if(body->_rChild == NULL){
- ghost = body->_lChild;
- if(ghost != NULL) offsetDown(ghost);
+ if(body->_child[1] == NULL){
+ ghost = body->_child[0];
+ if(ghost != NULL) ghost->syncDown();
}else{
- ghost = findMinMax(body->_rChild, true);
- connectLChild(ghost, body->_lChild);
- if(ghost != body->_rChild){
- connectLChild(ghost->_parent, ghost->_rChild);
- connectRChild(ghost, body->_rChild);
- for(Node* acestor = ghost->_parent;
- acestor != ghost;
- acestor = acestor->_parent){
- sizeUpdate(acestor);
- }
+ ghost = (Node*)findMinMax(body->_child[1], true);
+ connect(ghost, 0, body->_child[0]);
+ if(ghost != body->_child[1]){
+ connect(ghost->_parent, 0, ghost->_child[1]);
+ connect(ghost, 1, body->_child[1]);
+ for(Node* a = ghost->_parent; a != ghost; a = a->_parent)
+ a->syncUp();
}
- sizeUpdate(ghost);
- }
- if(body->_parent != NULL && body->_parent->_lChild == body){
- connectLChild(body->_parent, ghost);
- }else{
- connectRChild(body->_parent, ghost);
+ ghost->syncUp();
}
- setRoot(splay(ghost != NULL ? ghost : body->_parent));
+ Node* parent = body->_parent;
+ connect(parent, parent != NULL && parent->_child[0] == body ? 0 : 1,
+ ghost);
+ delete body;
+ splay(ghost != NULL ? ghost : parent);
return true;
}
template<class Key, class Value>
+ inline void SplayTree<Key, Value>::keyOffset(Key const& __delta){
+ if(_root != NULL){
+ _root->keyOffset(__delta);
+ }
+ }
+ template<class Key, class Value>
inline Value&
SplayTree<Key, Value>::operator[](Key const& __key){
if(find(__key) == end()) insert(__key, Value());
- return find(__key)->second;
+ return _root->_value;
}
+ /////////////////////// **# split, merge #** ///////////////////////
template<class Key, class Value>
inline void
SplayTree<Key, Value>::splitOut(Key const& __upper_bound, SplayTree* __right){
__right->clear();
- if(rLowerBound(__upper_bound) != Element(NULL)){
+ if(rLowerBound(__upper_bound) != end()){
split(_root, &_root, &(__right->_root));
}else{
__right->_root = _root;
@@ -450,7 +421,7 @@ namespace meow{
SplayTree<Key, Value>::mergeAfter(SplayTree* __tree2){
if(_root == NULL || __tree2->_root == NULL ||
last()->first < __tree2->first()->first){
- setRoot(merge(_root, __tree2->_root));
+ _root = merge(_root, __tree2->_root);
__tree2->_root = NULL;
return true;
}
@@ -459,16 +430,13 @@ namespace meow{
template<class Key, class Value>
inline bool
SplayTree<Key, Value>::merge(SplayTree* __tree2){
- if(_root == NULL || __tree2->_root == NULL){
- setRoot(merge(_root, __tree2->_root));
+ if(_root == NULL || __tree2->_root == NULL ||
+ last()->first < __tree2->first()->first){
+ _root = merge(_root, __tree2->_root);
+ }else if(__tree2->last()->first < first()->first){
+ _root = merge(__tree2->_root, _root);
}else{
- if(last()->first < __tree2->first()->first){
- setRoot(merge(_root, __tree2->_root));
- }else if(__tree2->last()->first < first()->first){
- setRoot(merge(__tree2->_root, _root));
- }else{
- return false;
- }
+ return false;
}
__tree2->_root = NULL;
return true;
@@ -478,12 +446,5 @@ namespace meow{
SplayTree<Key, Value>::print() const{
print(_root, 0);
}
- template<class Key, class Value>
- inline void
- SplayTree<Key, Value>::moveTo(SplayTree* __tree2){
- __tree2->clear();
- __tree2->_root = _root;
- _root = NULL;
- }
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-16 19:03:36 +0800