diff options
Diffstat (limited to 'README.asciidoc')
| -rw-r--r-- | README.asciidoc | 164 |
1 files changed, 162 insertions, 2 deletions
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] + + + |======================================================================= |