-
Notifications
You must be signed in to change notification settings - Fork 0
/
RangeSetQuerySqrtTree.cpp
63 lines (62 loc) · 2.25 KB
/
RangeSetQuerySqrtTree.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
* @title RangeSetQuerySqrtTree - 区間setクエリ用平方分割木
* @docs md/segment-tree/RangeSetQuerySqrtTree.md
*/
template<class T, unsigned int bit_length=20> class RangeSetQuerySqrtTree {
using size_t = unsigned int;
RangeIntegerFrequencyQuerySqrtTree<bit_length> tree;
unordered_map<T,set<size_t>> mp;
vector<T> ar;
size_t length;
size_t range_set_size_impl(const int l, const int r) const {
if (l < 0 || length <= l || r < 0 || length < r) return 0;
return (r-l) - tree.range_freq_upper(l,r,r);
}
void update_impl(const size_t idx, const T next) {
T prev = ar[idx];
//更新前の1つ左に影響があるか確認
{
auto itr_r = mp[prev].lower_bound(idx);
//左が存在するなら影響あり
if(itr_r != mp[prev].begin()) {
auto itr_l=itr_r;
itr_l--;
itr_r++;
if(itr_r==mp[prev].end()) tree.erase((*itr_l));
else tree.update((*itr_l),(*itr_r));
}
mp[prev].erase(idx);
}
//更新後の1つ左に影響があるか確認
{
mp[next].insert(idx);
auto itr_r = mp[next].upper_bound(idx);
if(itr_r==mp[next].end()) tree.erase(idx);
else tree.update(idx,(*itr_r));
//左が存在するなら影響あり
auto itr_l = mp[next].lower_bound(idx);
if(itr_l != mp[next].begin()) {
itr_l--;
tree.update((*itr_l),idx);
}
}
ar[idx] = next;
}
public:
RangeSetQuerySqrtTree(const vector<T> & vec):ar(vec),tree(vec.size()) {
length = vec.size();
for(size_t i = 0; i<length; ++i) mp[ar[i]].insert(i);
for(auto& [_,st]: mp) {
size_t l=length,r=length; //このl,rは閉区間 [l,r]
for(size_t idx: st) {
r=idx;
if(l<length && r<length) tree.update(l,r);
l=r;
}
}
}
//idx番目の要素をupdate
void update(const size_t idx, const T val) { update_impl(idx,val); }
//[l,r) range set size
size_t range_set_size(const int l, const int r) const {return range_set_size_impl(l,r);}
};