Skip to content

Commit 0cc772a

Browse files
NASU41NASU41
committed
add multiset
1 parent a5c4c6f commit 0cc772a

4 files changed

Lines changed: 90 additions & 1 deletion

File tree

‎FenwickTree/README.md‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,4 @@
11
# クラス FenwickTree
2-
- - -
32

43
長さ $N$ の long型配列に対し,
54

‎Multiset/Multiset.java‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
class Multiset<T> extends TreeMap<T,Long>{
2+
public Multiset(){
3+
super();
4+
}
5+
public Multiset(List<T> list){
6+
super();
7+
for(T e: list) this.addOne(e);
8+
}
9+
public long count(Object elm){
10+
return getOrDefault(elm,0L);
11+
}
12+
public void add(T elm, long amount){
13+
if(!this.containsKey(elm)) put(elm, amount);
14+
else replace(elm, get(elm)+amount);
15+
if(this.count(elm)==0) this.remove(elm);
16+
}
17+
public void addOne(T elm){
18+
this.add(elm, 1);
19+
}
20+
public void removeOne(T elm){
21+
this.add(elm, -1);
22+
}
23+
public void removeAll(T elm){
24+
this.add(elm, -this.count(elm));
25+
}
26+
public static<T> Multiset<T> merge(Multiset<T> a, Multiset<T> b){
27+
Multiset<T> c = new Multiset<>();
28+
for(T x: a.keySet()) c.add(x, a.count(x));
29+
for(T y: b.keySet()) c.add(y, b.count(y));
30+
return c;
31+
}
32+
}

‎Multiset/README.md‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
# クラス Multiset
2+
3+
本機能は AtCoderLibrary ではなく C++標準ライブラリ `std::multiset` の移植です.
4+
5+
多重集合を表すクラスです.
6+
7+
* 定数個の要素の追加
8+
* 特定の要素の個数
9+
10+
を $O(\log N)$ の時間で求めることができるデータ構造です.
11+
12+
## コンストラクタ
13+
### FenwickTree
14+
```java
15+
public Multiset()
16+
```
17+
18+
空の多重集合を作ります. 計算量 $O(1)$
19+
20+
```java
21+
public MultiSet(List<T> list)
22+
```
23+
`list`の各要素を持った多重集合を作ります. 計算量 $O(`list.size()`)$
24+
25+
## メソッド
26+
### add
27+
```java
28+
public void add(T elm, long amount)
29+
```
30+
多重集合に要素`elm`を`amount`個加えます. 計算量 O(log N)
31+
32+
### addOne
33+
```java
34+
public void addOne(T elm)
35+
```
36+
多重集合に要素`elm`を1個加えます. 計算量 O(log N)
37+
38+
### removeOne
39+
```java
40+
public void removeOne(T elm)
41+
```
42+
多重集合から要素`elm`を1個取り除きます. 計算量 O(log N)
43+
44+
### removeAll
45+
```java
46+
public void removeAll(T elm)
47+
```
48+
多重集合から要素`elm`を全て取り除きます. 計算量 O(log N)
49+
50+
### merge
51+
```java
52+
public static<T> Multiset<T> merge(Multiset<T> a, MMultiset<T> b)
53+
```
54+
`a` と `b`の和集合となる多重集合を新たに構成して返します.

‎README.md‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,10 @@
2222
* [Lazy Segment Tree](https://github.com/NASU41/AtCoderLibraryForJava/tree/master/LazySegTree)
2323
* [Mod Int](https://github.com/NASU41/AtCoderLibraryForJava/tree/master/ModInt)
2424

25+
また, ACL外のアルゴリズムについても必要に応じて実装を進めています.
26+
27+
* [Multiset](https://github.com/NASU41/AtCoderLibraryForJava/tree/master/Multiset)
28+
2529
## プログラムを編集したい方へ
2630
Slackワークスペースへの参加を推奨しています.
2731
各編集者の進捗共有などに利用しているので, 重複を防ぐことができます.

0 commit comments

Comments
 (0)